Memoization메모이제이션

# 일반 재귀: O(2ⁿ) — 지수 시간
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# 메모이제이션: O(n) — 각 n을 한 번만 계산
cache = {}
def fib_memo(n):
    if n in cache: return cache[n]
    if n <= 1: return n
    cache[n] = fib_memo(n-1) + fib_memo(n-2)
    return cache[n]

# Python lru_cache 활용
from functools import lru_cache

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