0Pricing
DSA Interview Prep · 강의

메모이제이션: 재귀 결과 캐싱

@functools.lru_cache와 수동 메모 딕셔너리를 피보나치와 climbing-stairs에 적용해 지수적으로 반복되는 계산을 제거합니다.

메모이제이션: 재귀 결과 캐싱은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA 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))  # 89

lru_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의 두 가지 방식이며, 메모이제이션은 도출하기 쉽고 테이블화는 스택 깊이 문제를 피합니다. 축하합니다. 재귀 및 해시 맵 모듈을 모두 마쳤습니다!

자주 묻는 질문

“메모이제이션: 재귀 결과 캐싱” 강의는 무료인가요?

네 — “메모이제이션: 재귀 결과 캐싱” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“메모이제이션: 재귀 결과 캐싱”에서 뭘 배우나요?

@functools.lru_cache와 수동 메모 딕셔너리를 피보나치와 climbing-stairs에 적용해 지수적으로 반복되는 계산을 제거합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“메모이제이션: 재귀 결과 캐싱” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 재귀 프레임워크: 기본 사례, 신뢰, 구성
  2. 호출 스택 시각화
  3. 재귀와 반복의 트레이드오프
  4. 메모이제이션: 재귀 결과 캐싱
← DSA Interview Prep(으)로 돌아가기