Note
재귀 함수의 중복 계산을 제거하기 위한 메모이제이션 기법에 대해 알아봅니다.
문제 상황
재귀 함수를 사용할 때, 같은 입력에 대해 같은 계산을 여러 번 반복하는 경우가 있습니다.
예를 들어 복잡한 재귀 함수 w(a, b, c)가 있을 때:
w(15, 15, 15)를 계산하기 위해w(14, 15, 15)가 여러 번 호출됨- 같은 입력으로 함수가 반복 호출되면 시간이 기하급수적으로 증가
이런 문제를 해결하기 위해 **메모이제이션(Memoization)**을 사용할 수 있습니다.
메모이제이션이란?
**메모이제이션(Memoization)**은 함수의 결과를 저장해 두고, 같은 입력이 다시 들어오면 저장된 결과를 반환하는 최적화 기법입니다.
핵심 아이디어
- 결과 저장: 함수를 처음 호출할 때 결과를 딕셔너리나 배열에 저장
- 중복 체크: 함수 호출 시 이미 계산한 결과가 있는지 확인
- 재사용: 저장된 결과가 있으면 다시 계산하지 않고 반환
기본 구조
# 메모이제이션을 위한 딕셔너리
memo = {}
def function(x, y, z):
# 이미 계산한 결과가 있으면 반환
if (x, y, z) in memo:
return memo[(x, y, z)]
# 기저 조건
if base_condition(x, y, z):
result = base_value
else:
# 재귀 호출
result = function(x-1, y, z) + function(x, y-1, z) + ...
# 결과를 메모에 저장
memo[(x, y, z)] = result
return result메모이제이션의 장점
1. 시간 복잡도 개선
메모이제이션 없이:
- 시간 복잡도: O(지수 시간) 또는 O(매우 큰 수)
- 같은 계산을 반복하여 비효율적
메모이제이션 사용:
- 시간 복잡도: O(고유한 입력 조합의 수)
- 각 고유한 입력에 대해 한 번만 계산
2. 구현의 간편함
- 재귀 함수의 구조를 크게 바꾸지 않고 최적화 가능
- Top-Down 방식의 동적 프로그래밍 구현이 자연스러움
메모이제이션 vs 동적 프로그래밍
| 특징 | 메모이제이션 | 동적 프로그래밍 (Bottom-Up) |
|---|---|---|
| 접근 방식 | Top-Down (재귀) | Bottom-Up (반복문) |
| 계산 순서 | 필요할 때 계산 | 작은 문제부터 순차 계산 |
| 메모리 사용 | 필요한 것만 저장 | 모든 하위 문제 저장 |
| 구현 | 재귀 함수 + 딕셔너리 | 반복문 + 배열 |
활용 예시
메모이제이션은 다음과 같은 상황에서 유용합니다:
- 복잡한 재귀 함수 최적화
- 중복 계산이 많은 재귀 알고리즘
- 조건부 계산이 필요한 경우 (필요한 하위 문제만 계산)
- 다차원 DP 문제 (배열 인덱스가 복잡한 경우)
주의사항
1. 메모리 사용
메모이제이션은 계산 결과를 저장하므로 메모리를 사용합니다. 입력 공간이 매우 크면 메모리 부족이 발생할 수 있습니다.
2. 해시 가능한 키
딕셔너리를 사용할 때, 함수의 입력(키)은 해시 가능해야 합니다. 튜플, 정수, 문자열 등은 사용 가능하지만, 리스트는 직접 사용할 수 없습니다.
3. 부작용 없는 함수
메모이제이션은 함수가 **순수 함수(pure function)**일 때만 안전합니다. 즉, 같은 입력에 대해 항상 같은 출력을 반환해야 합니다.
관련 문제
- BOJ 9184: 신나는 함수 실행 - 메모이제이션을 활용한 재귀 함수 최적화 문제