동적 계획법이란 어떻게 풀어야 할지 모르는 문제가 있을 때, 그 문제를 역시 어떻게 풀어야 할지 모르는 더 작은 문제들로 나누는 것입니다.
다음과 같은 문제를 생각해 봅시다. 다음과 같이 정의되는 $n$번째 피보나치 수 $f_n$을 구해야 합니다.
$$ \begin{aligned} f_0 &= 0 \\ f_1 &= 1 \\ f_n &= f_{n-2} + f_{n-1} \end{aligned} $$위의 정의를 함수로 작성하면 문제를 재귀적으로 풀 수 있습니다.
int f(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return f(n - 2) + f(n - 1);
}
그러나 $n$이 ~40을 넘으면 이러한 풀이는 매우 오래 걸립니다. 실행 시간 $T(n)$을 대략적으로 추정해 봅시다.
$f_n$을 계산하려면 $f_{n-1}$과 $f_{n-2}$를 재귀적으로 계산해야 합니다:
$$ T(n) = T(n-2) + T(n-1) + \Theta(1) $$ $f_{n-1}$을 계산하는 데에는 $f_{n-2}$를 계산할 때보다 적지 않은 연산이 필요합니다. 앞의 내용과 합치면, 이는 $f_n$을 계산하는 데 $f_{n-2}$보다 적어도 두 배 많은 연산이 필요하다는 뜻입니다: $$ T(n) \ge 2 \cdot T(n-2) $$ 따라서 실행 시간은 지수적으로 증가합니다: $$ T(n) \ge \Omega(2^{n/2}) $$연습 문제. $f_n$을 계산할 때 재귀 호출의 정확한 총 횟수는 얼마입니까?
결과 기억하기
문제를 더 작은 문제로, 그리고 어느 시점에는 기저 문제로 환원한다는 기본 아이디어 자체는 전적으로 옳습니다.
그러나 이러한 문제의 개수가 지수적으로 늘어나지 않도록 주의해야 합니다. 이를 위한 가장 간단한 방법은 불필요한 작업을 전혀 하지 않는 것입니다. 한 번 $f_n$을 계산했다면 그 값이 무엇인지 기억해 두고, 다음에 그 값이 필요할 때 바로 사용합시다.
가장 편리한 방법은 필요한 모든 $f_n$ 값을 담을 배열을 만들고, 재귀 함수 대신 배열의 기저값을 초기화한 다음, 나머지 모든 $f_i$를 반복문으로 순회하면서 이전 반복에서 이미 구한 $f_{i-2}$와 $f_{i-1}$을 사용하여 계산하는 것입니다:
const int n = 100;
int f[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; i++)
f[i] = f[i - 2] + f[i - 1];
($n$이 크면 마지막 줄에서 오버플로가 발생하므로, 이러한 문제에서는 흔히 모든 값을 모듈로 연산하여 다룹니다.)
동적 계획법(영어: dynamic programming, DP)이란 바로 위에서 소개한 접근 방식을 말하며, 보통 다음과 같은 일반적인 단계로 이루어집니다:
- $n$에 대한 문제를 $n$보다 작은 수에 대한 문제로 환원합니다. 즉, 어떤 재귀식을 찾습니다.
- 부분 문제의 답을 저장할 배열(또는 다른 자료 구조)을 만드십시오.
- 배열의 앞부분을 직접 채웁니다(공식이 적용되지 않는 기저 사례).
- 배열을 이미 알려진 값에서 아직 알려지지 않은 값 쪽으로 순회하면서 공식에 따라 답을 채웁니다.
- 답을 출력합니다. 답은 보통 배열의 마지막 칸에 기록되어 있습니다.
동적 계획법으로 문제를 풀려면 다음 5가지 질문에 답해야 합니다:
- 배열에는 무엇이 들어 있습니까? (대개 가장 중요한 질문입니다)
- 배열의 시작 부분은 어떻게 초기화합니까?
- 배열을 어떤 순서로 순회합니까? (대부분 왼쪽에서 오른쪽으로 순회하지만, 항상 그런 것은 아닙니다)
- 배열의 원소는 어떤 공식으로 계산합니까?
- 배열의 어디에 답이 있습니까?
이 기법으로 수많은 중요한 문제를 풀 수 있으며, 이 절에서 그 사실을 확인해 보겠습니다.