동적계획법(DP)

동적 계획법

쉽게 말해 이미 구해 놓은 값들을 재활용하는 알고리즘이라고 생각하면 편하다.

예시를 들면 편하다.

피보나치(동적 계획법 X)

let count = 0;
function fibo(num) {
    count++;
	if(num == 0) {
		return 0;
	} else if (num <= 2) {
		return 1;
	} else {
		return fibo(num-1) + fibo(num-2);
	}
}

console.log('fibo(50) : '+fibo(50))            
//fibo(50) : 12586269025; 71초 후 계산완료
console.log('fibo함수가 호출된 횟수 : ' + count)
//fibo함수가 호출된 횟수 : 25,172,538,049

피보나치(동적 계획법 O)

let memorize = [0,1,1];
let count = 0;
function fibo(num) {
    count++;
	if(memorize[num]) {
		return memorize[num];
	} else {
		memorize[num] = fibo(num-1) + fibo(num-2);
		return memorize[num];
	}
}

console.log('fibo(50) : '+fibo(50))            
//fibo(50) : 12586269025 0.071초 후 계산완료
console.log('fibo함수가 호출된 횟수 : ' + count)
//fibo함수가 호출된 횟수 : 97

위 두 개 코드 모두 피보나치를 구하는 코드이지만 계산 시간은 천지 차이다.

동적 계획법을 사용하지 않은 첫번째 코드는 피보나치의 각각의 값을 끝까지 내려가서 계산한다.

재귀 함수로 구현했기 때문에 한번 재귀가 일어날 때마다 함수가 새롭게 호출된다. 그 결과가

첫 번째 코드는 fibo(50)을 계산하기 위해 fibo함수가 250억 가량 호출되었다. 시간도 71초 이상 걸렸다.

반면에 두 번째 코드는 fibo(50)을 계산하기 위해 fibo함수가 97번만 호출되었다. 시간도 0.07초 가량 걸렸다.

1. 주어진 문제를 작은 문제들로 쪼갤 수 있어야 한다.
2. 쪼개진 작은 문제들이 계산하다 보면 중복되는 값들이 존재해야 한다.
3. 중복된 값들을 저장 할 수 있어야 한다.
4. 3번째의 저장한 값을 통해 주어진 문제를 해결 할 수 있어야 한다.

위 4개의 조건을 만족하면 동적 계획 법으로 작성할 수 있다.

간단한 알고리즘이지만 문제는 이 알고리즘을 어디서 언제 사용해야 하는지 파악하는 것이 더 어려운 것 같다.

관련 문제들

https://school.programmers.co.kr/learn/courses/30/parts/12263