[TIL-20210616] 메모이제이션(Memoization)

메모이제이션

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술.

재귀함수에서의 메모이제이션 사용 전후 비교

재귀함수의 대표적인 예로 피보나치 수열이 있다.

// 일반 재귀함수로 작성된 피보나치 수
function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 2) + fibonacci(n - 1);
}

간단한 함수처럼 보이고 이상없이 동작할 거 같지만, 함수의 실행시간을 간단히 측정해보면 n의 값이 커질수록 함수의 실행시간이 길어지는 것을 확인할 수 있다.

let start = new Date(); // 시작
fibonacci(42); // 267914296
let end = new Date(); // 종료

console.log(end - start); // 4003ms => 약 4초

n의 값이 42가 되었을때 실행시간이 대략 4초 발생했다. 함수 1개가 동작하는데 4초가 걸린다면 만약 이 함수를 21600개 실행시켜야한다면 약 24시간 하루가 꼬박 걸리게된다.
이러한 실행시간을 줄이기 위해 이전에 계산했던 값을 메모리에 저장해서 반복을 줄여 결과적으로 실행시간을 줄여주는 메모이제이션을 하는 것이다. 피보나치 함수를 메모이제이션을 적용하여 작성해보면 아래와 같다.

// 메모이제이션으로 작성된 피보나치 함수
function fibonacciM(n) {
  let saved = [0, 1];
  let fib = (n) => {
    if (saved[n] !== undefined) return saved[n];
    saved[n] = fib(n - 1) + fib(n - 2);
    // 계산한 값을 saved[n]에 할당해 메모리에 저장해서 다음 계산을 진행한다.
    return saved[n];
  };
  return fib(n);
}

이렇게 메모이제이션으로 작성된 fibonacciM 함수를 실행시켜보면,

let start = new Date(); // 시작
fibonacciM(42); // 267914296
let end = new Date(); // 종료

console.log(end - start); // 0

같은 n의 값을 계산하는데 시간이 확연히 줄어든 것을 확인할 수 있다.

마무리

이처럼 메모이제이션은 반복되는 계산이 많을수록 효과가 높아진다. 특히 반복 작업이 많을 경우에는, 숫자가 커질수록 반복 횟수가 기하급수적으로 늘어난다. 하지만 메모이제이션은 속도면에서 큰 이점이 있지만 속도를 위해 많은 메모리 사용량이 소비되기 때문에, 많은 RAM을 사용하는 함수를 처리해야 할 경우 영향을 준다고 한다. 때문에 무조건 메모이제이션이 좋다라고 하기보단 상황에 맞게 코드를 작성해서 프로그램을 완성하는 것이 중요한 것 같다.