동적 계획법 (Dynamic Programming)
주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결방안을 바탕으로 주어진 문제를 해결하는 방법을 말한다. 이때, 소문제는 더 작은 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만, 입력의 크기가 작다는 특징을 지니고 있다.
피보나치 수열
피보나치는 1,1,2,3,4,8,...의 수를 이루게 되는데, 이런 피보나치 수열을 분해하여 트리 형태로 나타내게 되면 위와 같은 형태로 나타낼 수 있다. 즉, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 확인할 수 있는데 이때, 여러 개의 소문제로 분할하여 각 소문제의 해결방안을 바탕으로 주어진 문제를 해결하는 방법이라고 말할 수 있다.
int fibo(int n)
{
if (n<=2)
return 1;
else
return fibo(n-1) + fibo(n-2);
}다음은 피보나치 수열을 코드로 바꾼 것이다. 이 코드에는 문제점이 하나 발생하는데 소문제의 결과가 상위문제의 결과를 찾는데 사용됨으로 각각의 소문제는 중복적으로 발생한다는 문제점이 생긴다. 따라서 이는 자원낭비가 심하고, 시간도 더 많이 걸리게 되는 문제점이 발생한다. 그래서 동적 계획법(DP)은 소문제의 해를 따로 저장해놓고 이를 큰 문제를 푸는데 이용합니다. 중복 연산을 방지하는 데에는 두 가지 방법이 있다.
1. 메모이제이션(하향식) : TOP-DOWN
재귀함수로 구현하는 경우는 대부분 하향식이라 생각하면 되고, 큰 문제를 풀때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결해 나가면서 푸는 방식이다. 흔히 메모이제이션이라고 부른다.
int fiboData[100] = {0,};
int fibo(int n)
{
if (n<=2)
return 1;
if (fiboData[n]==0)
fiboData[n] = fibo(n-1) + fibo(n-2);
return fiboData[n];
}2. 타뷸레이션(상향식) : BOTTOM-UP
작은 문제부터 천천히 살펴본 다음에 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나가는 방식이다. 흔히 타뷸레이션이라고 부른다.
int fibo(int n)
{
fibodata[0] = 0;
fiboData[1] = 1;
for (int i=2; i<=n; i++)
fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
return fiboData[n];
}3. Top down과 Bottom up의 각 특징
Top down : 소스의 가독성이 증가되는 장점, 작성하기 어려운 단점
Bottom up: 풀기 쉬운 장점, 가독성이 저하되는 단점
정답은 없다.
분할 정복과 탐욕법과의 차이점
1. 분할 정복
분할 정복의 경우 작은 문제가 독립적이므로 큰 문제에 영향을 주지 않는다. 예를 들어 병합 정렬을 들 수 있는데, 분할한 원소들이 정렬되는 과정에서 다른 우너소에 영향을 주지 않는다. 그러나 동적 계획법은 작은 문제가 독립적이지 않고 큰 문제에 영향을 주는 특징이 있다. 위에 예시로 든 피보나치 수열을 보면 f(1), f(2) 값들이 계속 f(4), f(5), ...의 값에 영향을 주는 것을 볼 수 있다.
2. 탐욕법 (Greedy)
탐욕법의 경우 각 단계별로 현재 상태에서 가장 최적의 경우를 판단에서 결정하기 때문에 문제에 따라서는 판단된 결정이 최적해를 구하지 않는 경우도 존재한다. 하지만 동적 계획법의 경우는 모든 가능성을 고려하므로 어떤 문제든 항상 최적의 결과를 도출해낸다.
