동적 계획법(DP)을 구현하는 두 가지 주요 방식
- 반복적(Iterative) DP (상향식, Bottom-up)
- 재귀 + 메모이제이션(Recursive + Memoization) (하향식 + Top-down)
1. Iterative DP (상향식, Bottom-up)
- 방향: 작은 문제부터 시작하여 점차 큰 문제의 해를 계산
- 구현: 주로 반복문(예:
for루프)을 사용하여 구현 - 저장: 결과를 저장할 배열(DP 테이블)을 정의하고, 순서대로 채움
- 호출 스택: 재귀 호출이 없어 오버헤드가 적고, 보통 속도가 빠르며 스택 오버플로우 위험이 없음
- 직관성: 점화식을 찾으면 배열을 채우는 순서가 명확하여 이해하기 쉬움
2. Recursive + Memo (하향식, Top-down)
- 방향: 가장 큰 문제에서 시작하여 재귀 호출을 통해 필요한 작은 문제를 호출하고 그 결과를 합침
- 구현: 재귀 함수를 사용하여 구현, 이전에 계산한 결과를 저장하기 위한 메모(Memo) 기능을 추가
- 저장: 함수 호출 시 가장 먼저 메모를 확인하여 이미 계산된 값이라면 바로 반환하고, 아니면 계산 후 메모에 저장
- 호출 스택: 재귀 호출에 따른 스택 오버헤드가 발생할 수 있으며, 문제가 클 경우 스택 오버플로우의 위험이 있음
- 직관성: 문제의 점화식(재귀 관계)을 그대로 코드로 옮기기 때문에 구현이 더 직관적일 수 있음. 또한, 실제로 필요한 부분 문제만 계산
주요 비교 요약
| 특징 | Iterative DP | Recursive + Memo |
|---|---|---|
| 계산 방향 | 상향식 (작은 것 → 큰 것) | 하향식 (큰 것 → 작은 것) |
| 구현 방식 | 반복문 (Iterative) | 재귀 함수 (Recursive) |
| 오버헤드 | 적음 (스택 오버플로우 위험 거의 없음) | 재귀 호출로 인한 스택 오버헤드 발생 가능 |
| 계산 범위 | 일반적으로 모든 부분 문제를 계산 | 필요한 부분 문제만 계산 |
| 직관성 | 배열 채우는 순서가 명확 | 점화식과 구조가 유사해 구현이 직관적일 수 있음 |
- 일반적으로 성능 면에서는 Iterative DP가 유리하지만, 복잡한 문제에서는 Recursive + Memo가 점화식을 코드로 바로 옮기기 쉬워 구현이 더 편리할 때도 있다.
