Dynamic Programming (dp)
dp는 굉장히 널리 사용되는 기법으로 정말 다양한 난이도의 문제에서 사용됩니다. 배열을 기반으로 과거의 어떤 상태를 미리 계산해두고 그 값을 계속 재활용해 효율적인 작동을 하도록 만드는 것이 dp입니다. 다양하게 사용되는 만큼 형태도 다양하고 다른 알고리즘과 함께 사용되기도 하며 여러가지 최적화를 통해 더 효율적으로 동작하게 만들 수도 있습니다.
\( m \)개의 정수 \( a_i \)를 입력받아서 \( a_i \)번째 피보나치 수를 \( 10^9 + 7 \)로 나눈 나머지를 출력하는 문제를 생각해봅시다. 단, \( F_0 = 0, \,\, F_1 = 1 \)이고 \( 0 \leq a_i \leq 10,000 \) 입니다. 이전에 살펴봤던 대로 재귀를 통해 구현하게 되면 시간복잡도가 지수 형태로 굉장히 커집니다. 재귀롤 통한 피보나치는 중복 호출도 많고, 하나의 피보나치 수를 찾는 것이 아니기 때문에 매번 새로 계산하지 않고 한 번만 계산한 후 재활용 하는 방식을 고려해야 합니다. 이것을 dp라고 부릅니다.
constexpr int MOD = 1e9 + 7;
int main() {
int fibo[10001];
fibo[0] = 0; fibo[1] = 1;
for (int i = 2; i <= 10000; i++)
fibo[i] = (fibo[i - 1] + fibo[i - 2]) % MOD;
int m; cin >> m;
while (m--) {
int n; cin >> n;
cout << fibo[n] << '\n';
}
}
이렇게 fibo 배열을 통해서 선형 시간에 피보나치 수를 모두 구해놓고 필요할 때마다 접근해서 사용할 수 있었습니다. 이 코드에서 핵심은 fibo[i - 1] + fibo[i - 2] 입니다. 이렇게 구성하면 이전에 계산했던 값을 추가적인 계산 없이 바로바로 가져다 쓸 수 있습니다. dp는 일반적으로 배열로 구현되며 배열의 인덱스로 어떤 상태를 나타내서 필요한 상태의 값을 \( O(1) \)에 가져오는 것이 핵심입니다.
위 코드처럼 낮은 인덱스에서 높은 인덱스로 올라오는 방식을 bottom-up dp라고 합니다. 가장 대중적으로 사용되는 방식이며 보통 반복문으로 구현됩니다. 반대로 위에서 내려오는 방식도 있습니다. 이것을 top-down dp라고 부르고 보통 재귀를 통해 구현됩니다. 앞 챕터에서 재귀로 피보나치를 구했던 코드에서 약간만 수정하면 됩니다. 메모이제이션(memoization)이라고도 볼 수 있습니다. 이 문제를 top-down dp로 구현해 보면 다음과 같습니다.
constexpr int MOD = 1e9 + 7;
int dp[10001];
int fibo(int x) {
if (dp[x] != -1) return dp[x];
if (x == 0) return dp[x] = 0;
if (x == 1) return dp[x] = 1;
return dp[x] = (fibo(x - 1) + fibo(x - 2)) % MOD;
}
int main() {
fill(dp, dp + 10001, -1);
int m; cin >> m;
while (m--) {
int n; cin >> n;
cout << fibo(n) << '\n';
}
}
bottom-up 코드는 시작하자마자 1만개의 피보나치 수를 모두 계산하고 시작했는데, top-down 에서는 요청을 받으면 계산했습니다. 결과는 똑같지만 메모리와 속도 측면에서 약간의 차이가 있습니다. bottom-up은 모두 계산하고 시작하기 때문에 실행하고 약간의 딜레이 후 입력을 받기 시작합니다. 대신 입력이 들어오면 출력은 바로 나옵니다. top-down에서는 아무런 딜레이 없이 시작하지만 입력이 들어온 후 값이 계산되어 있지 않다면 그때 계산하고 출력합니다.
여기서 1만 길이의 배열을 미리 만들어서 저장해 두는 것이 비효율적이라고 느껴질 수 있습니다. 실제로 어떤 숫자가 들어올지 모르기 때문입니다. 그런 경우 top-down 방식에 1만개짜리 배열을 만드는 대신 hash map을 적용해 그때그때 필요한 숫자만 저장해서 메모리를 최대한 줄일 수 있습니다. top-down과 bottom-up은 상황에 따라 적절히 골라서 사용해야 합니다.
연습문제
dp는 길게 설명하기보단 직접 많은 문제를 풀어 보는 것이 중요합니다. 그래서 기초적인 dp를 소개하고 많은 연습문제를 제시하는 것으로 마치도록 하겠습니다. 아래 문제는 기본적인 dp의 유형입니다. 이 외에도 비트마스킹을 이용한 dp, 트리에서의 dp 등 여러 알고리즘과 같이 조합될 수 있습니다. 또, convex hull, divide and conquer 등 여러 기법을 사용해서 최적화하는 고급 기술들도 등장하게 됩니다. 고급 최적화 알고리즘에 대해서는 후반부에 다루도록 하겠습니다.