동적 계획법 DP 입문: 메모이제이션과 타뷸레이션 완벽 비교
알고리즘 학습의 가장 큰 고비이자, 마스터했을 때 가장 강력한 무기가 되는 것이 바로 동적 계획법(Dynamic Programming, DP)입니다. 복잡해 보이는 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 재활용하는 이 기법은 중복 계산을 획기적으로 줄여줍니다. 본 포스팅에서는 DP의 핵심 성립 조건부터 시작하여, 구현의 두 축인 하향식(Top-down)과 상향식(Bottom-up)의 논리적 차이를 2,500자 이상의 상세한 설명으로 풀어내겠습니다.
1. 동적 계획법(DP)이 성립하기 위한 두 가지 조건
모든 최적화 문제에 DP를 적용할 수 있는 것은 아닙니다. DP를 사용해 효율적인 해를 구하기 위해서는 반드시 다음의 두 가지 성질을 만족해야 합니다. 이를 파악하는 것이 알고리즘 설계의 첫 번째 단계입니다.
1-1. 최적 부분 구조 (Optimal Substructure)
큰 문제의 최적해를 작은 부분 문제의 최적해들로부터 구성할 수 있는 구조를 말합니다. 예를 들어, 서울에서 부산까지 가는 최단 경로는 서울에서 대구까지의 최단 경로와 대구에서 부산까지의 최단 경로의 합으로 이루어진다는 논리입니다.
1-2. 중복되는 부분 문제 (Overlapping Subproblems)
동일한 작은 문제들이 반복적으로 계산되는 경우를 의미합니다. 단순 재귀로 풀었을 때 같은 함수 호출이 수만 번 발생하는 구조라면, DP를 통해 이미 계산된 값을 저장함으로써 실행 시간을 극적으로 단축할 수 있습니다.
2. 하향식(Top-down)과 메모이제이션(Memoization)
하향식 접근법은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식입니다. 주로 재귀 함수를 사용하여 구현하며, 이때 한 번 계산한 결과를 리스트나 테이블에 저장해두는 기법을 메모이제이션(Memoization)이라고 합니다.
2-1. 메모이제이션의 장점과 한계
메모이제이션은 필요한 부분 문제만 계산한다는 'Lazy Evaluation'의 장점이 있어 직관적인 코드 작성이 가능합니다. 하지만 재귀 깊이가 너무 깊어지면 'Stack Overflow'가 발생할 수 있으므로, 언어적 제약이나 시스템 메모리 상황을 고려해야 합니다.
3. 상향식(Bottom-up)과 타뷸레이션(Tabulation)
상향식 접근법은 가장 작은 문제부터 차례대로 정답을 구해 나가며 테이블을 채워나가는 방식입니다. 반복문을 사용하여 구현하며, 이를 타뷸레이션(Tabulation)이라고 부릅니다. 아래에서부터 위로 차곡차곡 쌓아 올린다는 의미입니다.
3-1. 타뷸레이션의 효율성
재귀 호출의 오버헤드가 없기 때문에 실행 속도가 상대적으로 빠르고 안정적입니다. 또한 테이블의 모든 값을 채우기 때문에 모든 부분 문제의 해가 필요한 경우에 유리합니다. 실제 코딩 테스트나 성능이 중요한 실무 엔진에서는 상향식 방식을 더 선호하는 경향이 있습니다.
4. DP 문제 해결을 위한 4단계 전략
DP 문제를 마주했을 때 당황하지 않고 해결하기 위한 표준 프로세스는 다음과 같습니다.
- 해당 문제가 DP 조건(최적 부분 구조, 중복 문제)을 만족하는지 확인합니다.
- 문제의 상태를 정의합니다 (예:
dp[i]는 $i$번째까지의 최댓값). - 상태들 간의 관계를 나타내는 점화식을 세웁니다.
- 메모이제이션이나 타뷸레이션을 선택하여 코드로 구현합니다.
1. 철학: "이미 계산한 것은 다시 하지 않는다"는 효율성 중심의 설계 기법입니다.
2. 방법론: 재귀 기반의 메모이제이션(Top-down)과 반복문 기반의 타뷸레이션(Bottom-up)이 존재합니다.
3. 성공 열쇠: 문제의 규칙성을 찾아 올바른 점화식을 설계하는 능력이 가장 중요합니다.