동적 계획법의 표준적인 접근 방식은 부분 문제의 답을 저장할 배열을 만들고 반복문으로 그 배열을 순회하면서 이미 알고 있는 값으로부터 알지 못하는 값을 계산해 나가는 것입니다. 그러나 필요한 모든 값이 이미 계산되어 있도록 하는 순회 순서를 고안하기가 어렵거나 아예 불가능한 경우도 있습니다.
이런 경우에는 반복문 대신 메모이제이션이라는 방법을 사용할 수 있습니다. DP를 재귀 함수로 계산하되, 계산한 결과를 저장해 두었다가 같은 입력 인자로 함수가 다시 호출되면 그 결과를 곧바로 반환하는 것입니다.
#간단한 예시
이러한 방식으로 $n$번째 피보나치 수를 구하는 문제를 풀어 봅시다.
처음에는 모든 $f[i] = -1$로 둡니다. 이는 해당 상태에 대한 값이 아직 계산되지 않았음을 나타냅니다. 다음으로, 기저 값으로 $f[0] = 0$과 $f[1] = 1$을 둡니다.
이제 전이 함수를 작성합시다. 이 함수는 맨 처음에 구하려는 값이 이미 계산되었는지 확인하고, 계산되지 않았다면 재귀적으로 그 값을 계산합니다.
int f[n] = {-1};
f[0] = 0;
f[1] = 1;
int g(int k) {
if (f[k] == -1)
f[k] = g(k - 2) + g(k - 1);
return f[k];
}
실행 시간은 마찬가지로 $O(n)$입니다. 각 값을 한 번씩만 계산하기 때문입니다. 하지만 함수 호출에 드는 상수가 단순한 반복문보다 훨씬 크기 때문에 실제 실행 시간은 몇 배 더 길어집니다.
또한 이러한 DP에서는 실제로 필요한 상태만 방문한다는 것이 보장되며, 이 덕분에 일부 문제에서는 더 나은 점근적 복잡도를 얻을 수 있다는 점도 알 수 있습니다.
#캐싱
더 일반적으로 말하면, 우리가 하는 일은 캐싱, 즉 중간 결과를 기억해 두었다가 재사용하는 것이라고 합니다. 이는 프로그래밍에서 매우 흔한 개념이며, 현대 프로그래밍 언어들은 — 특히 이를 지원하는 언어들은 — 보통 메모이제이션을 내장 최적화로 지원합니다.
예를 들어, Python에는 정확히 이 일을 하는 cache 데코레이터가 있습니다:
from functools import cache
@cache
def f(n):
if n == 0:
return 0
if n == 1:
return 1
return f(n - 2) + f(n - 1)
이때 이 데코레이터는 $n$에 대한 어떠한 제약도 알 필요가 없습니다. 튜플로서 해시 테이블에 넣을 수 있는 입력 및 출력 데이터라면 무엇이든 그 결과를 기억합니다.
이와 비슷한 것을 C++로 구현해 봅시다.
#복잡한 예제
«Игра финансистов» 문제를 살펴봅시다.
$n \le 4000$개의 수로 이루어진 배열 $a_i$가 있고, 두 플레이어가 번갈아 가며 이 배열에서 수를 가져가는데, 각자 자신의 합과 상대의 합의 차이를 최대화하려고 합니다. 매 턴마다 플레이어는 한쪽 끝에서 몇 개의 수를 가져갈 수 있습니다. 첫 번째 플레이어는 왼쪽에서, 두 번째 플레이어는 오른쪽에서 가져갑니다. 이때 플레이어가 이전 턴에 $k$개의 수를 가져갔다면, 그 상대는 다음 턴에 $k$개 또는 $(k + 1)$개의 수를 가져갈 수 있습니다(첫 턴에는 1개 또는 2개를 가져갈 수 있습니다).
게임은 플레이어가 수를 둘 수 없을 때 종료됩니다.
다음과 같은 DP를 도입합시다: $f[l, r, k, p] = $ 플레이어 $p$와 그 상대의 합의 차이 중 달성 가능한 최댓값입니다. 단, $l$번째부터 $r$번째까지의 원소만 남아 있고 직전 턴에 $k$개의 수를 가져간 경우입니다. 선택지는 $k$개 또는 $(k+1)$개의 수를 가져가는 두 가지뿐이므로, 전이는 단순히 이 두 가지 경우 중 최댓값입니다:
$$ f[l, r, k, 0] = \max \begin{cases} \sum_{i=l}^{k} a_i + f[l + k, r, k, 1] \\ \sum_{i=l}^{k + 1} a_i + f[l + k + 1, r, k + 1, 1] \end{cases} $$(다른 플레이어 $p=1$에 대해서도 마찬가지입니다.)
이것이 어느 정도의 시간에 동작하는지 추정해 봅시다. 재계산은 원래 배열에 대해 한 번 계산해 둔 누적 합을 이용하면 $O(1)$에 할 수 있으므로, 점근적 복잡도는 상태의 수와 같습니다. 그런데 여기서 문제가 생기는 것처럼 보입니다:
$$ l \in [1, n] \\ r \in [1, n] \\ k \in [1, n] \\ p \in \{ 0, 1 \} $$모든 상태를 순진하게 4차원 배열에 저장하면 $O(n^3)$개의 칸이 필요한데, $n=4000$이므로 이는 받아들일 수 없습니다. 그런데 도달 가능한 상태는 훨씬 적다는 것이 밝혀집니다.
명제 1. $k = O(\sqrt n)$입니다.
주어진 $k$를 얻으려면 이전의 어떤 단계들에서 $k, (k-1), \ldots, 2, 1$개의 수를 가져갔어야 하며, 이를 위해서는 배열의 크기 $n$이 적어도 다음 값 이상이어야 합니다.
$$ n \ge \sum_{i=1}^x i \approx \frac{k^2}{2} $$이로부터 $k = O(\sqrt n)$임을 알 수 있습니다.
명제 2. 주어진 왼쪽 경계 $l$에 대해 가능한 오른쪽 경계 $r$는 최대 $O(\sqrt n)$개 존재합니다.
첫 번째 플레이어와 두 번째 플레이어가 가져간 수의 개수의 차이 $d$를 생각해 봅시다:
$$ d = l - (n - r) $$한 플레이어가 몇 개의 원소를 가져가면 다른 플레이어는 그 뒤에 같은 개수를 가져가거나 하나 더 많이 가져가므로, 연속된 두 수마다 $d$는 최대 1만큼만 변합니다. 게다가 $d$가 1만큼 변하려면 $k$도 증가해야 합니다. 앞서 확인했듯이 $k = O(\sqrt n)$이므로 $d = O(\sqrt n)$이기도 합니다. 위 정의에서 $(l, d)$ 쌍으로부터 $r$을 복원할 수 있으므로, 각 $l$에 대해 서로 다른 $r$도 $O(\sqrt n)$개임을 얻습니다.
결국 실제로 도달 가능한 상태는 $O(n^3)$개가 아니라 $O(n \cdot \sqrt n \cdot \sqrt n \cdot 2) = O(n^2)$개입니다. 따라서 DP를 저장하는 더 영리한 형식과 더 영리한 순회 방법을 고안하거나, 메모이제이션을 적용할 수 있습니다.
4차원 배열을 그냥 만들면 메모리에 들어가지 않으므로(원소가 $O(n^{2.5})$개라 하더라도), 대신 해시 테이블을 사용합시다. 가장 간단한 방법은 해시 테이블을 int에서 int로 가는 unordered_map으로 정의하고, 튜플 $(l, r, k, p)$를 int에 들어가는 어떤 범위로 번호를 매기는 방법을 찾아, 4개의 수로 이루어진 튜플 대신 이 번호를 사용하는 것입니다.
const int N = 4000, K = 80;
int n;
int s[N + 1];
unordered_map<int, int> dp;
long f(int l, int r, int k, bool p) {
if ((r - l + 1) < k)
return 0;
int key = l * N * K * 2 + r * K * 2 + k * 2 + p;
if (dp.count(key))
return dp[key];
return dp[key] = (p ?
max(
s[l + k] - s[l] - f(l + k, r, k, 0),
s[l + k + 1] - s[l] - f(l + k + 1, r, k + 1, 0)
)
:
max(
s[r + 1] - s[r - k + 1] - f(l, r - k, k, 1),
s[r + 1] - s[r - k] - f(l, r - k - 1, k + 1, 1)
)
);
}
int main(){
dp.rehash(6.2e7);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s[i + 1];
s[i + 1] += s[i];
}
cout << f(0, n - 1, 1, 1);
return 0;
}
해시 테이블의 원소 개수를 미리 추정할 수 있다면, 처음부터 dp.rehash로 공간을 예약해 두는 것이 유리합니다. 이렇게 하면 보통 풀이가 23배 빨라집니다. 해시 테이블을 직접 작성하면 거기서 34배 더 빨라집니다.