[JS] 동적계획법 (DP)

❗️동적계획법

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
• 작은 문제가 반복해서 발생하는데 결과 값이 항상 같은 경우 사용
• Memoization : 결과값을 저장해뒀다가 다시 사용

✅ 구현 방식

• Top-down : 큰 문제부터 쪼개가며 작은 문제로 만들고 다시 합침 (재귀)
  함수 호출 과정이 많이 들어가서 스택 오버플로우 문제 발생 가능

• Bottom-up : 작은 문제들을 모아서 큰 문제를 만들어 쌓아감 (반복문)

❗️동적계획법 vs 분할정복

• 분할정복은 작은 문제가 중복 없이 해결

✅ 피보나치수열의 재귀 & dp 함수 호출 횟수 비교

const N = 30;

// 재귀사용
let count1 = 0;
function fibo1(N) {
  if (N <= 2) {
    count1++;
    return 1;
  } else {
    return fibo1(N - 1) + fibo1(N - 2);
  }
}
fibo1(N);
console.log(`재귀함수 호출 횟수 : ${count1}`); // 832040

// dp사용
let count2 = 0;
let dp = [];
function fibo2(N) {
  dp[0] = 1;
  dp[1] = 1;

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

  return dp[N - 1];
}
fibo2(N);
console.log(`DP함수 호출 횟수 : ${count2}`); // 28