[Python 실전] 딕셔너리로 코드 속도 10배 올리기: 메모이제이션(Memoization)

1. 메모이제이션(Memoization)이란?

컴퓨터 프로그래밍에서 메모이제이션은 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 딕셔너리 같은 저장 공간에 '메모'해 두었다가 다시 사용하는 기술입니다.
복잡한 연산을 매번 처음부터 다시 하지 않고, "아! 이거 아까 계산해둔 건데?" 하고 딕셔너리에서 바로 꺼내 쓰기 때문에 속도가 획기적으로 빨라집니다.

---

2. 왜 딕셔너리를 사용하나요?

메모이제이션의 핵심은 검색 속도입니다. 파이썬의 딕셔너리(Dictionary)는 내부적으로 해시 테이블(Hash Table) 구조를 사용하기 때문에, 데이터가 아무리 많아도 내가 원하는 값을 찾는 속도가 거의 일정하고 매우 빠릅니다. (시간 복잡도 $O(1)$)

---

3. 실전 예제: 피보나치 수열 (Fibonacci)

피보나치 수열은 재귀 함수로 구현할 때 중복 계산이 가장 많이 발생하는 대표적인 알고리즘입니다.

❌ 일반 재귀 방식 (매우 느림)

n=40만 되어도 연산 횟수가 수억 번에 달해 컴퓨터가 버벅이기 시작합니다.

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

✅ 딕셔너리 메모이제이션 방식 (매우 빠름)

한 번 구한 값은 memo 딕셔너리에 저장하므로, 동일한 계산은 단 한 번만 수행됩니다.

# 결과를 저장할 캐시 딕셔너리
memo = {}

def fib_memo(n):
    # 1. 이미 메모에 적혀있다면 바로 반환
    if n in memo:
        return memo[n]

    # 2. 기본 조건 처리
    if n <= 1:
        return n

    # 3. 계산 후 결과를 메모에 저장
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

print(fib_memo(100)) # 354224848179261915075 (0.001초 만에 결과 출력)

---

4. 고수들의 한 줄 팁:

사실 파이썬에서는 딕셔너리를 직접 만들지 않아도 이 기능을 사용할 수 있습니다. functools 라이브러리의 @lru_cache 데코레이터를 함수 위에 붙여주기만 하면 됩니다.

from functools import lru_cache

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

---

📝 핵심 요약

1. 중복 연산 제거: 똑같은 입력값에 대해 반복 계산이 일어난다면 메모이제이션을 고려하세요.
2. 딕셔너리 활용: Key는 입력값, Value는 결과값으로 저장하여 캐시로 활용합니다.
3. 효과: 연산량이 기하급수적으로 줄어들어 프로그램의 성능이 극대화됩니다.