Dynamic Programming (기초 개념)

Dynamic Programming 이란?

복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼개서 각 하위 문제들을 풀어서 그 답을 저장하는 방식으로 문제를 푸는 것

대부분의 문제에 적용할 수 있는 것은 아니지만 사용할 수 있는 경우에는 코드의 속도를 많이 향상시켜준다.

=> 최적의 해답을 찾아내는 것

 

Dynamic Programming 을 사용하기 위한 전제 조건

1. 최적 부분 구조가 존재하는가

2. 반복되는 하위 문제가 있는가

 

반복되는 하위 문제란?

한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능하다는 말.

ex) Fibonacci Sequence

// Big O : O(2^n)
function fib(n) {
  if (n <= 2) return 1;

  return fib(n - 1) + fib(n - 2);
}

 

최적 부분 구조란?

하위 문제의 최적 해답을 통해서 더 큰 범주의 문제의 최적 해답을 구성할 수 있는 경우 해당 문제가 최적 부분 구조를 가지는 것

ex) A, B, C, D 가 있고 A 에서 D로 갈떄 A -> B -> C -> D 가 아닐 수 있다는 것. 

 

 

Dynamic Programming example - Fibonacci

TIP 

1. Fib(n) = Fib(n-1) + Fib(n-2)

2. Fib(2) is 1

3. Fib(1) is 1

 

Memoization

배열이나 객체인 데이터를 저장할 구조를 만든 다음에 시간이 오래 걸리는 함수를 실행하는 것. (메모 역할)

// Big O : O(n)
function fib(n, memo = []) {
  if (memo[n]) return memo[n];
  if (n <= 2) return 1;

  const res = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = res;
  return res;
}

 

Tabulation

테이블에 이전 결과를 저장하는 것으로 보통 배열을 사용한다. 재귀를 사용하는 Memoization에 비해 공간복잡도다 낫다.

(Memoization에서 stack이 넘치는 오류가 발생할 수 있다. = Maximum call stack size exceeded)

function fib(n) {
  if (n <= 2) return 1;
  let fibNums = [0, 1, 1];

  for (let i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
}