동적 계획법 입문 — 메모이제이션과 점화식

재귀로 짠 피보나치 함수는 n이 40 정도만 돼도 눈에 띄게 느려진다. fib(40)을 부르면 그 안에서 fib(38)이 두 번, fib(37)이 세 번 계산되고, 아래로 내려갈수록 같은 계산이 기하급수로 불어난다. 동적 계획법(DP, Dynamic Programming)은 이 낭비를 없애는 기법이다. 한 번 구한 부분 문제의 답을 저장해 두고, 같은 문제를 다시 만나면 계산하는 대신 꺼내 쓴다.

DP가 성립하는 두 조건

모든 문제에 DP를 쓸 수 있는 건 아니다. 두 성질이 있어야 한다.

겹치는 부분 문제: 큰 문제를 쪼갰을 때 같은 부분 문제가 여러 번 등장한다. 피보나치가 정확히 이 경우다.
최적 부분 구조: 부분 문제의 답을 조합하면 전체 문제의 답이 된다. fib(n)은 fib(n-1)과 fib(n-2)의 답만 알면 되고, 그 답이 “어떤 경로로” 구해졌는지는 필요 없다.

둘 중 하나라도 없으면 저장할 가치가 없거나, 저장해도 조합이 안 된다.

메모이제이션 — 위에서 아래로

재귀 구조는 그대로 두고, 계산 결과를 담는 캐시만 얹는 방식이다. 큰 문제에서 출발해 필요한 부분 문제로 내려가므로 top-down이라 부른다.

memo = {}

def fib(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(40))  # 102334155

각 n은 처음 한 번만 계산되고 이후엔 딕셔너리 조회로 끝난다. 시간복잡도가 O(2^n)에서 O(n)으로 내려온다. 기존 재귀 코드에 몇 줄만 더하면 되는 것이 장점이고, 재귀 깊이 제한에 걸릴 수 있는 것이 약점이다.

타뷸레이션 — 아래에서 위로

반대로 가장 작은 문제부터 표(table)를 차례로 채워 올라가는 방식이다. 재귀가 없어 bottom-up이라 부른다.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib(40))  # 102334155

반복문뿐이라 재귀 깊이 걱정이 없고, 채우는 순서가 눈에 보여 디버깅이 쉽다. 대신 답에 필요 없는 칸까지 전부 채울 수 있다. 코딩테스트에서는 어느 쪽이든 통과하는 경우가 대부분이므로, 점화식이 자연스럽게 재귀로 떠오르면 메모이제이션, 순서대로 쌓는 그림이 그려지면 타뷸레이션을 쓰면 된다.

점화식 세우기 — 3단계

DP 문제 풀이의 실체는 코드가 아니라 점화식 세우기다. 계단 오르기 문제(한 번에 1칸 또는 2칸씩 올라 n번째 계단에 도달하는 방법의 수)로 순서를 밟아보자.

상태 정의: dp[i] = i번째 계단에 도달하는 방법의 수. “인덱스가 무엇을 뜻하는가”를 한 문장으로 말할 수 있어야 한다.
점화식: i번째 계단에 오는 직전 위치는 i-1 아니면 i-2뿐이다. 따라서 dp[i] = dp[i-1] + dp[i-2].
초기값: 점화식이 참조할 수 없는 맨 앞을 직접 채운다. dp[1] = 1, dp[2] = 2.

세 가지가 정해지면 코드는 위의 타뷸레이션 틀에 그대로 들어간다. 문제가 어려워질수록 달라지는 것은 이 틀이 아니라 상태의 차원(2차원 표, 상태 압축 등)이다.

DP 문제를 알아보는 신호

코딩테스트에서 DP인지 판별하는 단서는 대략 이렇다.

“경우의 수”, “최댓값/최솟값”, “가능한지 여부”를 묻는데, 모든 경우를 다 해보기엔 입력이 크다.
현재의 선택이 이후에 영향을 주지만, 과거의 구체적인 경로가 아니라 “지금 어떤 상태인가”만 중요하다.

이 두 신호가 보이면 완전 탐색 대신 상태 정의부터 시작해 보자. DP는 어려운 알고리즘이라기보다, 같은 계산을 두 번 하지 않겠다는 원칙을 표 하나로 구현한 것이다.