메모이제이션은 계산 결과가 될 수 없는 값으로 해야 합니다.

 

 

재귀로 작성한 다이나믹 프로그래밍에서 한 번 계산한 결과를 기록해 두고 같은 상태에 재방문했을 때 재계산을 하지 않고 기록해 둔 값을 바로 반환하는 메모이제이션은 필수적인 기법 중 하나입니다. 여기에서 중요한 것은 코드가 이미 계산했던 결과인지 여부를 판단할 수 있어야 한다는 것입니다. 이 말만 들으면 별로 특별할 것이 없어 보이는데, 실제로 재귀 DP에서 이 부분은 매우 자주 실수하고 시간 초과를 받게 되는 원인입니다.

 

예를 들어 11048 - 이동하기 문제에서 다음과 같은 코드를 작성할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1005][1005];
int dp[1005][1005];

int f(int r, int c)
{
    int &ret = dp[r][c];
    if (ret != 0)
        return ret;
    ret = a[r][c];
    if (r < n)
        ret = max(ret, a[r][c] + f(r + 1, c));
    if (c < m)
        ret = max(ret, a[r][c] + f(r, c + 1));
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    cout << f(1, 1) << '\n';
}

 

얼핏 보기에는 단순히 각 $(r, c)$ 칸에서 아래 칸인 $(r+1, c)$로 갈 수 있으면 가보고, 오른쪽 칸인 $(r, c+1)$로 갈 수 있으면 가본 뒤 더 값이 큰 것을 메모이제이션 하여 반환하는 정상적인 코드로 보입니다. 하지만 이 코드를 실제로 제출해 보면, 빠르게 잘 가다가 90% 정도에서 갑자기 올라가기를 멈추더니 시간 초과를 받게 되는 것을 볼 수 있습니다.

 

이 코드의 문제점은 dp 배열이 0으로 초기화 된 상태에서, 메모이제이션 된 dp값이 이미 전에 계산된 값인지 여부를 그 값이 0이 아닌지 여부로 판단하고 있다는 점입니다. 왜 이것이 문제가 될까요? 그것은 바로 이미 계산하여 메모이제이션 된 값 그 자체가 0이 될 수도 있다는 점을 간과했기 때문입니다.

 

문제의 조건을 잘 보면 다음과 같은 문구가 있습니다.

사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

 

예제에서도 드러나지만 사탕의 개수는 0개가 될 수 있습니다. 그렇다면 모든 칸의 사탕이 0개라면 어떻게 될까요? 어떤 칸에서부터 시작하더라도 끝까지 도달하여 얻을 수 있는 사탕의 최대 개수 또한 0개일 것입니다. 즉, 모든 $r$, $c$에 대해 $dp[r][c]=0$이 됩니다.

 

재귀 DP에서 이미 계산한 상태를 재계산하는 것의 폐해는 단순히 한 번 계산할 것을 두 번 세 번 계산하는 것에 그치지 않습니다. 이는 최악의 경우 모든 가능한 경로를 브루트포스로 탐색하는 것이나 다를 것이 없고, DP를 하는 의미 자체가 없어지게 만듭니다. 다시 말해 탐색 횟수는 상태의 개수가 많아질수록 그 개수에 대한 지수꼴로 증가합니다. 비슷한 경우로 BFS를 할 때에는 큐에 넣을 때 방문 표시를 해야 합니다. 와 같은 경우도 있습니다.

 

따라서 이 코드를 올바르게 고치기 위해서는 $dp$ 배열의 초깃값을 계산 결과로 나올 수 없는 값으로 설정하고, 이미 계산한 결과인지 여부를 이 값을 기준으로 판단해주면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1005][1005];
int dp[1005][1005];

int f(int r, int c)
{
    int &ret = dp[r][c];
    if (ret != -1)
        return ret;
    ret = a[r][c];
    if (r < n)
        ret = max(ret, a[r][c] + f(r + 1, c));
    if (c < m)
        ret = max(ret, a[r][c] + f(r, c + 1));
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j], dp[i][j] = -1;
    cout << f(1, 1) << '\n';
}

 

처음 코드와 비교했을 때 $dp[i][j]$들을 -1로 초기화하는 부분이 추가되었고, 메모이제이션 여부를 확인할 때 $0$ 대신 $-1$이 기준이 된 것을 볼 수 있습니다. 이 코드는 문제없이 잘 통과됩니다.

 

사소한 팁으로, $-1$로 초기화하는 것의 경우 다소 편법이지만 거의 모든 채점 시스템에서 다음과 같은 문장으로도 배열 전체를 $-1$로 초기화하는 효과를 볼 수 있습니다. $0$과 $-1$ 외에는 동작하지 않는 방법이니 주의해야 합니다.

memset(dp, -1, sizeof dp);