[DP] 동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming : DP)

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

최적부분구조와 같은 문제에서 효과를 발휘함 ★

 

최적 부분 구조(Optimal Substructure)

출처 : 나무위키

문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성

 

동적계획법 사용

동적 계획법을 적용하기 위한 예시를 가져왔다

여기서 조건은

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b>=1)
• f(0,0) = 1
• 자연수 n에 대하여 f(n,0)=f(0,n)=1

여기서 주목해야 하는 점은 f(1,1)이다

f(2,2)는 f(1,2)와 f(2,1)의 합으로 나타낼 수 있고,

f(1,2)와 f(2,1)는 또 각각 f(0,2)+f(1,1)과 f(1,1)+f(2,0)으로 나눌 수 있다

그렇다면 두 개를 개산하기 위해 각각 f(1,1)을 따로따로 계산해야하는 일이 생긴다

하지만 동적계획법을 쓰게 되면, f(1,2)에서 미리 계산된 f(1,1)의 결과값을 가져와 f(2,1) 연산에 적용시킬 수 있다

여기서는 공통 연산 부분이 f(1,1)밖에 안나와서 연산 횟수차이가 별로 나지 않지만,

연산의 규모가 커질수록 동적계획법의 효율도 동시에 커지게 된다

이러한 연산을 하기에 가장 기본적인 예시로 재귀함수 형태의 피보나치 수열이 있다

 

동적 계획법 - 피보나치 수열

출처 : 나무위키

기본적으로 피보나치 수열을 나타내는 함수는 다음과 같다

(나는 Java를 쓰기 때문에 Java로 표현하였다)

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

이 문제를 동적계획법으로 나누어서 풀면, 값을 저장해주는 전역변수를 먼저 설정해주면 된다

int num[] = new int[100]; //0으로 초기화
int fibo(int n) {
	if(n<=1)
		return 1;
	if(num[n]!=0)
		return num[n];	//값이 있으면 return
	num[n] = fibo(n-1)+fibo(n-2);	//없으면 분할해서 구하기
	return num[n];
}