Dynamic Programming

Dynamic Programming : 작은 문제의 답을 조합해서 큰 문제의 답을 푸는 과정이다.

 

DaC(Divide and Conquer) 과 DP(Dynamic Programming)은 비슷하지만 다음의 차이점이 존재한다.

 

DaC

1. 문제가 절반으로 줄어든다.

2. Function Problem

3. 결과가 한번 사용된다.

4. 분할이 성능을 향상 시킨다. 

 

DP

1. 문제가 -1로 줄어든다. 

2. 최적화 문제

3. 결과가 여러번 사용된다.

4. 결과 재사용이 성능을 향상시킨다.

 

Overlapping Subproblem 은 중복되는 부분 문제이다. 예를 들면 N번째 피보나치수를 구하는 문제를 구하는 문제는 N-1번째 N-2번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 경우가 생긴다.
큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야한다. 그리고 문제를 작은 문제로 나누어서 풀 수 있어야한다.

 

Optimal Substructure 문제의 정답을 작은 문제의 정답을 구할 수 있다.

다이나믹 프로그래밍에서는 작은 문제들을 한 번만 풀어야한다.(시간을 줄이려면 당연히) 그리고 정답을 구했으면 이 답을 어딘가 메모해놓고 (Memoization) 이 답들을 이용해서 큰 문제를 푼다. 그리고 저장되는 공간을 cache라고 한다. 따라서 DP를 구현하기 위해서는 메모를 작성하는 부분과 메모를 읽는 부분이 필요하다. 피보나치 수를 구하는 예제를 살펴보면서 DP를 더 자세히 알아보자.

(출처 : http://gnujoow.github.io/algo/2016/05/15/Algo0-dynamic-programing/)

 

int fibonacci(int n){
    if (n <= 1) return n;
    else{
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

 

피보나치 수열을 구하는 함수가 작동하면 함수의 재귀호출로 작은 피보나치수 들을 구하게 되는데 이때 중복해서 구해지는 수들이 있다. 이를태면 fibonacci(2),fibonacci(3)이 여러번 호출된다.

 

int memo[100]={0,};
int fibonacci(int n){
    if( n <= 1) return n;
    else{
        if(memo[n] > 0) return memo[n];
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

작은 문제를 풀 때 작은 문제들의 답을 메모를 하고 중복되는 작은 문제를 풀어야 할 때는 이미 답을 알고 있으므로 메모된 답을 이용하면 더 빠르게 풀 수 있다.

 

Dynamic programming을 푸는 방법에는 두가지가 있다. (Top-down, Bottom-up) a. Top-down 방식은 다음과 같다.1. 문제를 작은 문제로 나눈다.2. 작은 문제들을 푼다.3. 작은 문제들의 답으로 전체 문제를 푼다.
b. Bottom-up 방식은 다음과 같다.1. 가장 작은 문제부터 푼다.2. 문제의 크기를 점점 크게 만들어서 전체문제를 푼다.