[etc] 동적 계획법
동적 계획법
수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
설명
문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장 하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
보통의 피보나치수열
function fib(n){
if(n==0) return 0;
if(n==1) return 1;
return fib(n-1) + fib(n-2);
};
/*
fib(5)를 구한다 하면
1.fib(5)
2.fib(4) + fib(3)
3.(fib(3) + fib(2)) + (fib(2) + fib(1))
4.((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5.(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
여기서 fib(2)가 중복되어 계산됨 -> 계산 속도가 떨어짐
*/
여기에 각 함수의 계산값을 저장하는 객체를 이용한 피보나치수열 - 동적계획법
var m;
function solution(n) {
m = new Array(n);
return fib(n)
}
function fib(n){
if( n <= 2 ) return 1;
if( m[n] != null ) return m[n];
return m[n] = fib(n-1) + fib(n-2);
}
/*
이렇게 각 계산값을 저장하면
중복계산이 줄어들고
시간복잡도는 O(n)이 된다.
*/
