[백준 문제풀이] 2798번 블랙잭

2798번 블랙잭 (Bronze 2)

문제

https://www.acmicpc.net/problem/2798

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

배운 것

조합을 위한 알고리즘은 재귀를 사용해서 만든다.

forEach의 parameter는 element, index, array가 있다. element는 각각의 원소이고, index는 해당 원소의 위치, array는 forEach가 진행되는 배열을 말한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

input[0] = input[0].split(" ");
const N = parseInt(input[0][0]);
const M = parseInt(input[0][1]);
const cards = input[1].split(" ").map((card) => parseInt(card));
let answer = 0;

const getCombinations = (arr, selectNumber) => {
  const results = [];
  if (selectNumber === 1) {
    return arr.map((element) => [element]);
  }

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNumber - 1);
    const attached = combinations.map((element) => [fixed, ...element]);
    results.push(...attached);
  });
  return results;
};

getCombinations(cards, 3).forEach((result) => {
  const sum = result[0] + result[1] + result[2];
  if (sum <= M && answer <= sum) {
    answer = sum;
  }
});

console.log(answer);

[백준 문제풀이] 1011번 Fly me to the Alpha Centauri

1011번 Fly me to the Alpha Centauri (Gold 5)

느낀 점

어려운 문제도 계속 생각하면 풀린다.

문제

https://www.acmicpc.net/problem/1011

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다.

그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. )

김우현은 공간이동 장치 작동시의 에너지 소모가 크다는 점을 잘 알고 있기 때문에 x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.

김우현을 위해 x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

풀이

y의 최댓값이 2의 31승 –1로 컸기 때문에 수학적으로 접근해야하는 문제라고 생각했다. 고로 규칙성을 찾기 위해 노력했다.

처음에는 오직 1만 이동할 수 있고 마지막에도 오직 1을 이동해야 하기 때문에 이동 count의 최대 이동거리와 전체 이동 중 1회 이동거리가 가장 긴 수 간의 규칙성을 발견할 수 있었다.

결론적으로 이동 횟수가 홀수 2n-1회일 때는 최대 이동거리를 n^2이며, 짝수 2n회일 때는 n(n+1)라는 식을 유도할 수 있었다.

완전 탐색으로 접근할 경우 시간초과가 뜰 것 같아서, 위의 수식을 사용해서 이동거리가 포함될 최대 이동 횟수 중 홀수와 짝수일 경우를 조건문을 통해 풀이했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = parseInt(input[0]);
const answerArr = [];

for (let i = 1; i <= T; i++) {
  const c = input[i].split(" ").map((num) => parseInt(num));
  const distance = c[1] - c[0];
  const max = Math.ceil(Math.sqrt(distance));
  if (distance <= max * (max - 1)) {
    answerArr.push(max * 2 - 2);
  } else {
    answerArr.push(max * 2 - 1);
  }
}

console.log(answerArr.join("\n"));

[백준 문제풀이] 10870번 피보나치 수 5

10870번 피보나치 수 5 (Bronze 2)

문제

https://www.acmicpc.net/problem/10870

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

풀이

꼬리 재귀로 풀이했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

const fs = require("fs");
const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

function fibonacci(n, number = 0, total = 1) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return total;
  } else {
    return fibonacci(n - 1, total, number + total);
  }
}

const answer = fibonacci(input);

console.log(answer);

[백준 문제풀이] 10872번 팩토리얼

10872번 팩토리얼 (Bronze 3)

문제

https://www.acmicpc.net/problem/10872

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

출력

첫째 줄에 N!을 출력한다.

재귀함수란?

재귀함수란 함수에서 스스로를 호출해서 명령을 수행하는 함수이다. 반복문을 사용하는 명령은 모두 재귀 함수를 통해 구현이 가능하고, 재귀함수를 반복문으로 만드는 것도 가능하다.

재귀함수를 만들 때는, 재귀 호출을 그만둘 수 있는 조건을 만들어야 무한 루프를 막을 수 있다.

재귀 함수는 단순히 명령을 반복하는 것이 아니라, 함수를 반복해서 호출하므로 메모리를 많이 차지하기 때문에 반복문에 비해 느리다.

그럼에도 재귀함수를 사용하는 이유는 변수를 만들 필요가 없으며, 반복문을 사용하지 않기 때문에 코드가 매우 간결해지기 때문이다.

다만 위에서 말한대로 단순한 반복문이 아니라 반복적으로 함수를 호출하기 때문에, 해당 함수에서 필요한 것들을 메모리에 저장하는 과정에서 스택 메모리가 커지고, stack overflow가 발생할 수 있다.

이러한 에러를 방지하기 위해 사용하는 방법이 ‘꼬리 재귀 최적화’ 이다.

