Algorithm - Dynamic Programming

Dynamic Programming

• 복잡한 문제를 단순한 작은 문제들로 분해함
• 작은 문제를 한번만 풀고, 그 해를 저장해둠(memoization)
• 큰 문제를 풀 때 똑같은 작은 문제가 나타나면, 저장해둔 해를 사용해서 해결함
  • 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 푸는 방법
    • Optimal Substructure : 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 구조
    • Overlapping Subproblems : 부분 문제의 정답을 한번만 계산하고 같은 부분 문제를 풀 때 저장한 정답을 사용함

Dynamic Proramming의 조건

• 아래의 두 조건을 만족하는 경우에만 Dynamic Programming을 사용 가능함
  • 작은 문제가 반복해서 일어남
  • 작은 문제의 결과값은 항상 같음

Divide and Conquer & Dynamic Programming

• Divide and Conquer as to Dynamic Programming
  • 공통점 : 큰 문제를 작은 문제로 나누어 푸는 방법
  • 차이점 : 작은 문제가 반복되지 않음, 작은 문제의 결과값이 항상 같음

Solutions

• Recursive Solution : Top-down Approach
• Memoization Solution
• Tabulation Solution : Bottom-up Approach

Recursive Solution : Top-down Approach

• 함수를 재귀적으로 호출하여 작은 문제를 해결함
• Big O notation of Time Complexity : O(2^N)

// 피보나치 수열 - Recursive Solution 
function fib(n){
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Problem of Recursive Solution

• 이전에 계산한 문제를 중복해서 계산하는 경우가 많아서 시간이 오래 걸림
  • 이전의 값을 사용하면 이후 문제를 풀기 수월함
  • Dynamic Programming은 복잡한 문제를 서브 문제들로 분해하고, 서브 문제를 각각 풀고, 푼 값을 저장함

Memoization

• Memoization : 비싼 연산의 함수 호출 결과값을 저장하고, 같은 입력값으로 함수가 다시 호출되었을 때 저장해둔 결과값을 반환함
• Big O notation of Time Complexity : O(N)

Memoization Soluton

// 피보나치 수열 - Memoized Solution
function fib(n, memo=[]){
  if (memo[n] !== undefined) return memo[n];
  if (n <= 2) return 1;
  let res = fib(n - 1, memo) + fib(n - 2, memo);
  memo[n] = res;
  return res;
}

Tabulation : Bottom-up Approach

• Tabulation
  • 이전 결과를 "table"(array)에 저장함
  • iteration을 사용함
  • tabulation을 사용하면 Space Complexity가 낮아짐
  • Big O notation of Time Complexity : O(N)

Tabulated Solution

// 피보나치 수열의 Tabulated Solution
function fib(n) {
  if (n <= 2) return 1;
  var fibNums = [0, 1, 1];
  for (let i = 3; i <= n; i++) {
    fibNums[i] = fibNums[i - 1] + fibNums[i - 2];
  }
  return fibNums[n];
}

Big O notation of Solutions

• Big O notation of Time Complexity
  • Recursive Solution : O(2^N)
  • Memoized Solution : O(N)
  • Tabulated Solution : O(N)