DP(Dynamic Programming)

어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위 구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이 동적계획법(Dynamic Programming) 이다.

 

Divide-and-conquer 와 비슷해 보이지만 DC는 문제를 큰 부분에서 작은 부분으로 나누는 Top-Down approach인데 반해, DP는 작은 문제부터 큰 문제로 풀어가는 Bottom-Up approach이다. 또한 DC는 나눈 문제들을 완전히 새로운 하나의 독립된 문제로 보지만 DP는 이전 단계의 답에 의존적이다. 그래서 한 번 푼적 있는 문제는 다시 풀지 않도록 테이블에 저장해둔다. 

 

정리하면,

 1. 문제를 작은 부분 문제로 나눈다.

 2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다. (Memoization)

 3. 테이블에 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.

 

DP 는 다음과 같은 특징이 있다.

 

 1) Overlapping Subproblems

 문제를 하위 문제로 나누어 풀 떄, 중복되는 하위 문제가 발생한다는 개념이다. 대표적으로 아래와 같은 피보나치 수열이 있을 수 있는데 Factorial 연산을 수행하다보면 중복되는 연산이 발생한다.

ex) 4! = 4 x 3!, 5!=5 x 4 x 3!

DP의 경우 이것을 해결하기 위해 Memoization, Tabulation 을 사용하여 중복된 계산을 막는다.

 

 2) Optimal Subproblems

문제를 하위 문제로 쪼개었을 때, 하위 문제를 해결하면 원래 문제를 해결할 수 있게 되는 구조를 말한다.

 

int Fibonacci(int n) {
	if( n > 1 ) 
    	return Fibonacci(n-1)+Fibonacci(n-2);
    else if ( n == 1 )
    	return 1;
    else 
    	return 0;
}

대표적으로 이 피보나치 수열을 C코드로 구현한 내용을 보면 알고리즘 Time Complexity는 $$O(2^n)$$ 으로 상당히 비효율적이다. 하지만 DP를 이용하여 알고리즘을 재구성해보자.

 

$$Fn = Fn-1 + Fn-2$$ 이고, $$ Fn-1 = Fn-2 + Fn-3 $$ 이다.

순서 번호	저장된 값
0	0
1	1
2	1
3	2
4	3
5	5
6	8
n-2	$$Fn-2$$
n-1	$$Fn-1$$
n	$$Fn$$

 

0,1 은 이미 정의 된 값을 그대로 저장하면되고 2부터 테이블에 저장된 값을 이용하여 답을 구해나간다. 이렇게 계속 구해나가면 $$Fn$$의 값을 구할 수 있는데, 이렇게 구현한 피보나치 수열의 Time Complexity는 $$O(n)$$ 이 된다.

Dived-and-conquer로 구한 시간 복잡도는 $$O(log_2n)$$ 이였지만 DP로 구한 $$O(n)$$ 은 이기때문에 분할 정복보단 성능이 조금 떨어진다고 할 수 있다.