[코딩테스트] 2. 메모이제이션

이전 편에서 재귀의 문제를 확인했다. 같은 값을 수십, 수억 번 반복 계산한다. 원인도 명확했다. 계산한 결과를 저장해두지 않는다는 것. 메모이제이션은 이 원인을 직접 제거한다.

이름의 의미

메모이제이션(Memoization)은 "메모(Memo)하다"에서 온 말이다. 메모라이제이션(Memorization, 암기)과 다르다. 계산 결과를 메모해두고, 나중에 같은 계산이 필요하면 메모를 꺼내 쓴다는 뜻이다.

Top-down DP라고도 부른다. 큰 문제에서 시작해서 필요한 하위 문제를 재귀로 내려가며 해결하기 때문이다. Bottom-up 방식(타뷸레이션)과 대비되는 접근이다.

저장 배열 추가

기존 재귀 코드에서 딱 한 가지만 바꾼다. 계산한 결과를 배열에 저장한다.

int[] memo = new int[101];
Arrays.fill(memo, -1);

int fib(int n) {
    if (n <= 2) return 1;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

재귀 코드와 비교하면 두 줄이 추가됐다.

• if (memo[n] != -1) return memo[n] : 이미 계산한 값이 있으면 바로 반환
• memo[n] = fib(n-1) + fib(n-2) : 결과를 저장하면서 반환

나머지는 원래 재귀 코드 그대로다. 구조는 바꾸지 않았다.

-1로 초기화하는 이유

Arrays.fill(memo, -1)은 "아직 계산하지 않은 상태"를 표현한다. 피보나치는 항상 양수를 반환하므로 -1이 나올 일이 없다. 그래서 -1을 미계산 표시로 쓸 수 있다.

memo[n] != -1이라는 조건은 두 가지를 동시에 검사한다. n의 계산이 끝났는가, 그리고 저장된 값이 있는가. 이 두 조건은 항상 같다.

어떻게 달라지는가

같은 fib(6) 호출인데 흐름이 완전히 바뀐다.

초록색 노드는 저장된 값을 바로 반환한 경우다. 새 계산이 전혀 일어나지 않는다.

이전 편에서 25번이었던 호출 횟수가 9번으로 줄었다. fib(4)는 처음 한 번만 실제로 계산되고, 이후에는 memo[4]를 그냥 반환한다.

실행 흐름을 따라가보면

fib(6) → fib(5) → fib(4) → fib(3) → fib(2) : 반환 1

이 경로에서 처음 fib(2)를 만나면 계산하고 memo[2] = 1로 저장한다. 이제 어떤 경로에서든 fib(2)를 호출하면 계산 없이 memo[2]를 반환한다.

fib(3) → fib(2) : 이미 memo[2]에 있으니 바로 반환

결국 각 fib(k)는 딱 한 번만 실제 계산된다. 나머지는 모두 저장값 반환이다.

시간복잡도

각 fib(k)가 딱 한 번만 계산된다. k는 1부터 N까지 N개다.

시간복잡도는 O(N)이다. O(2^N)에서 극적으로 개선됐다.

이전 편에서 N = 50이면 1조 번이라고 했다. 메모이제이션을 적용하면 50번이다. 실질적으로 제한이 없어진 것과 같다.

메모이제이션의 핵심 구조

메모이제이션 코드는 항상 같은 3단계 구조를 따른다. 이 틀을 익혀두면 어떤 문제에도 바로 적용할 수 있다.

int solve(int n) {
    if (n <= 기저_조건) return 기저값;
    if (memo[n] != -1) return memo[n];
    return memo[n] = 점화식;
}

1. base case : 더 이상 쪼갤 수 없는 최소 단위. 없으면 무한 재귀
2. 캐시 확인 : 이미 계산했으면 바로 반환
3. 계산 및 저장 : 처음 계산할 때만 이 줄이 실행됨

2차원 메모이제이션

상태가 두 변수에 의존하면 배열을 2차원으로 만든다. 예를 들어 dp[i][j]가 "위치 (i, j)에서의 최댓값"이라면 이렇게 된다.

int[][] memo = new int[N][M];
for (int[] row : memo) Arrays.fill(row, -1);

int solve(int i, int j) {
    if (i < 0 || j < 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    return memo[i][j] = Math.max(solve(i-1, j), solve(i, j-1)) + grid[i][j];
}

구조는 1차원과 동일하다. 저장 배열의 차원만 상태 변수의 수에 맞춰 늘린다.

자주 하는 실수

-1로 초기화하면 안 되는 경우

정답이 음수가 될 수 있는 문제라면 -1을 미계산 표시로 쓸 수 없다. memo[n] = -1이 "아직 계산 안 함"인지 "계산 결과가 -1"인지 구분이 안 된다.

이럴 때는 두 가지 선택지가 있다.

// 방법 1: Integer[] 사용 (null이 미계산 표시)
Integer[] memo = new Integer[101];

int fib(int n) {
    if (n <= 2) return 1;
    if (memo[n] != null) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// 방법 2: 별도 boolean 배열
int[] memo = new int[101];
boolean[] computed = new boolean[101];

int fib(int n) {
    if (n <= 2) return 1;
    if (computed[n]) return memo[n];
    computed[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Integer[]는 간결하지만 오토박싱 비용이 있다. 코딩테스트에서 N이 크다면 boolean[] 방법이 더 안전하다.

배열 크기 설정

memo[n]으로 n번째 값을 저장하려면 배열 크기가 n + 1 이상이어야 한다. 0-indexed가 아니라 1-indexed로 쓴다면 더욱 그렇다.

base case를 빠뜨리면

int fib(int n) {
    if (memo[n] != -1) return memo[n];       // base case 없이 바로 캐시 확인
    return memo[n] = fib(n - 1) + fib(n - 2);
}

base case 없이 캐시 확인부터 하면 fib(1), fib(2)도 재귀를 타고 내려간다. 결국 fib(0), fib(-1)... 음수 인덱스로 계속 내려가다 배열 접근 오류가 난다. 항상 base case를 먼저 처리하고 나서 캐시를 확인해야 한다.

메모이제이션의 한계

메모이제이션은 강력하지만 한계가 있다.

재귀 깊이가 그대로 유지된다. N이 크면 스택에 쌓이는 호출이 많아진다. Java의 기본 스택 크기는 수백 킬로바이트 수준이다. N = 10,000 정도면 스택 오버플로우가 날 수 있다.

이 문제를 완전히 해결하는 방법이 Bottom-up DP, 즉 타뷸레이션이다. 재귀를 쓰지 않고 반복문으로 작은 값부터 채워 올라간다. 다음 편에서 다룬다.

→ 다음 — 타뷸레이션

---