배경
재귀적 해법: 관계중심으로 파악해서 문제를 간명하게 볼 수 있지만, 심한 중복 호출이 일어나는 경우가 있다. (ex. 피보나치수를 구하는 재귀 알고리즘, 행렬 곱셈 최적순서 구하기)
-> 피보나치 알고리즘의 경우, Divid & Conquer(D&Q) 알고리즘 방법으로 설게하면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되어 효율적이지 않다.
이 해결책이 동적 프로그래밍이다.
동적 프로그래밍(Dynamic Programming)
먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결한다. => 최종적으로 원래 주어진 입력의 문제를 해결
-> Bottom-up algorithm (D&Q는 top-down)
- 잘못된 결정/수정을 하지 않음
- 딱 한번만 결정
동적 프로그래밍 알고리즘 예시: 피보나치(sudo 코드)
fibonacci(n)
{
f[0] = 0; f[1] = 1;
for(i = 2; i <= n; i++)
f[i] = f[i-1]+f[i-2];
return f[n];
}-> 선형시간에 끝난다.
Principle of Optimality (최적성의 원칙)
동적 프로그래밍을 적용하려면 최적성 원칙(principle of optimality) 또는 최적 부분구조(optimal substructure) 특성을 가지고 있어야만 함
=> 큰 문제의 최적 해에 작은 문제의 최적 해가 포함됨
Shortest Path 문제
방법 1) 무작적 알고리즘(brute-force algorithm)
한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소 길이를 찾는다.
절대적으로 비효율적임
방법 2) Dynamic Programming
자료구조: 그래프의 인접행렬식 표현
D(k)[i][j]: 정점들 {v1, v2, ... , vk}을 통해서, 정점 i에서 정점 j로 가는 최단경로의 길이
동적계획 알고리즘으로 모든 쌍의 최단 경로 문제를 해결하려면 먼저 부분 문제들을 찾아야 함
step 1: D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])
-> 'vi에서 vj로 가는 최단 경로가 vk를 거치지 않는 경우'와 'vk를 거치는 경우'로 나눈다.
step 2: 상향식으로 k=1부터 n까지 반복하여 해를 구한다.
시간복잡도: O(n^3)
Floyd-Warshall algorithm
void floyd(int n, const number W[][], number D[][]){
int i, j, k;
D = W;
for(k = 1; k <= n; k++)
for(i = 1, i <= n; i++)
for(j = 1; j <= n; j++)
D[i][j] = minimum(D[i][j], D[i][k] + D[k][j]);
// 계속 노드와 노드사이를 갈 때, 다른 노드를 거치는 것과 거치지 않는 것으로 구분
}Dynamic Programming 방법에 의한 설계 절차
- 문제의 입력에 대해서 최적(Optimal)의 해답을 주는 재귀 관계식(Recursive property)을 설정
- 상향적으로 최적의 해답을 계산
- 상향적으로 최적의 해답을 구축
Greedy 방법과 Dynamic Programming 방법의 비교
| Greedy 방법 | Dynamic Programming 방법 |
|---|---|
| 최적화 문제를 푸는데 적합 | 최적화 문제를 푸는 데 적합 |
| 알고리즘이 존재할 경우 보통 더 효율적 | 때로는 불필요하게 복잡 |
| 알고리즘이 최적인지 증명해야 함 | 최적화 원칙이 적용되는지를 점검해 보기만 하면 됨 |
| 단일 출발점 최단경로 문제: O(n^2) | 단일 출발점 최단경로 문제 : O(n^2) |
Knapsack Problem (배낭문제)
-problem-
S = {아이템1, 아이템2,...}
wi = 아이템i의 무게
pi = 아이템i의 가치(이윤)
W = 배낭에 넣을 수 있는 총 무게라고 할 때,
배낭에 들어간 총 무게 <= W를 만족하면서, 배낭에 들어간 총 이윤이 최대가 되도록 하는 답을 찾는 문제
방법 1) 무작정 알고리즘
n개의 물건에 대해서 모든 부분집합을 다 고려한다.
크기가 n인 집합의 부분집합의 수는 2^n개이다.
방법 2) Greedy 알고리즘
1) 가장 비싼 물건부터 우선적으로 채운다 : 최적 보장 안됨
2) 무게 당 가치(이윤)이 가장 높은 물건부터 우선적으로 채운다 : 최적 보장 안됨
<복습> The Fractional Knapsack Problem
- 물건의 일부분을 잘라서 담을 수 있다.
- Greedy 방법으로 최적해를 구하는 알고리즘 존재
방법 3) Dynamic Programming 방법
- 전체 무게가 W가 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고의 이익을 P[i][w]고 하면,
P[i][w] =
maximum(P[i-1][w], pi + P[i-1][w-wi]) -> if wi <= W
P[i-1][w] -> if wi > W
P[i-1][w] : i번째 항목을 포함시키지 않는 경우의 최고 이익
pi + P[i-1][w-wi] : i번째 항목을 포함시키는 경우의 최고 이익
물건의 개수 n과 배낭의 총 무게 W는 아무런 상관관계가 없다. 따라서, 만일 W = n!이라면 수행시간은 O(n*n!)이 된다. => 무작정 알고리즘보다도 나을 게 없다.
착안점
P[n][W]를 계산하기 위해서 (n-1)번째 행을 모두 계산할 필요가 없다!
즉, P[n-1][W]와 P[n-1][W-w] 두 항만 계산하면 됨
개선된 알고리즘의 최악의 경우 수행시간 : O(minimum(2^n, nW))
