동적계획법(Dynamic Programming)

동적 계획법이란?

하나의 문제는 단 한 번만 풀도록 하는 알고리즘입니다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다. 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있습니다.

---

동적 계획법을 사용할 수 있는 조건

1. Problem가 더 작은 sub-problem으로 쪼개질 경우
2. 이 작은 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우
3. sub-problem이 겹칠 경우

---

피보나치 수열

위 공식에서 Fn은 Fn-1과 Fn-2로 쪼개지면서 조건 1을 만족시킨다. 그리고 fn-1과 fn-2로 fn의 값을 구할 수 있으므로 조건 2를 만족시킨다.

 

마지막으로 중복의 fn을 가지므로 조건 3도 만족한다.

피보나치 수열에서 이전에 계산한 값을 다시 계산하지 않도록 저장을 해주고 이를 다음에 중복으로 사용일 될 경우 저장된 값을 불러와서 사용하는 과정을 메모이제이션(Memoization)이라고 합니다.

let fibo = [0,1];

function DP(num){

  if(fibo.length < num)
    for(let i = fibo.length; i <= num; i++){
      fibo.push(fibo[i-2]+fibo[i-1])
    }
    return fibo[num]
}
console.log(DP(20))
//6765

위 코드와 같이 이전의 값이 존재하면 바로 저장된 배열에서 출력을 한다.

하지만 저장이 된 배열보다 이 후의 값을 알기 위해서는 for문을 통해서 새로운 값을 저장하게 되는데 이 때는 이전 수는 다시 계산하는 것이 아닌 저장된 값을 가져오는 것이 중요하다.

 

 

> DP 관련 문제