[코딩테스트] 3. 타뷸레이션

메모이제이션은 재귀 기반이라 스택 오버플로우 위험이 있다. 작은 문제부터 순서대로 채워 올라가면 재귀 없이도 같은 결과를 낼 수 있다. 이 방식이 Bottom-up DP, 타뷸레이션이다.

발상의 전환

메모이제이션은 큰 문제(fib(n))에서 시작해서 필요한 작은 문제를 재귀로 찾아 내려간다. 반대로 생각하면 어떨까.

fib(1), fib(2)는 바로 알 수 있다. 이걸 이용해서 fib(3)을 구할 수 있다. fib(3)이 있으면 fib(4)를 구할 수 있다. 이런 식으로 작은 것부터 차례로 채우면 재귀 없이 fib(n)에 도달한다.

구현

int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}

재귀가 전혀 없다. 배열을 앞에서부터 채울 뿐이다.

dp[i]를 계산할 때 dp[i-1]과 dp[i-2]는 이미 채워진 상태이므로, 그냥 더하면 된다.

아래는 n=6일 때 배열이 채워지는 과정이다.

초기: [_, 1, 1, _, _, _, _]
i=3: [_, 1, 1, 2, _, _, _]   dp[3] = dp[2] + dp[1] = 2
i=4: [_, 1, 1, 2, 3, _, _]   dp[4] = dp[3] + dp[2] = 3
i=5: [_, 1, 1, 2, 3, 5, _]   dp[5] = dp[4] + dp[3] = 5
i=6: [_, 1, 1, 2, 3, 5, 8]   dp[6] = dp[5] + dp[4] = 8

메모이제이션 vs 타뷸레이션

같은 문제를 푸는 두 가지 방식이다. 어떤 차이가 있는지 비교해보자.

• 접근 방향 : 메모이제이션은 큰 문제 → 작은 문제 (Top-down), 타뷸레이션은 작은 문제 → 큰 문제 (Bottom-up)
• 구현 방식 : 메모이제이션은 재귀 + 저장, 타뷸레이션은 반복문
• 스택 오버플로우 : 메모이제이션은 가능성 있음, 타뷸레이션은 없음
• 불필요한 계산 : 메모이제이션은 필요한 것만 계산, 타뷸레이션은 전부 계산

코딩테스트에서는 타뷸레이션이 표준이다. 재귀 오버헤드가 없고 최적화하기 쉽다.

공간 최적화

타뷸레이션의 장점 중 하나는 공간 최적화가 쉽다는 점이다. 피보나치처럼 dp[i]가 직전 두 값만 사용한다면, 배열 전체를 저장할 필요가 없다.

int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
}

O(N) 공간을 O(1)로 줄였다. 모든 문제에 적용 가능하지는 않지만, 가능한 경우 시도해볼 만하다.

다음 시리즈에서는 새로운 문제를 보고 DP를 어떻게 설계하는지 배운다.

→ 다음 시리즈 : DP 설계 전략

---