[알고리즘] 동적 프로그래밍 (자바스크립트)

DP

동적 프로그래밍이란 복잡한 문제를 더 간단한 하위 문제의 모음으로 쪼갠 후, 각 하위 문제들을 풀어 그 답을 저장하여 문제를 해결하는 문제 해결 방식을 말한다. 적용 가능한 문제 영역이 그리 넓지 않지만, 적용 가능한 경우에는 성능에 있어 아주 큰 차이를 가져온다.

 

두 가지 특성

• Overlapping Subproblems : 한 문제를 더 작은 문제들로 나눌 수 있고, 그 조각들 중 일부가 재활용 가능해야 한다.
• Optimal Substructure : 하위 문제의 최적 해답을 통하여 더 큰 범주를 갖는 문제의 최적 해답을 구성할 수 있어야 한다.

 

재귀를 통한 구현 : 피보나치 수열

수열의 첫 번째 숫자와 두 번째 숫자는 1이며, 그 밖의 경우 Fib(n) = Fib(n-1) + FIb(n-2)이다. 해당 구현에 DP는 사용되지 않았다.

function fibo(n) {
  if (n <= 2) return 1;
  return fibo(n - 1) + fibo(n - 2);
}

트리 구조를 가지며 중복되는 연산이 발생하게 된다. 시간 복잡도 또한 O(2^N)으로, 커지는 입력 정수에 따라 기하급수적으로 연산량이 늘어나게 된다.

 

메모이제이션 (하향식, 탑다운)

반복되는 하위 문제에 대한 답을 저장하는 방법이다. 빈 객체 배열에 반복되는 연산의 결과를 저장해놓고, 다음 번에 중복되는 연산이 발생할 경우 저장해둔 데이터에서 불러와 사용한다.

function fiboDP(n, memo = []) {
  // 이미 연산된 값인 경우, 그 값을 그대로 반환
  if (memo[n] !== undefined) return memo[n];
  if (n <= 2) return 1;

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

 

타뷸레이션 (상향식, 바텀업)

DP의 두 번째 구현 방식으로, 보통 루프와 함께 순환을 통해 작업한다. 배열에 데이터를 저장하고 루프를 돌면서 앞으로 나아가 덧셈을 하는 방식이다.

function fiboTabu(n) {
  if (n <= 2) return 1;
  var fiboNums = [0, 1, 1];

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