메모이제이션: Top-Down DP

"메모이제이션은 동적 계획법으로 들어가는 가장 부드러운 문이야. 당연한 재귀를 쓰고, 캐시를 더해. 지수 재앙이 선형 시간 해법으로 바뀌는 게 종종 딱 한 줄 변경이야."

재귀 더하기 캐시

메모이제이션은 top-down DP야. 문제를 그대로 비추는 자연스러운 재귀 해법을 쓰고, 각 부분 문제의 답을 처음 계산할 때 기억해 두는 캐시를 더해. 그러면 같은 부분 문제를 다시 만날 때마다 서브트리를 통째로 다시 계산하는 대신 즉시 조회로 끝나. top-down이라 부르는 이유는 큰 문제에서 출발해 base case 쪽으로 아래로 재귀해 내려가면서, 재귀가 풀려 올라올 때 결과를 캐시하기 때문이야. 아름다운 건 아무것도 재설계하지 않아도 된다는 점이야. 맞지만 느린 재귀를 가져다가, 기억하는 것만으로 빠르게 만들어.

캐시 키가 상태다

캐시는 부분 문제의 완전한 상태를 키로 잡아야 해. 함수 인자가 결과를 결정하는 불변 상태를 빠짐없이 담고 있고 함수가 외부의 가변 상태에 기대지 않는다면, 그 인자들이 좋은 캐시 키야. 상태 일부를 빼먹거나 가변 객체를 참조로 숨기면 같은 키가 서로 다른 답을 뜻하게 돼. @functools.cache는 해시 가능한 인자를 자동으로 캐시해 주지만, 순수성 계약까지 대신 증명해 주진 않아.

메모이제이션 = 자연스러운 재귀 + 부분 문제 상태(인자)를 키로 삼은 캐시. 큰 문제에서 시작해 아래로 재귀하고 가면서 캐시하는 top-down이야. Python에서는 @functools.cache가 맞는 재귀를 한 줄 만에 DP로 바꿔 줘. 실제로 닿는 부분 문제만 계산하는 지연 방식이고.

강점과 약점의 거래

메모이제이션의 강점은 두 가지야. 가장 쉬운 DP라는 것. 이미 믿는 재귀에 캐시만 얹으면 되니까. 그리고 지연(lazy)이라는 것. 질문에 답하는 데 실제로 필요한 부분 문제만 계산하니까, bottom-up 테이블이라면 채우느라 시간을 버렸을 닿지도 않는 상태들을 건너뛰어. 약점도 있어. 콜 스택을 타고 달리니 아주 깊은 상태 사슬은 재귀 한계에 부딪힐 수 있고(재귀 트랙의 경고 그대로), 캐시는 메모리와 조회 오버헤드를 조금 짊어져. 대부분의 문제에서 메모이제이션이 옳은 첫수야. bottom-up 테이블화는 깊이나 공간이 강제할 때 꺼내면 돼. 바로 다음에 다뤄.

피파의 고백

처음으로 'DP를 했'을 때, 난 모든 걸 낯선 테이블 채우기 모양으로 다시 써야 하는 줄 알았어. 아빠는 그냥 내 기존 재귀 함수 위에 @cache를 붙였고, 타임아웃 나던 게 즉답으로 바뀌었어. 살짝 속은 기분이었지. 이게 동적 계획법이라고? 근데 그게 top-down DP의 정직한 진실이야. 재귀가 맞으면 메모이제이션은 데코레이터 하나면 끝나는 일이 많아. 어려운 부분은 캐싱이 아니라 맞는 점화식을 쓰는 거였고, 난 그걸 이미 해 놨던 거야.

Code

동전 교환을 top-down 메모이제이션 DP로·python

from functools import cache

# 양의 정수 동전으로 amount를 만드는 최소 동전 수, top-down 메모이제이션.
# 상태 = 남은 금액. 그게 캐시 키.
def coin_change(coins, amount):
    @cache
    def fewest(remaining):                # 'remaining' 이 부분 문제 상태
        if remaining == 0:
            return 0                       # base case: 0 만드는 데 동전 0
        if remaining < 0:
            return float('inf')            # 넘침 — 불가능
        # 모든 동전 시도. 최선 (최소-동전) 옵션 + 이 동전 1
        return min(fewest(remaining - c) + 1 for c in coins)
    result = fewest(amount)
    return result if result != float('inf') else -1

print(coin_change([1, 3, 4], 6))   # 2  (3 + 3, 그리디의 4+1+1 = 3 동전 아니라)
# 참고: 그리디 '가장 큰 동전 잡기' 는 4+1+1 = 3 동전 — 틀려.
# DP 는 재귀에 걸쳐 fewest(remaining) 을 재사용: 같은 부분 문제가 반복,
# @cache 가 각각 한 번 계산. 맞는 재귀 + 데코레이터 하나 = top-down DP.

Exercise

재귀 함수 climb(n) = climb(n-1) + climb(n-2)는 한 번에 1계단 또는 2계단씩 올라 n계단을 오르는 방법 수를 세(base는 climb(0) = climb(1) = 1). 이대로면 지수야. 메모이제이션을 더하고 캐시 키가 뭔지 말해 봐. 캐싱이 왜 전체를 O(n)으로 무너뜨리는지, 각 부분 문제의 '상태'가 뭔지 설명해.

Hint

상태는 그냥 n(남은 계단 수)이고, 그래서 캐시 키도 n이야. @cache로 데코레이트하면 각 climb(k)는 한 번만 계산되고 반복 방문은 전부 O(1) 조회가 돼. 서로 다른 상태가 n개뿐이니 총 O(2ⁿ) 대신 O(n). 계단 옷을 입은 피보나치 패턴이지.

재귀 더하기 캐시

캐시 키가 상태다

강점과 약점의 거래

피파의 고백

Code

External links

Exercise

Progress

댓글 0