[Algorithm] Dynamic Programming

동적 프로그래밍

'하나의 문제는 한 번만 풀도록 하는 알고리즘'

분할 정복 기법의 단점을 보완하는 알고리즘이다. 그 단점이라 하면, 동일한 문제를 다시 푼다는 것. 예를 들어 피보나치 수열 문제에서 답을 구하기 위해서는 매 항이 바로 앞의 두 항을 필요로 한다. 이를 분할 정복 기법으로 풀 경우 같은 값을 반복적으로 다시 계산해 구해야 하기 때문에 비효율 적이다. 따라서 이럴 때 동적 프로그래밍 기법이 사용되어야 한다.

그림에서 볼 수 있듯 분할 정복 기법을 이용패 피보나치 문제를 해결하려고 하면 12번째 수를 세번이나 계산하게 된다. 이 때의 시간 복잡도는 O(2^n)으로 구하려는 수가 커지면 비용이 기하급수적으로 증가한다. 이럴 때 바로 동적 프로그래밍 기법을 사용해야 하는 것이다.

다음과 같은 가정하에 사용할 수 있다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

이 과정에서 Memoization(메모이제이션)이 사용된다는 점이 분할 정복법과 다른 점이다.
계산한 값을 저장하는 과정이다. DP를 사용하게 되면 이미 계산되어있는 연산은 안해도 되기 때문에 트리의 깊이 만큼만 계산이 이루어져 시간 복잡도는 O(n)이 나온다. 분할 정복 기법에 비해 엄청나게 감소한 것이다.

방식은 top-down과 down-top 이 있다. 자신에게 잘 맞는 방식으로 문제를 풀면된다. 둘 중 하나의 방식으로만 풀리는 문제도 있다고는 하는데 난 아직 본 적 없다.

코딩테스트에서 매우 자주 등장하므로 꼭 풀 줄 알아야 한다!

예제 ) 백준 1463 - 1로 만들기 (https://www.acmicpc.net/problem/1463)

#include <iostream> using namespace std; //DP(Dynamic Programming)  //10^6까지의 숫자를 테스트 한다  int memo[1000001]={0,}; int find(int num){     //down-top       for(int i=2;i<=num;i++){         //1을 뺐을 때의 경우를 먼저 저장          memo[i] = memo[i-1]+1;         //2와 3으로 나누어 떨어질 때 비교하여 작은 것 선택          if(i%2==0)              if(memo[i] > memo[i/2])                  memo[i]=memo[i/2]+1;         if(i%3==0)             if(memo[i]>memo[i/3])                  memo[i] = memo[i/3]+1;     }     return memo[num]; } int main(){     int num;     cin>>num;     cout<<find(num);      } Colored by Color Scripter

cs