꼬리 재귀는 재귀 함수의 호출 이후 바로 결과만 반환할 수 있도록 하는 방법이다. 이러한 것은 코드에서는 바로 볼 수 없고, 자바스크립트 언어에서 ‘꼬리 재귀 최적화’라는 기능을 지원해주기 때문이다. 이러한 이유로, 꼬리 재귀에서 return 값은 마지막(tail - 꼬리)부분에 있어야한다.

재귀 함수 예시

1
2
3
4
5
6

function factorial(n) {
  if (n === 1) {
    return total;
  }
  return n * factorial(n - 1);
}

꼬리 재귀 예시

1
2
3
4
5
6

function factorial(n, total = 1) {
  if (n === 1) {
    return total;
  }
  return factorial(n - 1, n * total);
}

출처: https://joooing.tistory.com/entry/재귀-→-꼬리-재귀-Tail-Recursion [joooing]

둘이 뭐가 다른 걸까?

위에서 설명된 일반 재귀는 값을 받으면, 그 값에 연산을 하고 다시 재귀 함수에 전달해줬다. 하지만 꼬리 재귀는 아무것도 하지 않고 인수로 total 값을 전달만 해준다. 결과 값에 아무 일도 하지 않고 다시 반환하기 때문에, 스택 오버플로우가 발생하지 않게 되는 방식이다.

콜스택과 스택 오버플로우, 꼬리재귀 최적화

자바스크립트는 단일 스레드 프로그래밍 언어이다. 이 말은 쉽게 말하자면, 자바스크립트라는 언어는 안에 들어있는 계산 요정님이 한 명에다가 멀티태스킹은 할 줄 모른다라는 것이다.

그렇기 때문에 콜스택이라는 실행 대기열을 만들고, 하나씩 대기열에서 명령을 꺼내서 처리해준다.

근데 이 요정님께도 역량과 나름의 사정이 존재하기 때문에 우리가 요청할 수 있는 대기열의 최대 길이는 13939개 정도이다.

그래서 많은 양의 함수가 있을 때 요정님께

첫 번째로 값을 받으시구요. 두 번째로 이 값을 곱해서 세 번째로 아까 이 값 드렸던 위치로 전송 부탁드려요.

같이 여러 일로 내용을 나눠서 요청을 하게 되면, 요정님은 파업해버리신다. 이 파업선언이 일반 재귀에서 마주할 수 있는 Uncaught RangeError: Maximum call stack size exceeded이다.

그렇기 때문에 꼬리재귀를 사용해서 요정님이 할 일을 간단 명료하게 줄여주는 것이다. 꼬리재귀를 사용하게 되면

다음 함수 부르실 때, 곱해진 이 값좀 같이 넘겨주세요.

라는 간략화된 요청으로 말할 수 있게된다.

풀이

꼬리 재귀를 구현해서 풀었다. 재귀는 아직 너무 어렵다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const fs = require("fs");

const input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

function factorial(n, total = 1) {
  if (n === 0 || n === 1) {
    return total;
  } else {
    return factorial(n - 1, n * total);
  }
}

const answer = factorial(input);

console.log(answer);

[백준 문제풀이] 1002번 터렛

1002번 터렛 (Silver 4)

문제

https://www.acmicpc.net/problem/1002

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 –1을 출력한다.

풀이

각 터렛의 위치가 [같음, 다름] 각각의 경우에서 원이 [내접할 때, 외접할 때, 겹칠 때, 반지름이 같을 때]로 나눠서 쉽게 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const T = parseInt(input[0]);
const answerArr = [];

function checkCount(numArr) {
  const xFir = numArr[0];
  const yFir = numArr[1];
  const rFir = numArr[2];
  const xSec = numArr[3];
  const ySec = numArr[4];
  const rSec = numArr[5];
  const max = Math.max(rFir, rSec);
  const min = Math.min(rFir, rSec);

  const distance = Math.sqrt(
    Math.pow(xFir - xSec, 2) + Math.pow(yFir - ySec, 2)
  );
  if (xFir === xSec && yFir === ySec) {
    if (rFir === rSec) {
      answerArr.push(-1);
      return;
    } else {
      answerArr.push(0);
      return;
    }
  } else {
    if (distance === max) {
      answerArr.push(2);
      return;
    } else if (distance < max) {
      if (distance + min === max) {
        answerArr.push(1);
        return;
      } else if (distance + min < max) {
        answerArr.push(0);
        return;
      } else {
        answerArr.push(2);
        return;
      }
    } else {
      if (distance === max + min) {
        answerArr.push(1);
        return;
      } else if (distance > max + min) {
        answerArr.push(0);
        return;
      } else {
        answerArr.push(2);
        return;
      }
    }
  }
}

for (let i = 1; i <= T; i++) {
  const numbers = input[i].split(" ").map((num) => parseInt(num));
  checkCount(numbers);
}

console.log(answerArr.join("\n"));