메모이제이션

컴퓨터 프로그래밍 용어로, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다. 동적 계획법의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이다.

• 나무위키 (https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98)

예시

• 피보나치 수열을 출력할때 재귀 함수를 호출하면

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

이렇게 할수도 있지만 불필요한 계산을 많이 하게 된다.

때문에 불필요한 계산을 줄이기 위해서 별도의 변수를 통하여 계산값을 저장하고 계산할때마다 꺼내와서 비교하고 이미 계산을 했는지 비교할 필요가 있다.

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

기존의 O(2^n) 의 복잡도가 O(n) 으로 감소하는것을 알수가 있다.