동적 프로그래밍 - 메모이제이션(Memoization)

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

DYNAMIC PRGRAMMING is.. an optimization technique.
dynamic programming = divide and conquer + memoization

 

언제 Dynamic Programming을 적용할지에 대한 Cheatsheet

1. Can be divided into subproblem?
2. Recursive Solution
3. Are ther repetitive subproblems?
4. Memoize subproblems
5. Demand a raise from your boss

 

동적 프로그래밍이라는 용어랑 사실 내용이랑은 크게 관련이 없다고 한다. 단지 동적 프로그래밍은 문제를 더 작은 반복적인 문제들로 쪼갠 후에, 각 문제들의 return값을 어딘가에 보관함으로써 최적화를 시키는 테크닉이다.

 

# Fibonacci and Dynamic Programming

function fibonacci(n) {
  if (n < 2) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}
fibonacci(6); // 8

재귀 함수를 배울 때 피보나치 문제를 재귀 함수로 풀었는데, 그 때 이 문제 풀이의 Big O는 O(2^n), Exponential Time이라고 했다. 거의 최악에 가까운 시간 복잡도이다. 동적 프로그래밍으로 이를 개선시켜보자.

 

function fibonacciMaster() { // O(n)
  let cache = {};
  return function fib(n) {
    if (n in cache) return cache[n];
    else {
      if (n < 2) return n;
      cache[n] = fib(n-1) + fib(n-2);
      return cache[n];
    }
  }
}

cache라는 객체를 만들고, 만약 실행 결과가 cache에 존재한다면, 실행시키는 대신 cache에서 값을 찾아서 불러오도록 하고 있다. 알다시피 Hash Table에서의 lookup은 O(1)이기 때문에 무척이나 빠르다.

 

아래는 유명한 Memoization을 활용하는 알고리즘 문제들이다.

☞ House Robber

☞ Best Time To Buy And Sell Stock

☞ Climbing Stairs