메모이제이션: Top-Down DP

"메모이제이션은 동적 계획법으로 가는 제일 부드러운 길이야: 당연한 재귀를 쓰고, 캐시를 더해. 종종 지수 재앙을 선형 시간 해법으로 바꾸는 한 줄 변경이야."

재귀 더하기 캐시

메모이제이션은 top-down DP 야: 문제를 직접 거울처럼 비추는 자연스러운 재귀 해법을 쓰고, 각 부분 문제 답을 처음 계산할 때 기억하는 캐시를 더해. 같은 부분 문제에 대한 나중 모든 요청이 다시 계산된 서브트리 대신 즉시 조회. top-down 이라 불리는 건 큰 문제에서 시작해 base case 쪽으로 아래로 재귀하며, 재귀가 풀릴 때 결과를 캐시하니까. 아름다움: 아무것도 재설계 안 해도 돼 — 맞지만 느린 재귀를 가져다 기억으로 빠르게 만들어.

캐시 키가 상태다

못 박을 개념 하나: 캐시는 부분 문제의 상태로 키 매겨져 — 편리하게도, 정확히 함수의 인자야. fib(7) 의 상태는 7; edit_distance(i, j) 의 상태는 쌍 (i, j). 같은 인자의 두 호출은 같은 부분 문제고 같은 답을 반환해야 해, 그래서 인자가 완벽한 캐시 키. Python 에선 거의 공짜야: 함수를 @functools.cache (또는 @lru_cache) 로 데코레이트하면 인자로 키 매겨져 캐싱이 자동으로 일어나. 맞는 재귀가 말 그대로 한 줄로 top-down DP 가 돼.

메모이제이션 = 자연스러운 재귀 + 부분 문제 상태 (인자) 로 키 매긴 캐시. top-down (크게 시작, 아래로 재귀, 가면서 캐시). Python 에선 @functools.cache 가 맞는 재귀를 한 줄로 DP 로 바꿔. 실제 닿는 부분 문제만 계산 (지연).

거래

메모이제이션의 강점: 가장 쉬운 DP 라 쓰기 (이미 믿는 재귀를 캐시할 뿐), 그리고 지연 (lazy) — 네 쿼리에 답하는 데 실제 필요한 부분 문제만 계산해, bottom-up 테이블이 채우느라 시간 낭비할 닿을 수 없는 상태를 건너뛰어. 약점: 콜 스택을 타, 그래서 아주 깊은 상태 사슬이 재귀 한계를 칠 수 있고 (재귀-트랙 주의), 캐시가 메모리랑 조회 오버헤드를 좀 져. 대부분 문제엔, 메모이제이션이 맞는 첫 수 — bottom-up 테이블 (다음 lesson) 은 깊이나 공간이 강제할 때만 손대.

피파의 고백

처음 '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