문제를 풀기 위한 아이디어 규칙이 복잡해보이지만 숫자를 대입하여 생각해보면 결국 바로 인접한 집끼리만 다른 색이면 된다는 것이다. 일단 주어진 각 집을 빨강,초록,빨강으로 칠하는 비용들을 2차원 배열에 저장한다. input = [ [26, 40, 83], [49, 60, 57], [13, 89, 99] ] 그 다음으로는 첫번째집을 R로 칠한 경우 / 첫번째 집을 G로 칠한 경우 / 첫번째 집을 B로 칠한 경우를 모두 다 따져주면 된다. 이를 점화식으로 세우면, 두번째 집부터는 다음과 같은 점화식이 성립한다. input[i][0] = min(input[i-1][1], input[i-1][2]) + input[i][0] input[i][1] = min(input[i-1][0], input[i-1][2]) +..

문제를 풀기 위한 아이디어 동적 프로그래밍 유형이 다들 그러듯이 점화식만 잘 세우면 된다. 점화식은 다른 분들의 코드를 보니까 여러 점화식이 나올 수 있는데 나는 그림을 보고 바로 유추할 수 있는 점화식을 사용했다. P(1) = 1 P(2) = 1 P(3) = 1 P(4) = 2 P(5) = 2 P(6) = 3 P(7) = 4 P(8) = 5 까지는 값을 미리 넣어놓고, P(9)부터는 P(N) = P(N-5) + P(N-1)을 사용했다. 사실 P(1)~P(3)까지만 넣어놓고 P(4)부터 P(N) = P(N-2) + P(N-3)을 쓰는 것이 더 좋은 방법인 것 같긴 하다. 하지만 나는 그림을 보고 예를 들어 P(9) = P(4) + P(8)의 합이라고 딱 그림에서 보기 쉬웠기 때문에 이렇게 점화식을 세웠다..

동적계획법이란? 큰 문제를 한 번에 해결하기 힘들 때 작은 문제로 나누어 푸는데, 이 때 이전에 계산한 값을 저장해두었다가 다시 사용하는 것이 핵심이다. 큰 문제를 작은 문제로 분할하여 푼다는 점에서 분할정복 알고리즘과 유사하지만, 한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다르다. 동적계획법이 필요한 이유 그렇다면 왜 동적계획법이 필요한 것일까? 피보나치 수열을 예를 들어보자면, 점화식은 F(n) = F(n-1) + F(n-2)가 된다. 이는 간단하게 재귀함수만으로 구현할 수 있지만, 비교적 그렇게 어마어마하게 크지 않은 수인 50만 생각해보더라도 50을 구하기 위해서 불필요한 재귀가 일어나게 되어 엄청나게 많은 연산이 요구된다. 위의 그림에서도 ..

문제를 풀기 위한 아이디어 다이나믹 프로그래밍 유형은 점화식을 세우는 것이 가장 중요하다. 이 문제의 점화식은 타일의 개수가 N개일 때 만들 수 있는 N자리수 이진수의 모든 개수를 T(n)이라 하면, T(n) = T(n-2) + T(n-1)이다. 다이나믹 프로그래밍을 푸는 방법에는 Top-down 방식과 Bottom-up 방식이 있는데, 처음에 이문제를 Top-down 방식으로 푸니까 stack이 계속 초과되었다고 나와서 Bottom-up 방식으로 반복문으로 풀었다. 내가 작성한 코드 (자바스크립트) function solution(N) { const memo = new Array(); memo[1] = 1; memo[2] = 2; for (let i = 3; i

문제를 풀기 위한 아이디어 피보나치 수열의 n번째 숫자는 n-2번째 수와 n-1번째 수의 합이 된다. 피보나치 수열을 재귀함수로만 풀 수도 있지만, 이렇게 하게 되면 비교적 작은 수더라도 실행횟수가 어마어마해진다. 예를 들어 fibonacci(5) 함수를 통해 피보나치 수열의 5번째 수를 구하려고 한다면, 아래의 그림과 같다. fibonacci(5) = fibonacci(4) + fibonacci(3) 이기 때문에, fibonacci(4)는 또 재귀를 부르고 fibonacci(3)도 재귀를 부른다. 이렇게 하면 안좋은 점이 2같은 경우에 3번이나 중복되고 있어 연산회수가 불필요하게 많아지고 있다. 5여서 망정이지 50번째 수만 되더라도 재귀를 쓰면 반복횟수는 어마어마해진다. 따라서 이미 구해놓은 값은 저..

let fs = require("fs"); let input = fs.readFileSync("예제.txt").toString().split(" "); const N = Number(input[0]); const K = Number(input[1]); const numbers = new Array(Number(input[0]) + 1); let primeNumber; const count = []; for (let i = 2; i < numbers.length; i++) { numbers[i] = i; } for (let i = 2; i