Dynamic Programming (DP, 동적 계획법)
1. 정의
Dynamic Programming(DP)은
복잡한 문제를 작은 부분 문제로 나누고,
그 부분 문제들의 해답을 저장(memoization)하여 재활용함으로써
중복 계산을 제거하고 문제를 효율적으로 해결하는 알고리즘 설계 기법이다.
즉,
“큰 문제 = 작은 문제들의 해답 조합”이라는 구조를 가진 문제에 적용하는 방식이다.
2. 핵심 아이디어
| 개념 | 설명 |
|---|---|
| 중복 부분 문제(Overlapping Subproblems) | 동일한 부분 문제가 반복적으로 등장한다. |
| 최적 부분 구조(Optimal Substructure) | 큰 문제의 최적해가 작은 문제의 최적해로부터 구성된다. |
| 메모이제이션 또는 테이블링 | 계산한 값을 저장해두고 다시 필요할 때 그대로 사용한다. |
DP는 불필요한 중복 계산을 제거하는 것이 목적이다.
3. 작동 원리
DP는 방법에 따라 두 가지 방식이 있다.
(1) Top-Down (Memoization 방식)
- 큰 문제를 해결하려고 재귀를 호출하면
필요한 작은 문제를 먼저 해결하고 그 결과를 저장한다. - 이미 계산한 값을 다시 요청하면 저장된 값을 즉시 반환한다.
(2) Bottom-Up (Tabulation 방식)
- 가장 작은 부분 문제부터 차례대로 해결하며
테이블(dp 배열)을 채워 나간다. - 반복문을 사용하며, 큰 문제로 확장해 나간다.
두 방식의 결과는 동일하며, 구현 방식만 다르다.
4. 대표 예시
1) 피보나치 수열
피보나치 수는 다음 점화식을 가진다.
F(n) = F(n-1) + F(n-2)재귀로 풀 경우 중복 계산이 폭발적으로 발생한다.
따라서 DP에서는 다음과 같이 하기 쉽다.
Bottom-Up 예:
dp[0] = 0
dp[1] = 1
for i = 2 to n:
dp[i] = dp[i-1] + dp[i-2]이를 통해 O(n) 시간에 해결할 수 있다.
2) 배낭 문제(Knapsack Problem)
대표적인 DP 문제.
- 물건 i의 무게 w[i], 가치 v[i]
- 배낭의 허용 무게는 K
점화식:
dp[i][w] = i번째 물건까지 고려했을 때, 무게 w에서의 최대 가치
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])즉,
- 물건을 안 담는 경우
- 물건을 담는 경우
중 더 좋은 값을 선택한다.
5. DP의 구성 요소
DP 설계를 위해 다음 네 가지 요소를 명확히 정해야 한다.
-
상태 정의 (State Definition)
dp[i] 또는 dp[i][j]가 무엇을 의미하는지 정의. -
점화식 (Recurrence Relation)
작은 문제에서 큰 문제로 확장하는 규칙. -
초기값(Base Case)
가장 작은 문제에서의 값. -
계산 순서 (Order of Computation)
점화식이 의존하는 방향에 맞게 테이블을 채우는 순서 결정.
6. 시간/공간 복잡도 특징
| 방식 | 특징 |
|---|---|
| Top-Down | 필요한 문제만 계산하므로 불필요한 계산이 줄어듦. |
| Bottom-Up | 순차적으로 계산되므로 반복문 형태로 빠르고 안정적. |
| 공간 복잡도 | dp 배열 크기에 비례. 일부 문제는 1차원 또는 2차원으로 표현. |
많은 DP 문제는 O(n) 또는 O(nk) 정도의 시간·공간 복잡도를 가진다.
7. 장단점
| 항목 | 설명 |
|---|---|
| 장점 | 중복 계산 제거로 효율적이고 안정적이다. |
| 단점 | 문제 설계를 위한 점화식 이해가 어려울 수 있다. |
| 주의 | 단순한 재귀를 DP로 바꾸면 성능이 크게 향상된다. |
8. 예시 의사코드 (Bottom-Up)
dp[0] = base_value
for i = 1 to n:
dp[i] = f(dp[i-1], dp[i-2], ...)
return dp[n]문제에 따라 dp의 차원, 점화식은 달라진다.
9. DP 문제를 해결하는 사고 과정
- 문제를 작은 단위로 쪼갤 수 있는가?
- 동일한 작은 문제가 반복되는가?
- 큰 문제는 작은 문제의 해로부터 결정되는가?
- dp 배열의 구조는 어떻게 만들 것인가?
- 점화식을 어떻게 표현할 것인가?
- 어떤 순서로 테이블을 채울 것인가?
이 순서를 따르면 대부분의 DP 문제를 해결할 수 있다.
10. 한 문장 요약
Dynamic Programming은
작은 문제의 해답을 저장해 두고 재활용함으로써
복잡한 문제를 효율적으로 해결하는 알고리즘 기법이다.
