Memoization (메모화)

✅ Memoization:

함수가 한 번 계산한 결과를 저장해두고, 같은 입력이 들어오면 저장된 결과를 바로 사용하는 기법입니다.

이렇게 하면 이미 계산한 값을 재계산하지 않아도 되므로 시간 복잡도를 크게 줄일 수 있습니다.

 

---

 

Memoization을 사용하는 이유

 

중복 계산 방지:

피보나치 수열처럼 같은 부분 문제를 여러 번 계산해야 하는 경우에 유용합니다.

Memoization을 쓰면 한 번 계산한 결과를 저장해 놓기 때문에, 동일한 입력이 다시 들어올 때 이미 계산해 둔 값을 그대로 돌려줄 수 있습니다. 그 결과 같은 입력에 대해 중복으로 계산할 필요가 없어 실행 시간을 크게 줄일 수 있습니다.

 

시간 복잡도 감소:

단순 재귀로 피보나치를 구하면 지수 시간(O(2^n))이 걸리지만, Memoization을 적용하면 선형 시간(O(n))에 해결 가능합니다.

 

코드 가독성 유지:

재귀 함수를 그대로 사용하면서 계산 결과만 저장하므로, 작성 및 이해가 쉽습니다.

 

---

 

Memoization 을 사용하지 않는 단순 재귀 (시간 많이 걸림)

 

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

 

Memoization을 적용한 버전

memo = {}  # 딕셔너리로 계산 결과를 저장

def fib_memo(n):
    if n <= 1:
        return n
    
    if n not in memo:       # memo에 n의 결과가 없으면 계산
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    
    return memo[n]          # 이미 있으면 저장된 결과 리턴


# 사용 예시
print(fib_memo(10))  # 이때부터 fib(10)을 빠르게 구할 수 있음
print(fib_memo(20))  # 이미 하위 계산이 저장되었으므로 더 빨라짐