다이나믹 프로그래밍(동적계획법)

다이나믹 프로그래밍이라는 것은

큰 문제를 작은 단위로 나눠서 푸는 알고리즘이다. 

 

방식 2개

 

1. Top - down

    재귀함수를 사용

 

int memo[100];
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];
    }
}

 

2. Bottom - p

    반복문을 사용

int d[100];
int fibonacci(int n) {
	d[0] = 0;
    d[1] = 1;
    for (int i = 2; i <= n; i++){
    	d[i]= d[i-1] + d[i -2];
    }
    return d[n];
}

 

두 방법의 시간차이는 알 수 없음. 시간차이에 대해 고민할 필요 없음.

 

나에게는 2번째 방법이 더 맞는 것 같다.

 

 

이외에 문제를 작게 나눠서 푸는 알고리즘이 또 있다. 

분할정복법 (divide & conquer)

D.P와의 차이점은, D.C알고리즘은 작은 문제가 절대로 중복되지 않는다는 점이다.