메모이제이션이란?

메모이제이션(memoization)은 특정 연산의 결과를 캐시에 저장해두고

나중에 같은 입력이 들어오면 다시 계산하지 않고 캐시된 결과를 반환하는 최적화 기법이다.

쉽게 말해, 같은 연산을 여러 번 하지 않도록 결과를 저장해 두고 재사용하는 것이다.

 

메모이제이션의 목적

• 불필요한 계산 방지 : 같은 입력값에 대해 중복 계산을 피한다.
• 성능 개선 : 특히 연산 비용이 높은 함수(예: 재귀, 복잡한 수학적 계산)에서 효율적이다.

작동 원리

1. 함수가 실행되면, 입력값과 결과값을 키-값 쌍으로 저장한다.
2. 동일한 입력값으로 함수가 호출되면, 저장된 결과를 반환한다.(실제로 계산을 다시 하지 않는다.)

예제 : 기본 메모이제이션

다음은 피보나치 수를 계산하는 코드이다.

메모이제이션이 없는 경우

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

console.log(fibonacci(40)); // 매우 느림 (중복 계산 많음)

 

fibonacci(40)은 같은 값(fibonacci(39), fibonacci(38) 등)을 여러 번 계산해서 시간이 오래 걸린다.

 

메모이제이션 적용한 경우

function memoizedFibonacci() {
  const cache = {}; // 계산 결과를 저장할 캐시 객체
  
  function fib(n) {
    if (n in cache) { 
      return cache[n]; // 이미 계산된 값이 있으면 반환
    }
    if (n <= 1) {
      cache[n] = n; // 결과 저장
    } else {
      cache[n] = fib(n - 1) + fib(n - 2);
    }
    return cache[n]; // 결과 반환
  }
  
  return fib;
}

const fibonacci = memoizedFibonacci();
console.log(fibonacci(40)); // 매우 빠름

 

캐시 객체를 이용해서 중복된 계산을 피하고 동일한 입력값에 대해 이미 계산된 결과를 바로 반환하므로 성능이 크게 향상된다.