메모이제이션: 재귀 결과 캐싱
@functools.lru_cache와 수동 메모 딕셔너리를 피보나치와 climbing-stairs에 적용해 지수적으로 반복되는 계산을 제거합니다.
메모이제이션: 재귀 결과 캐싱은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
중복 재귀의 문제
순진한 재귀 피보나치는 같은 값을 반복해서 계산합니다. fib(5)는 fib(4)와 fib(3)을 호출하고, fib(4)는 fib(3)과 fib(2)를 호출하므로 fib(3)이 두 번 계산됩니다. 이러한 중복은 지수적으로 증가하여 fib(40)은 10억 회가 넘는 함수 호출을 수행합니다. 메모이제이션은 각 결과를 처음 계산할 때 저장하여 이 문제를 해결합니다. 이후 호출에서는 다시 계산하지 않고 O(1)에 저장된 결과를 가져옵니다.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40딕셔너리를 사용한 수동 메모이제이션
memo 딕셔너리를 매개변수로 추가하거나 클로저로 만드세요. 계산하기 전에 답이 이미 메모에 있는지 확인합니다. 있다면 즉시 반환하고, 없다면 계산한 후 메모에 저장하고 반환합니다. 이제 각 고유 하위 문제는 정확히 한 번만 계산되므로, memo 딕셔너리에 O(n)의 공간과 O(n)의 스택 공간을 사용하면서 시간 복잡도를 O(2^n)에서 O(n)으로 줄일 수 있습니다.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!functools.lru_cache 데코레이터
Python은 메모이제이션을 자동화하는 @functools.lru_cache(maxsize=None)을 제공합니다. Python 3.9 이상에서는 @functools.cache로도 사용할 수 있습니다. 함수 위에 이 데코레이터를 추가하면 인수를 기준으로 모든 호출이 캐시됩니다. maxsize=None은 캐시 크기에 제한이 없다는 뜻이므로, 각 고유 인수 조합이 모두 캐시됩니다. 이렇게 하면 코드 한 줄만으로 모든 재귀 함수를 메모이제이션된 버전으로 바꿀 수 있습니다.
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)계단 오르기 (LeetCode 70)
LeetCode 70의 '계단 오르기' 문제에서는 한 번에 1계단 또는 2계단을 오를 수 있습니다. n번째 계단에 도달하는 방법은 몇 가지일까요? 이 문제는 사실 피보나치와 같습니다. ways(n) = ways(n-1) + ways(n-2)입니다. 기저 사례는 ways(0) = 1(지상에 그대로 있는 방법 한 가지)과 ways(1) = 1입니다. 메모이제이션을 사용하면 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21동전 교환 (LeetCode 322)
LeetCode 322의 '동전 교환' 문제에서는 동전의 액면가와 목표 금액이 주어졌을 때 필요한 동전의 최소 개수를 구합니다. 하향식 메모이제이션 재귀에서는 각 유효한 동전에 대해 dp(amount) = 1 + min(dp(amount - coin))을 계산합니다. 기저 사례는 dp(0) = 0입니다. 각 부분 금액을 캐시하고, 만들 수 없는 부분 금액이면 무한대를 반환합니다. 메모이제이션을 사용하면 지수 시간의 완전 탐색을 O(amount × len(coins)) 시간으로 줄일 수 있습니다.
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1메모이제이션을 사용한 단어 분할 (LeetCode 139)
LeetCode 139의 '단어 분할' 문제에서는 문자열을 사전의 단어들로 나눌 수 있는지 판단합니다. 하향식 재귀에서는 can_break(s, start)가 모든 접두사 s[start:end]를 시도합니다. 해당 접두사가 사전에 있고 can_break(s, end)가 참이면 참을 반환합니다. 메모이제이션이 없으면 시간 복잡도는 O(2^n)이지만, 각 시작 인덱스를 캐시하는 메모이제이션을 사용하면 L이 최대 단어 길이일 때 O(n² × L)이 됩니다.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # False메모이제이션과 테이블화
메모이제이션(하향식)은 원래 문제에서 시작하여 재귀적으로 발견하는 답을 캐시합니다. 따라서 실제로 필요한 하위 문제만 해결합니다. 테이블화(상향식)는 작은 하위 문제부터 큰 하위 문제까지 테이블을 미리 채우므로, 필요한지 여부와 관계없이 모든 하위 문제를 해결합니다. 메모이제이션은 재귀 해법에서 도출하기 쉽고, 테이블화는 재귀 깊이 제한과 함수 호출 비용을 피할 수 있습니다.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(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_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limit공간 최적화: 누적 변수
메모이제이션을 적용한 재귀 방식이 O(n)의 공간을 사용하는 많은 DP 문제는, 이전 하위 문제의 답 중 고정된 개수만 필요하다면 O(1)의 공간으로 더 최적화할 수 있습니다. 피보나치에서는 마지막 두 값만 중요하고, 계단 오르기에서도 마찬가지입니다. 두 개의 누적 변수를 사용하면 전체 메모 딕셔너리나 테이블을 대체할 수 있습니다.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache와 클로저, 전역 딕셔너리
메모이제이션을 직접 구현하는 방법은 세 가지입니다. 전역 딕셔너리는 간단하지만 모듈 범위를 오염시킵니다. 클로저는 캐시를 함수 내부에 캡슐화하여 외부로 새는 것을 막지만 감싸는 함수가 필요합니다. @lru_cache는 모든 반복 코드를 데코레이터 하나로 대체하므로 가장 깔끔합니다. 면접에서는 면접관이 수동 구현을 특별히 요구하지 않는 한 @lru_cache로 시작하세요.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040메모이제이션이 도움이 되지 않는 경우
메모이제이션은 겹치는 하위 문제, 즉 같은 하위 문제가 여러 번 계산되는 경우에만 문제를 빠르게 만듭니다. 단순한 트리 순회처럼 각 노드를 정확히 한 번씩 방문하여 모든 하위 문제가 고유하다면 메모이제이션은 이점 없이 비용만 추가합니다. 또한 재귀 트리의 지수적 증가가 문제의 재사용이 아니라 서로 다른 하위 문제의 수에 따른 것이라면 메모이제이션으로 해결할 수 없습니다. 이런 경우에는 전혀 다른 알고리즘이 필요합니다.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')요약: 메모이제이션 점검 목록
다음과 같은 경우 메모이제이션을 적용하세요. 중복 계산 때문에 느리지만 올바른 재귀 해법이 있고, 함수의 서로 다른 인수 조합 수가 적으며, 반환값이 인수에만 의존하는 경우입니다. 즉 부수 효과나 전역 상태가 없는 순수 함수여야 합니다. 하위 문제의 상태 공간을 확인하세요. 서로 다른 상태가 O(n)개 또는 O(n²)개 이하라면 메모이제이션을 통해 지수 시간을 다항 시간으로 바꿀 수 있습니다.
간단 확인
이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.
수업 복습
이 수업에서는 다음을 배웠습니다. 메모이제이션은 하위 문제의 결과를 저장하여 중복 계산을 피하고, 지수 시간의 재귀를 다항 시간으로 바꿉니다. 또한 @functools.lru_cache는 코드 한 줄만으로 사용할 수 있는 Python의 관용적 도구입니다. 그리고 메모이제이션(하향식)과 테이블화(상향식)는 DP의 두 가지 방식이며, 메모이제이션은 도출하기 쉽고 테이블화는 스택 깊이 문제를 피합니다. 축하합니다. 재귀 및 해시 맵 모듈을 모두 마쳤습니다!
AI 튜터와 함께 Coding Interview Prep을(를) 배우세요 — 무료
브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.
- 코스
- 90
- 레슨
- 360
자주 묻는 질문
“메모이제이션: 재귀 결과 캐싱” 강의는 무료인가요?
네 — “메모이제이션: 재귀 결과 캐싱” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“메모이제이션: 재귀 결과 캐싱”에서 뭘 배우나요?
@functools.lru_cache와 수동 메모 딕셔너리를 피보나치와 climbing-stairs에 적용해 지수적으로 반복되는 계산을 제거합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“메모이제이션: 재귀 결과 캐싱” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 재귀 프레임워크: 기본 사례, 신뢰, 구성
- 호출 스택 시각화
- 재귀와 반복의 트레이드오프
- 메모이제이션: 재귀 결과 캐싱