💡 DP(Dynamic Programming)

• Dynamic Programming = 동적 계획법
• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 부분 문제 반복과 최적 부분 구조를 가진 알고리즘을 더욱 적은 시간 내에 풀 때 사용

💻 원리

• 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푼다
• 나누어 푼 것을 결합하여 최종적인 목적에 도달하는 것
• 각 하위 문제를 해결한 뒤 해결책을 저장하여, 후에 하위 문제가 나왔을 경우 저장해둔 것을 사용해 간단하게 해결

  따라서 동적 계획법은 계산 횟수를 줄일 수 있다. 하위 문제의 수가 기하급수적으로 증가할 때 유용함

• 가능한 모든 방법을 고려해야 한다는 단점이 있음
  (이를 극복하기 위해 나온 것이 그리디 알고리즘)

📝 문제 링크

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

👩‍💻 적용

1. 재귀 함수

부르투포스를 DP로 착각했음.
내가 쓴건 재귀함수를 이용한 top-down 방식이 아니라, 그냥 부르투포스임

let memo = new Array(11).fill(-1);
memo[1] = 1;
memo[2] = 2;
memo[3] = 4;

function dp(num) {
  if (num === 1) return memo[1];
  if (num === 2) return memo[2];
  if (num === 3) return memo[3];

  if (memo[num] != -1) {
    return memo[num];
  }

  memo[num] = dp(num - 1) + dp(num - 2) + dp(num - 3);

  return memo[num];
}

dp(10);

for (let i = 0; i < testCase.length; ++i) {
  console.log(memo[testCase[i]]);
}

• 1의 경우의 수는 1(1)
• 2의 경우의 수는 2(1+1, 2)
• 3의 경우의 수는 4(1+1+1, 1+2, 2+1, 3)
• 문제를 읽으면 4의 경우의 수는 7인 것을 알 수 있다
  (이 때, 7이 1+2+4의 결과라는 것을 알면 점화식을 쉽게 도출할 수 있음)
• 더 확실히 알기 위해 5의 경우의 수 까지 구해보자
  (1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+2+1, 2+1+2, 1+2+2, 3+1+1, 1+3+1, 1+1+3, 3+2, 2+3 => 총 13개)
• n이 4이상일 때, n의 경우의 수는 f(n-1)+f(n-2)+f(n-3)이라는 것을 알 수 있음

2. Bottom-Up : 반복문

let dp = new Array(11);

dp[0] = 1;
dp[1] = 2;
dp[2] = 4;

for (let i = 3; i < 11; ++i) {
  dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}

for (let i = 0; i < testCase.length; ++i) {
  console.log(dp[testCase[i] - 1]);
}

• 상태 정의 : dp 배열을 만들었을 때 index 값이 의미하는 상태
• ex) dp[0] = 1의 경우의 수 / dp[1] = 2의 경우의 수
  즉 dp[i] = [i+1]의 경우의 수
• 점화식 구하기 : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

동작 방법

let dp = new Array(11);

dp[0] = 1;
dp[1] = 2;
dp[2] = 4;

for (let i = 3; i < 11; ++i) {
  dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
  console.log(`dp[${i}]: ${dp[i]}`)
}

for (let i = 0; i < testCase.length; ++i) {
  console.log(dp[testCase[i] - 1]);
}

console 값을 찍어보면 아래와 같다

dp[3]: 7
dp[4]: 13
dp[5]: 24
dp[6]: 44
dp[7]: 81
dp[8]: 149
dp[9]: 274
dp[10]: 504