Ch.10 다이나믹 프로그래밍

Top-Down Memoization — 재귀 + 캐싱

메모이제이션의 원리를 재귀 트리로 설명한다functools.lru_cache와 딕셔너리 memo를 사용하여 DP를 구현한다메모이제이션의 시간·공간 복잡도를 분석한다

재귀는 그대로, 속도만 바꾼다

피보나치 재귀 함수에 딱 한 줄을 추가하면 O(2^n)이 O(n)으로 변합니다. 비결은 '이미 계산한 값을 기억하는 것'입니다.

어떻게 코드 한 줄로 지수 시간을 선형 시간으로 바꿀 수 있을까?

메모이제이션(Memoization) — 함수 호출 결과를 캐싱하여 같은 입력이 들어오면 즉시 반환합니다.

lightbulb

핵심 개념

메모이제이션

함수 호출 결과를 딕셔너리에 저장하여 재사용하는 기법

lru_cache

Python 내장 데코레이터로 자동 메모이제이션을 제공

article

핵심 내용

가장 직관적인 방법: 딕셔너리에 결과를 저장합니다

def fib(n, memo={}):
    if n in memo:
        return memo[n]       # 캐시 히트!
    if n <= 1:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(40))  # 102334155 — 즉시 반환!

memo 딕셔너리가 이미 계산한 값을 기억합니다. fib(38)이 두 번째 호출되면 즉시 반환!

fib(5)를 메모이제이션으로 한 줄씩 추적합니다

순수 재귀는 15번 호출, 메모이제이션은 9번으로 줄었습니다

Python은 메모이제이션을 내장 데코레이터로 제공합니다

from functools import lru_cache

@lru_cache(maxsize=None)  # 무제한 캐시
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))  # 354224848179261915075 — 즉시!

lru_cache 장점: • 코드 한 줄 추가로 메모이제이션 완성 • 원래 함수 시그니처 변경 불필요 • cache_info()로 히트율 확인 가능 주의사항: • 인자가 해시 가능(hashable)해야 함 • 리스트 인자 → tuple로 변환 필요 • 재귀 깊이 제한: sys.setrecursionlimit()

import sys
sys.setrecursionlimit(10000)  # 재귀 깊이 늘리기

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

print(fib(1000))  # 매우 큰 수도 즉시!
print(fib.cache_info())  # 캐시 통계 확인

메모이제이션을 적용하면 복잡도가 어떻게 변할까요?

피보나치 복잡도 비교: 순수 재귀: 시간 O(2^n), 공간 O(n) — 콜스택 메모이제이션: 시간 O(n), 공간 O(n) — memo + 콜스택 핵심 공식: 시간 = (고유 부분문제 수) × (부분문제당 계산 시간) = n × O(1) = O(n)

메모이제이션은 시간을 공간으로 교환하는 기법입니다. 지수 시간 → 다항 시간!

실전에서 자주 쓰이는 메모이제이션 패턴을 정리합니다

# 패턴 1: 2D 메모이제이션
@lru_cache(maxsize=None)
def grid(i, j):
    if i == 0 or j == 0: return 1
    return grid(i-1, j) + grid(i, j-1)

# 패턴 2: 문자열 → tuple 변환
def solve(items):
    @lru_cache(maxsize=None)
    def dp(idx, remaining):
        if idx == len(items): return 0
        ...
    return dp(0, tuple(items))

면접에서 Top-Down을 언제 선택해야 할까요?

Top-Down 장점: • 재귀적 사고가 직관적 • 필요한 부분문제만 계산 (lazy evaluation) • 점화식을 그대로 코드로 옮김 Top-Down 단점: • 재귀 깊이 제한 (Python: ~1000) • 함수 호출 오버헤드 • 스택 오버플로 위험

면접에서는 Top-Down으로 먼저 풀고, 면접관이 최적화를 요구하면 Bottom-Up으로 전환하는 전략이 좋습니다

메모이제이션을 적용한 피보나치의 시간 복잡도는?

lru_cache는 리스트(list)를 인자로 받을 수 있다

메모이제이션 마스터!

key

핵심 용어

📝

메모이제이션

함수 결과를 딕셔너리에 저장·재사용

🐍

lru_cache

Python 내장 자동 메모이제이션 데코레이터

edit_note

정리 노트

Top-Down Memoization — 재귀 + 캐싱

구현 방법

딕셔너리 memo: memo = {} → if n in memo: return memo[n]
lru_cache: @lru_cache(maxsize=None) 데코레이터 한 줄

복잡도

시간: (고유 부분문제 수) × (부분문제당 시간)
공간: memo 딕셔너리 + 재귀 콜스택

★

면접에서는 lru_cache보다 딕셔너리 memo를 직접 구현하는 게 실력을 보여줍니다!

check_circle

핵심 정리

1메모이제이션 = 재귀 + 결과 캐싱
2lru_cache 데코레이터로 한 줄 구현
3O(2^n) → O(n)으로 극적 최적화

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작