DP(Dynamic Programming) 알고리즘

DP 알고리즘이란?

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. Dynamic은 별 의미 없고 단지 멋있어서 붙인 이름이라고 한다.

 

DP 방법

모든 작은 문제들은 한번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해 놓는다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

DP 조건

- 작은 문제가 반복 일어나는 경우

- 같은 문제는 구할 때 마다 정답이 같은 경우

 

Memoization?

메모이제이션은 한번 계산한 작은 문제를 저장해놓고 다시 사용하는 것을 말한다.

 

예를 들어 피보나치를 재귀함수로 풀게 될 경우

위의 그림처럼 했던 작업을 또 하게 되는데 예를 들어 F(3)의 경우 또 구하게 된다.

이 때 DP 조건 두가지 1. 작은 문제들이 반복된다. 2. 같은 문제를 구할 때 마다 정답이 같다. 를 만족하므로 DP로 풀 수 있다.

 

Bottom-up 과 Top-down

1. Bottom-up

작은 문제부터 차근차근 구해나아가는 방법

function fibonaccit_bottom_up(n){
  if(n<=1){
    return n;
  }

  let first = 0;
  let second = 1;
  let next;

  for(let i=0; i<n-1; i++){
    next = first+second;
    first = second;
    second = next;
  }

  return next
}

console.log(fibonaccit_bottom_up(n))

 

2.Top-down

재귀함수로 구현하는 경우가 대부분 Top-down. 큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결

let memo = [];
for(let i=0; i<100; i++){
  memo[i] = 0;
}

function fibonaccit_top_down(n){
  if(memo[n] > 0){
    return memo[n]
  }
  
  if( n<=1 ){
    memo[n] = n;
    return memo[n]
  } else {
    memo[n] = fibonaccit_top_down(n-1) + fibonaccit_top_down(n-2);
    return memo[n]
  }
}

console.log(fibonaccit_top_down(6))