동적계획법 (DP, Dynamic Programming)

DP란?

동적계획법, DP, 다이나믹 프로그래밍 모두 같은 말이며, 복잡한 문제를 작은 문제로 나누어 풀고, 그 결과를 저장하여 중복 계산을 줄이는 방법이다.

이를 이해하기 위해 대표적인 예제인 피보나치 수열을 살펴보자.

피보나치 수열

1, 1, 2, 3, 5, 8 ···

피보나치 수열은 1과 1로 시작한다.

1번째 피보나치 수는 1이고, 2번째 피보나치 수는 1이다. 그 다음 3번째 부터는 바로 앞 두 피보나치 수를 더한 값이 된다.

즉, 피보나치 수열은 앞의 두 수를 더해서 다음 수를 만들어가는 수열이다.

이제 이 로직을 재귀함수로 구현해본다면 다음과 같다.

function fibonacci(n) {
  if (n == 0 || n == 1) return n;
  return fibonacci(n - 2) + fibonacci(n - 1);
}

console.log(fibonacci(5)); // 5

5번째 피보나치 수를 출력했을 때, 3번째 값 2와 4번째 값 3을 더한 5가 정상적으로 출력된다.

하지만 이 재귀함수는 성능이 좋지 못한 코드다. 그 이유는 그림을 통해 살펴보자!
(열심히 그렸다 ㅋ)

그림을 보면 중복되는 호출이 많다는 것을 알 수 있다. 만약 5번째가 아닌 100번째를 호출한다면 중복해서 계산하는 부분은 훨씬 많을 것이다. (」ﾟﾛﾟ)｣NOOOooooo━

중복 계산으로 인해 낭비되는 시간을 어떻게 줄일 수 있을까?

간단하다. 바로 계산 결과를 저장하면 된다. 그리고 같은 계산이 필요할 때 저장된 결과를 사용하면 된다. 그러면 함수의 호출 수가 훨씬 줄어들고 성능이 향상될 것이다.

Top-down 방식과 Bottom-up 방식

function fibonacci(n, memo) {
  if ((n == 0) | (n == 1)) return n;

  if (memo[n] == null) {
    memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
  }

  return memo[n];
}

console.log(fibonacci(5, {})); // 5

위와 같은 방식은 fibonacci(n)부터 fibonacci(0)로 접근하므로, Top-down 방식이라고 한다. 반대로 fibonacci(1)부터 fibonacci(n)까지 접근하는 방식을 Bottom-up 방식이라고 한다. Bottom-up 방식은 다음과 같다.

function fibonacci(n) {
  if (n <= 1) return n;

  let table = [0, 1];

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

  return table[n];
}

Top-down 방식에서 memo를 채워 나가는 것을 메모이제이션이라 하며, Bottom-up 방식에서 memo를 채워 나가는 것을 타뷸레이션이라고 한다.

메모이제이션

Top-down 방식으로 재귀로 구현된다.

메모이제이션은 계산 결과를 저장해서 여러 번 계산하지 않도록 하는 기법이다.

계산하려는 데이터가 있는지 검색하고, 데이터가 없다면 함수를 호출해 계산을 하고 그 결과를 저장시키면 된다.

메모이제이션은 재귀적인 기법으로 어려운 문제를 간단하게 해결할 수 있고 계산 결과를 저장하고 재사용하기 때문에 속도가 빠르는 장점이 있다. 하지만 메모이제이션도 재귀를 사용하기 때문에 함수 하나를 호출하는 것보다 오버헤드가 더 클 수 밖에 없다.

하지만 꼭 재귀를 써야만 중복 계산을 줄일 수 있을까?
꼭 그렇지는 않다. 반복문을 이용해 같은 효과를 얻을 수도 있다.

이러한 방식이 바로 타뷸레이션이다.

타뷸레이션

Bottom-up 방식은 반복문을 통해 구현된다.

타뷸레이션은 작은 문제부터 차례대로 계산하여, 그 결과를 테이블에 저장하는 방식이다.

타뷸레이션은 계산에 필요하지 않을 수도 있는 값도 미리 계산해 테이블에 저장하기 때문에 중복 계산 없이 빠르게 문제를 해결할 수 있다.

접근 방법

1. 완전탐색으로 문제를 풀어본다.
2. 중복되는 하위 문제를 발견했다면 문제를 하위 문제로 나누어 푼다.
3. 저장 방법을 결정한다.
	- 1차원 배열 : 문제에서 이전 값만으로 충분한 경우
    - 2차원 배열 : 두 가지 값을 저장해야 할 경우
4. 점화식을 도출한다.
5. DP 테이블을 메모이제이션 or 타뷸레이션 방식으로 채운다.
6. 결과를 도출한다.

문제 추천

70. Climbing Stairs
746. Min Cost Climbing Stairs
322. Coin Change
62. Unique Paths
12865번 평범한 배낭