다이나믹 프로그래밍(DP)의 기초와 핵심 전략
다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)이란? 큰 문제를 작은 문제로 나누어 푸는 하향식/상향식 알고리즘 설계 기법입니다. 핵심은 **"한 번 계산한 작은 문제의 정답을 메모리에 저장(재활용)하여, 다시는 똑같은 계산을 하지 않도록 만드는 것"**입니다. (속도 향상의 치트키!)
1. DP를 사용할 수 있는 2가지 조건
모든 문제에 DP를 적용할 수 있는 것은 아닙니다. 아래 두 가지 조건을 모두 만족할 때 DP를 사용할 수 있습니다.
- 최적 부분 구조 (Optimal Substructure)
- 큰 문제의 최적해(정답)가 작은 문제들의 최적해들로 구성될 수 있는 구조를 말합니다.
- 중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제들이 반복해서 나타나는 구조여야 합니다. 이 반복되는 계산을 저장해 두는 것이 DP의 핵심입니다.
2. DP의 핵심 접근 방식 2가지
DP를 구현하는 방법은 크게 두 가지로 나뉩니다. 두 방식의 차이를 이해하는 것이 중요합니다.
📌 Top-Down (하향식) - 메모이제이션(Memoization)
- 방식: 큰 문제를 해결하기 위해 위에서부터 아래로 내려가며, 재귀(Recursion) 함수를 호출하는 방식입니다.
- 핵심: 이미 계산한 값을 배열이나 객체에 저장(Memo)해 두었다가, 필요할 때 꺼내 씁니다.
📌 Bottom-Up (상향식) - 타뷸레이션(Tabulation) (★ 추천)
- 방식: 가장 작은 기본 문제부터 차례대로 정답을 구해 나가며 테이블을 채우는(Tabulation) 방식입니다.
- 핵심: 반복문(Loop)을 사용하며, 직관적이고 재귀 호출로 인한 스택 오버플로우 위험이 없어 실무 및 코딩 테스트에서 더 선호됩니다.
3. 핵심 문제 풀이: 피보나치 수열
DP를 이해하는 가장 좋은 예제인 피보나치 수열을 두 가지 방식으로 구현해 봅니다.
피보나치 점화식: ```text F(n) = F(n-1) + F(n-2)```
⭕ Top-Down (재귀 + 메모이제이션)
TYPESCRIPT
class TopDownFibonacci {
// 계산된 결과를 저장할 메모리 공간 (객체 또는 배열)
private memo: Record<number, number> = {};
public getFib(n: number): number {
// 기저 조건 (Base Case)
if (n === 1 || n === 2) return 1;
// 이미 계산한 적이 있다면 저장된 값을 즉시 반환 (재활용)
if (this.memo[n] !== undefined) {
return this.memo[n];
}
// 계산 후 메모에 저장
this.memo[n] = this.getFib(n - 1) + this.getFib(n - 2);
return this.memo[n];
}
}
const tdFib = new TopDownFibonacci();
console.log(tdFib.getFib(50)); // 메모이제이션 덕분에 순식간에 계산 완료!
⭕ Bottom-Up (반복문 + 타뷸레이션)
TYPESCRIPT
function bottomUpFibonacci(n: number): number {
if (n === 1 || n === 2) return 1;
// 데이터를 저장할 DP 테이블 초기화
const dp: number[] = new Array(n + 1).fill(0);
// 초기 조건 설정
dp[1] = 1;
dp[2] = 1;
// 작은 문제부터 차례대로 계산하며 테이블 채우기
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(bottomUpFibonacci(50)); // 반복문 기반이라 스택 오버플로우 염려 없음
4. DP 문제 풀이 3단계 전략
실전 문제를 만났을 때 당황하지 않고 DP로 접근하는 프로토콜입니다.
- DP 문제인지 의심하기
- 문제가 그리디나 완전 탐색(DFS/BFS)으로 풀기에는 시간 초과가 날 것 같고, 대규모 데이터의 최적값을 요구할 때 의심하세요.
- "이전의 선택이 다음 선택에 영향을 주는가?"를 체크합니다.
- 점화식 세우기 (가장 중요)
- 문제를 쪼개서 상태를 나타낼 변수를 정하고, 이 변수들 간의 관계를 식으로 표현해야 합니다.
- 예:
dp[i] = i번째 계단에 오를 때의 최댓값
- 가장 작은 문제(초기값) 정의하기
dp[0],dp[1]등 가장 직관적으로 알 수 있는 기저 조건의 값을 명시하고 반복문을 돌립니다.
5. 요약
| 비교 항목 | Top-Down (메모이제이션) | Bottom-Up (타뷸레이션) |
| 주요 도구 | 재귀 함수 (Recursion) | 반복문 (For loop) |
| 가독성 | 점화식 형태를 그대로 코드로 옮기기 쉬움 | 흐름을 한눈에 파악하려면 숙련도가 필요함 |
| 장점 | 꼭 필요한 서브 문제만 계산함 (Lazy-evaluation) | 스택 오버플로우가 없고 속도가 상대적으로 빠름 |
| 단점 | 재귀 깊이가 깊어지면 에러 발생 위험 있음 | 필요 없는 하위 문제까지 전부 계산될 수 있음 |
6. 마치며 느낀 점
- 무차별 대입(Brute Force)에서 탈출하기 그동안 코딩 테스트 문제를 풀 때 시간 초과가 나면 막막하기만 했는데, DP를 배우고 나니 "컴퓨터의 메모리를 활용해 시간을 번다"는 개념이 정립되었습니다. 기억력이 나쁜 프로그램에게 기록을 쥐여주는 것만으로 연산 속도가 기하급수적으로 빨라지는 게 흥미로웠습니다.
