DP 란?

• 동적계획법, Dynamic Programming 이라고도 불린다.
• 큰 문제를 작은 문제로 나누어 푸는 알고리즘 방법 중 하나이다.

DP 알고리즘이 흘러가는 방법을 간단하게 추려보면 이렇다.

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제를 푼다.
3. 작은 문제의 해답을 이용해서 큰 문제를 푼다.

이 때 작은 문제들을 중복되지 않게 푸는 것이 매우 중요하다.

DP 알고리즘 예제

• DP의 대표적인 예제로는 피보나치 수열 구하기 문제가 있다.
• 피보나치 수열은 어떤 수열의 항이, 앞의 두 항의 합과 같은 수열을 의미한다.

function fibonacci(n) {
  if (n <= 1) return n; // 1보다 작으면 첫 번째 수이므로 리턴
  
  const memo = [0, 1]; // 경우의 수를 미리 선언
  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i-1] + memo[i-2];
  }
  return memo[n];
}

console.log(fibonacci(10)); // 55

위의 피보나치 수열을 구하는 방법으로 메모이제이션(memoization) 이라는 방법을 사용한다. 메모이제이션은 이전에 계산한 값을 저장해 두어, 같은 값이 필요할 때 중복 계산을 피하는 기법이다.

이를 위해 memo라는 배열을 사용하며, memo[0] 과 memo[1] 은 미리 계산해 둔다. 그리고 반복문을 이용하여 memo[i-1] 과 memo[i-2] 의 값을 더하여 memo[i] 에 저장한다. 이렇게 하면 memo[n] 에는 n번째 피보나치 수가 저장된다.

이 코드의 시간 복잡도는 O(n) 이며, DP 알고리즘을 적용하여 효율적으로 문제를 해결할 수 있다.

피드백은 언제나 감사히 받겠습니다!