🎯 다이나믹 프로그래밍 개념

DP라고도 불리는 다이나믹 프로그래밍은 명칭과 의미의 상관관계는 없다. 보통 큰 문제를 작은 문제로 나눠서 문제를 해결할 때 이용되는 알고리즘이다.

사람들에게 익숙한 예시는 피보나치 수열이 있다. 피보나치 수열 역시 재귀를 사용하여 수열의 큰 문제를 작은 문제로 나눠서 해결하는 과정이다. 하지만 피보나치 수열과 다이나믹 프로그래밍은 개념적으로 조금 다른 점을 갖는다.

💎 피보나치 수열의 핵심

  • 문제의 크기에 상관 없이 어떤 한 문제의 정답이 일정하다.
  • 몇번째 피보나치 수를 구하든지에 상관없이 n번째 피보나치수는 항상 동일하다.

💎 다이나믹 프로그래밍의 핵심

  • 각 작은 문제는 한 번만 풀어야 한다.
  • 같은 문제는 구할 때마다 정답이 같다.
  • 정답을 한 번 구했으면, 어딘가에 메모해놓는다.
  • 메모하는 것을 코드에서는 배열로 구현할 수 있다.
  • 메모한다고 해서 Memoization이라는 용어를 사용한다.

🎯 다이나믹 프로그래밍 구현

let fibo = (n) => (n > 2 ? fibo(n - 2) + fibo(n - 1) : 1);

위는 일반적으로 재귀를 이용하는 피보나치 수의 구현이다. 하지만 결론적으로 피보나치 수열은 이미 계산했던 값을 이용하는 것이라 매우 비효율적이다.

예를 들어 n의 값으로 5가 들어갔다고 가정해보자. 5번째 피보나치 수를 구하기 위해 4번째, 3번째의 피보나치 수를 구해야 하고 내부 4번째 수를 구하기 위해서는 또 3번째와 2번째의 피보나치 수를 구해야 하고, 3번째 피보나치 수를 구하기 위해 2번째와 1번째의 피보나치 수를 구해야 한다.

위 단락의 과정은 4번째 피보나치 수를 구한 방식이다. 3번째 피보나치를 구하기위해서 또 3번째 2번째 피보나치 수를 구하고 2번째 1번째 피보나치 수를 구하는, 무한반복의 과정이 이루어진다.

그래서 아래의 방법을 이용할 수 있다.

let fiboArr = [0];
let fiboWithMemoization = (n) => {
  if (n <= 3) {
    fiboArr[n] = 1;
  }

  if (!fiboArr[n]) {
    fiboArr[n] = fiboWithMemoization(n - 1) + fiboWithMemoization(n - 2);
  }

  return fiboArr[n];
};

위는 DP를 이용한 피보나치 수 구현이다. fiboArr이라는 곳에 내가 계산해둔 피보나치 수를 저장해둔다. 이러한 방식의 차이는 속도면에서 어마어마한 차이를 가져온다. 이를테면 50번째 피보나치 수를 구하는 것은 메모이제이션을 사용하지 않은 단순 재귀에서는 어마어마한 시간이 걸리지만, 메모이제이션을 사용한 피보나치 수 구하기 함수를 이용하면 금방 나온다.

🎯 다이나믹 프로그래밍의 시간복잡도

메모이제이션을 하지 않으면, 대략 O(2n^2) 만큼의 시간복잡도가 걸린다. 하지만 메모이제이션을 하면 대략 O(3n)만큼의 시간에 값을 구하게 된다.

🎯 다이나믹 프로그래밍의 구현 방식

  1. Top-down 큰 문제부터 문제를 쪼개가며 작은 문제로 만들고 다시 합쳐가며 원래 문제를 푸는 방식이다. 위에서 봤던 예제가 Top-down 방식이다.

  2. Bottom-up 작은 문제들을 모아서 큰 문제를 만들어 쌓아 올려가는 방식이다.

// bottom-up의 예제
int d[100];
int fibonacci(int n) {
  d[0] = 0;
  d[1] = 1;

  for(int i=2; i<=n; i++){
    d[i] = d[i-1] + d[i-2];
  }

  return d[n];
}

설명은 했지만 두 방법 중 하나만 알아도 다이나믹 프로그래밍 문제를 푸는데 큰 지장은 없다.