8. Dynamic Programming

동적 계획법이란?

메모리를 사용해 수행시간의 효율성 향상시키는 방식

이미 계산된 결과를 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 한다.

Top-Down 방식과 Bottom-Up 방식(전형적) 두 가지가 있다. 

- Dynamic Allocation에서 dynamic(실행 도중에 해결하는 방식)과 무관한 명칭이다. 

 

조건

Optimal Substructure (최적 부분 구조)

Overlapping Subproblem (중복되는 부분 문제)

 

예시

Fibonacci 수열

a₁ = 1, a₂ = 1 이고, a_n = a_n-1 + a_n-2 이라는 점화식으로 표현할 수 있다. 

재귀함수를 사용해서 풀 수 있는 문제인데, 여기서 이 수열의 계산값들을 배열이나 리스트로 저장해두면 더 빠르게 해결 가능하다. -> 계산한 결과를 다시 반복하지 않음으로써 시간을 줄일 수 있다. 

• 재귀로만 계산할 경우 시간복잡도: O(2ⁿ)

 

메모이제이션(Memoization)

• 한번 계산한 결과를 메모리 공간에 기록해두었다가, 똑같은 연산이 필요할 때 값을 가지고 옴. 
• 캐싱이라고도 함. 
•  DP 테이블: 결과 저장용 배열/리스트
• 메모이제이션이라는 개념이 다이내믹 프로그래밍에 국한되는 방식이 아니라는 것 주의

 

코드

Bottom Up 방식

#include <iostream>

long long d[100];

int main(void){
	
	// bottom up 방식, 낮은 인덱스부터 목표 인덱스까지 차례대로 더한다. 
	
	// 첫 번째, 두 번째 요소 초기화 
	d[1] = 1;
	d[2] = 1;
	
	// 목표 설정 
	int n = 50;
	
	// 반복문을 돌려서 a3부터 a99까지 구할 수 있도록 한다.
	for(int i = 3; i<n+1; i++){
		d[i] = d[i-1] + d[i-2];
	}
	
	std::cout << d[n] << std::endl;
	
}

Top-Down

#include <iostream>

long long d[100] = {0,};

long long fibonacci(int n){
	
	if (n==1 || n==2){
		return 1;
	}
	
	// 이미 계산한 값이면 
	if(d[n]!=0){
		return d[n];
	}else{
    // 아니면 피보나치 값을 구해 배열에 저장 후 그 값 반환
		d[n] = fibonacci(n-1) + fibonacci(n-2);
		return d[n];
	}
	
}


int main(){
	
	long long res = fibonacci(50);
	std::cout << res << std::endl;
	
	return 0;
}

메모이제이션을 이용하면 시간복잡도는 O(N)으로 줄어든다. 

 

분할 정복과의 차이

분할 정복은 문제 풀이의 반복이 일어나지 않는다는 점이다. 분할 정복은 문제를 나누지만, 각 sub 문제가 중복되지 않지만, 위에서 본 다이내믹 프로그래밍에서는 sub problem 풀이를 통해 다른 sub problem을 해결할 수 있다.