동적프로그래밍이란 동적계획법이라고도 부르는데 문제를 풀기위해 필요한 알고리즘이라기보다 문제를 푸는 방식을 말한다.
처음 알고리즘 공부할때 동적프로그래밍이 무엇인지 개념 잡기가 어려웠다.
개념 잡기가 어려웠던 이유는 아마 동적프로그래밍(dynamic programming ) 이름 자체의 모호함 때문이 아니였다 생각든다.
아직도 왜 동적프로그래밍이라고 부르는지 잘 모르겠지만 동적프로그래밍이 무엇인지 이해만 하면 된다.
개념 부터 설명하면 동적프로그래밍이란 ?
풀기가 복잡한 문제(complex problem)가 있다.
이 문제를 자세히 뜯어보니 큰 문제를 작은(하위) 문제(subproblems) 들로 나눌 수 있을거 같고 하위 문제들의 결과(답)를 이용하여 큰 문제를 풀려고 하는 방식이다.
복잡한 문제를 하위 문제들의 답을 이용하여 푼다고 하였는데 동적프로그래밍은 이 하위 문제들의 답을 자주 사용하게 되고 자주 사용되는 하위 문제의 답을 미리 저장해 놨다가 다음에 동일한 하위 문제가 나오면 이전에 구해놨던 답을 다시 사용하여 중복된 계산을 하지 않게 하여 계산 시간이 줄어들어 들게 되는 장점이 있다.
따라서 동적프로그래밍은 아래와 같은 특성이 있다.
- 복잡한 문제(complex problem)를 작은 문제(subproblems)로 나눈다.
- 작은 문제의 해는 복잡한 문제를 풀기위한 부분 해가 된다.
- 복잡한 문제를 풀기위한 작은 문제들은 자주 등장하기 때문에 작은 문제가 나타날때 마다 계산할 필요 없이 해를 저장해놨다가 동일한 문제가 나오면 재 활용하여 시간을 절약한다.
그럼 어떤 알고리즘 문제가 나왔을때 이것을 재귀(recursion)로 풀어야할지, 분할 & 정복(divide & conquer)으로 풀어야할지, 그리디 알고리즘(greey algorithm)으로 풀어야할지 아니면 동적프로그래밍으로 풀어야할지 감이 잡혀야 하는데 동적프로그래밍으로 풀어야하는 문제는 다음과 같은 2가지 특성을 가진다.
- Overlapping Subproblems
- Optimal Substructure
Overlapping Subproblems
분할 & 정복(Divide and Conquer) 처럼 동적프로그래밍(Dynamic Programming)은 하위 문제에 대한 솔루션을 사용(결합, 조합)하는데 동적 프로그래밍은 주로 동일한 하위 문제의 솔루션이 반복(again and again)해서 필요할 때 사용한다.
동적 프로그래밍에서 하위 문제가 이미 계산 되었다면 다시 계산할 필요가 없도록 테이블(ex. 룩업테이블)에 저장했다가 나중에 다시 사용한다고 하였다. 따라서 동적 프로그래밍은 공통적인 (겹치는) 하위 문제가 없다면 동적프로그래밍으로 풀면 안된다.
왜냐하면 솔루션이 다시 필요하지 않은데 솔루션을 저장하는 것은 이점이 없기 때문이다.
예를 들어 이진 검색(binary search)에는 공통의 하위 문제가 전혀 없다.
하지만 (재귀)피보나치 수열(Fibonacci Sequence)를 예를 들어보자.
반복적이고 중복되는 하위 문제가 많이 있는 것을 알 수 있다.
피보나치를 재귀적으로 알고리즘을 작성하면 다음과 같다.
|
1
2
3
4
5
|
int fib(int n) {
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
|
fib(5)를 구한다면 재귀적인 실행 트리(execution tree)는 그림1과 같을 것이다.
가만 보면 fib(5)를 구하기위해 많은 하위 문제들로 나눌수 있고 그 하위문제들중 중복되는 문제들이 있는 것을 알수있다.
예를들어 fib(5) 를 구하기위해 재귀에서 fib(3) 의 해가 2번 필요했고 fib(2) 가 3번 필요하다.
만약 여기서 fib(3) 이나 fib(2)를 값을 저장했다면 다시 계산하지 않고 이전에 저장된 값을 다시 사용할 수 있게 된다.
동적 프로그래밍에서는 다음 두 가지 방법으로 하위문제들(subproblem)의 해를 저장해 놨다가 다시 재활용하게 되는데 바로
Memoization 과 Tabulation이다.
- Memoization (Top Down)
- Tabulation (Bottom Up)
Memoization는 메모이제이션 또는 탑다운 방식이라고 얘기하기도 하고 Tabulation는 테뷸레이션 또는 바텀업 방식이라고도 한다.
동적프로그래밍에서 하위문제들의 해를 저장하기위해 보통 탑다운 방식보다 바텀업을 사용하는데 먼저 탑다운 방식을 먼저 살펴보자.
Memoization (Top Down)
위키백과를 보면 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 메모아이제이션이라고도 한다. 라고 나와있다.
여기까지는 사실 bottom up 방식도 동일하기 때문에 차이가 없다. 단, bottom up 방식과 차이점은 하위 문제에 대한 해결책이 필요할 때마다 먼저 조회 테이블(해를 저장한 테이블)을 조사하고 사전 계산 된 값이 있으면 그 값을 반환하고 그렇지 않으면 값을 계산하고 결과를 나중에 다시 사용할 수 있도록 조회 테이블에 저장하기 때문에 룩업테이블의 모든 엔트리에 값을 저장하지 않는다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Fibonacci {
final int MAX = 100;
final int NIL = -1;
int lookup[] = new int[MAX]; // 조회테이블
void initialize() {
for (int i = 0; i < MAX; i++)
lookup[i] = NIL;
}
int fib(int n) {
// 해당 n 엔트리에 값이 없다면 계산하여 저장한다.
if (lookup[n] == NIL) {
if (n <= 1) {
lookup[n] = n;
}
else {
lookup[n] = fib(n-1) + fib(n-2);
}
}
// 미리 계산되것이 있다면 그 값을 리턴한다.
return lookup[n];
}
}
Colored by Color Scripter
|
Tabulation (Bottom Up)
bottom up 방식은 메모이제이션과 다르게 하위 문제의 모든 해를 조회 테이블의 모든 엔트리에 저장하게 된다.
메모이제이션에서는 하위문제의 수요에 따라 계산되어 저장된다면 테뷸레이션에서는 첫 번째 항목부터 시작하여 모든 항목이 하나씩 지는 것이다.다음 코드를 보면 모든 f[n]을 계산하는것 같지만 자세히 보면 f[n]을 계산하기위해 이전에 미리 계산한 값 (f[0], f[1])을 사용하기 때문에 계산에 필요한 오버헤드가 전혀 없다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class Fibonacci {
int fib(int n) {
// f[0], f[1] 부터 f[n]까지 모든 하위문제를 차례차례 게산하여 복잡한 문제의 해로 사용한다.
int f[] = new int[n+1];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
public static void main(String[] args)
{
Fibonacci f = new Fibonacci();
int n = 9;
System.out.println("Fibonacci number is" + " " + f.fib(n));
}
}
Colored by Color Scripter
|
동적프로그래밍에서 어떤 방식으로 미리 계산된 값을 저장해 놓을지는 상황에 따라 선택하면된다.
피보나치 수열 f(40) 을 구하기위한 방식으로 재귀와 탑다운, 바텀업 방식으로 풀었을때 실행 시간은 아래와 같았다
재귀 : Time Taken 0.708307
탑다운 : Time Taken 0.000062
바텀업 : Time Taken 0.000077
확실히 재귀보다 계산시간이 현저히 줄어 드는 것을 알수 있다.
메모이제이션과 테뷸레이션둘다 순환식의 값을 계산하는 기법들이 둘 다 동적계획법의 일종으로 보기도 하는데 차이점은
메모이제이션은 top-down방식이며, 실제로 필요한 subproblem만을 푸는 반면 테뷸레이션은 bottom-up 방식이며, recursion에 수반되는 overhead가 없다.
Optimal Substructure
두번째 특성은 optimal substructure 이다.
최적 하부 구조란 ? 컴퓨터 과학에서, 문제의 최적 해가 그 하위 문제의 최적 해로부터 얻을 수 있다면 최적 하부 구조를 갖는다 고 말한다.
이 속성은 문제에 대한 동적 프로그래밍 및 욕심 알고리즘의 유용성을 결정하는 데 사용되는데 예를 들어, 최단 경로 문제(shortest path problem)는 다음과 같은 최적 하부 구조 속성가진다. 노드 x가 소스 노드 u에서 목적지 노드 v까지의 최단 경로에 놓이는 경우 u에서 v까지의 최단 경로는 u에서 x까지의 최단 경로와 x에서 v까지의 최단 경로의 조합이 된다.
Floyd-Warshall 및 Bellman-Ford 와 같은 최단경로 알고리즘이 동적 프로그래밍의 전형적인 예이다.
개념을 알았으니 이제 아래와 같은 동적프로그래밍 문제(Dynamic Programming Problem) 들을 살펴보면서 감을 익히도록하자.
- longest Common Subsequence.
- Shortest Common Supersequence.
- Longest Increasing Subsequence problem.
- The Levenshtein distance (Edit distance) problem.
- Matrix Chain Multiplication.
- 0–1 Knapsack problem.
- Partition problem.
- Rod Cutting.
레퍼런스
'알고리즘(Algorithm) > 동적프로그래밍(Dynamic Programming)' 카테고리의 다른 글
| 동적 프로그래밍 basic 문제-이항계수(Binomial Coefficient) - DP1 (0) | 2019.08.07 |
|---|---|
| 동적 프로그래밍 문제를 해결하는 방법? (0) | 2019.08.05 |
