동적계획법(DP) 개념 정리
동적계획법(DP, Dynamic Programming)은 같은 작은 문제가 반복해서 나올 때, 그 답을 저장해 한 번만 계산하는 기법이다.
DP를 사용할 수 있는 조건
| 알고리즘 | 작은 문제로 나누기 | 작은 문제 겹침 | 답 저장 |
|---|---|---|---|
| 완전탐색(재귀) | 가능 | 발생할 수 있음 | 보통 하지 않음 |
| 분할정복 | O | 보통 독립적 | 보통 필요 없음 |
| DP | O | O | O |
DP를 적용할 때 확인할 조건은 두 가지다.
- 겹치는 부분 문제: 같은 작은 문제가 반복해서 나타난다.
- 최적 부분 구조: 작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있다.
최댓값이나 최솟값을 구하는 문제뿐 아니라, 경우의 수를 세는 문제에도 작은 문제의 답을 조합하는 DP를 사용할 수 있다.
DP 풀이의 세 가지 요소
DP의 풀이는 상태 정의 → 점화식 → 초기 조건을 찾는 과정이다. 실제 구현은 재귀가 아닌 반복문으로도 할 수 있다.
| 단계 | 뜻 | 재귀 함수에서는 |
|---|---|---|
| 1. 상태 정의 | dp 한 칸의 의미 | 파라미터 + 반환값 |
| 2. 점화식 | 다른 상태의 답으로 현재 상태를 계산하는 규칙 | 더 작은 문제를 호출하고 결과를 조합하는 부분 |
| 3. 초기 조건 | 계산을 시작할 값 | 종료 조건 |
표기 관례: 대문자 DP는 알고리즘 기법인 동적계획법을, 소문자
dp는 계산한 답을 저장하는 배열을 가리키는 데 흔히 쓴다.
상태 정의
상태 정의는 dp의 한 칸에 무엇을 적을지 정하는 일이다. 이걸 잘 정해야 앞의 칸들로 다음 칸을 계산하는 규칙, 즉 점화식을 세울 수 있다. 세 단계 중 가장 어렵지만, 상태만 잘 정하면 점화식과 초기 조건은 대부분 따라 나온다.
칸을 정할 때는 재귀 함수로 생각하면 쉽다. 함수에 넣는 값이 dp의 칸 번호가 되고, 함수의 결과는 그 칸에 적어 둔다. 그래서 f(i)의 결과는 dp[i]에, f(i, j)의 결과는 dp[i][j]에 들어간다.
코드 구현
- 메모이제이션(Top-Down): 재귀로 필요한 상태를 계산하고 답을 저장한다.
- 타뷸레이션(Bottom-Up): 반복문으로 의존하는 상태부터 순서대로 채운다.
// 메모이제이션 (memo는 -1로 초기화)
int f(int n) {
if (n <= 2) return n; // 초기 조건
if (memo[n] != -1) return memo[n]; // 저장된 답 재사용
memo[n] = f(n - 1) + f(n - 2); // 점화식
return memo[n];
}
// 타뷸레이션
dp[1] = 1;
dp[2] = 2; // 초기 조건
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2]; // 점화식
시간복잡도는 같다. 타뷸레이션은 재귀 호출 비용이 없어 조금 더 빠르다.
← Back