[알고리즘] 다이나믹프로그래밍

Overlapping Subproblem 

 겹치는 작은 문제

 

Optimal Substructure

 최적부분구조

 

Optimal Substructure

목적

문제의 정답을 작은 문제의 정답에서 구할수 있다.

모든 문제를 풀며, 모든 문제는 1번만 풀어야한다.

 

시간복잡도

문제의 개수 : N

모든 문제를 1번씩 푸는 시간 : 1

O(N)의 시간복잡도를 가진다.

 

 

ex)

서울 > 부산 가장빠른길은 대전과 대구를 거친다의 조건이 있을경우,

대전 > 부산 가장빠른길은 대구를 거친다.

 

프로그래밍 방법

Optimal Substructure을 만족하면 정답을 메모한다. ( 코드에선 배열 ) Memoization 

 

예제 피보나치수열

 

피보나치를 구하게 될경우 아래의 코드와 같다.

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

 

이때 f(5)를 호출할경우 f(4) ... f(0) 을 구해야하며 f(4)또한 f(3)....f(0)을 구하면서 값을 구하게된다.

f(4)를 구하면서 f(3)이하의 값을 구했고, 다음 f(3)에서 재사용을 하면된다.

 

int memo[100]; //추가

int fi(int n){
	if( n<=1 ) {
    	return n;
    }else {
    	if ( !memo[n]>0 ){
    		memo[n] = fi( n-1 ) + fi( n-2 ); 
        } //추가
    	return memo[n]; //변형
    }
}

배열의 초기값일 경우 memo[n]에 피보나치 값을 저장하고 초기값이 아닐경우 그값을 꺼내어 사용한다.

 

 

1. Top-Down : 재귀

 ex) 위의 피보나치

 

2.Bottom-Up : 반복문

int memo[100];

int fi(int n){
	memo[0] = 0;
    memo[1] = 1;
    for ( int i=2; i<=n; i++ ){
    	memo[n] = memo[n-1] + memo[n-2];
    }
    return memo[n];
}

 

문제풀이

점화식의 정의를 구한다.

ex) 피보나치 Fn = Fn-1 + Fn-2