[알고리즘] Dynamic Programming (다이나믹 프로그래밍)이란

다이나믹 프로그래밍 이란? 

주어진 문제를 여러개의 부분 문제들로 나누어 푼다음, 겹치는 문제의 경우 메모이제이션 기법을 사용하여 주어진 문제를 푼다

기억하며 풀기라고 한다.

 

사용하는이유

일반적인 재귀와 DP는 매우 유사하다. 차이점은 일반적인 재귀를 사용할 때는 동일한 작은 문제들이 여러 번 반복되어

비효율적인 계산이 될 수 있다는 것이다. DP는 Memoization 기법을 통해 반복되는 작은 문제들의 결과 값을 저장해 두고 재사용하여

계산 속도를 향상시킨다.

 

 

특징

분할가능 -> 큰문제들을 작은 문제로 나눈다. 작게 나눈 문제는 항상 같은 값을 도출해야한다.

부분 문제반복 -> subproblem 들이 겹칠 때 memoization을 통해 필요한 연산 수를 줄일 수 있다

최적 부분 구조 -> subproblem의 solution으로 더 큰 규모의  proplem의 solution을 구한다.

 

 

 

 

장단점

장점

모든 가능한 경우를 확인하기 때문에 근사치가 아닌 정확한 값을 얻을 수 있다.

 

단점

모든 가능한 경우를 확인하기 때문에 알고리즘에 비해 시간 복잡도가 크다.

 

 

 

코드

 

DP를이용한 피보나치의 Top down 방법

let fiboArr = [0];
let fiboWithMemoization = (n) => {
  if (n < 3) {
    fiboArr[n] = 1;
  }

  if (!fiboArr[n]) { // 내가 저장한 값 중에 없다면 ...
    // 재귀를 이용해 구하고 저장
    fiboArr[n] = fiboWithMemoization(n - 1) + fiboWithMemoization(n - 2);
  }

  return fiboArr[n];
};