동적 계획법

동적 계획법은 알고리즘 문제를 최적 부분구조로 나누어 푸는 방법입니다. 가령 fibo(n)=fibo(n-1)+fibo(n-2)에서 fibo(n)은 fibo(n-1)과 fibo(n-2)라는 두 문제로 치환될 수 있음을 볼 수 있습니다. 이렇게 해결하고자 하는 문제가 해결하고자 하는 문제와 똑같은 보다 쉬운 여러개의 문제로 분할 될 수 있을 때 해당 문제는 최적 부분구조를 가지고 있다고 말합니다.
이러한 동적 계획법을 효율적으로 수행하기 위해서는 memoization기법이 필요합니다. 아무리 문제를 분할 했다 하더라도 지수승으로 증가하는 모든 문제를 해결한다면 너무 비효율적입니다.
가령 피보나치 문제를 단순히 최적부분구조로 나누어 접근하면 fibo(70)도 구하기가 어렵습니다. (참고로 사람이 풀어도 fibo(70)까지는 5분안에 풀 수 있을 겁니다.) 이 때 memoization을 이용하여 각 fibo(n)의 값을 기억하고 있다면 fibo문제를 O(n)안에 해결 할 수 있습니다.

피보나치 문제를 자바스크립트로 동적계획법을 이용하여 구현하면 다음과 같습니다.

function fibonaccis (n) {
    let memo=[0,0,1];

    function fibo(n){
        if(n===2){
            return memo[2];
        }
        if(n===1){
            return memo[1];
        }

        let left=memo[n-1] || fibo(n-1);
        let right=memo[n-2] || fibo(n-2);
        memo[n]=left+right;
        return memo[n];
    }

    return fibo(n);
}


console.log(fibonaccis(70));

참고자료
1. 한 권으로 그리는 컴퓨터 과학 로드맵, 지은이 : 블라드스톤 페헤이라 필루 옮긴이 : 박연오 102P-103P