ChatGPT와 JavaScript 공부:메모이제이션(Memoization)

ChatGPT와 JavaScript 공부:메모이제이션(Memoization)

이번 포스트에서는 JavaScript에서의 메모이제이션(Memoization)에 대해 공부해 볼까 한다.
이름만 봤을 때는 메모리와 관련된 것 같은데 ChatGPT를 통해 알아보자.

Question

JavaScript의 메모이제이션에 대해서 설명해줘

Answer

메모이제이션은 프로그래밍에서 사용하는 최적화 기법 중 하나로, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 실행을 줄이는 방법입니다.
이 방법은 특히 계산 비용이 높은 함수에서 효과적입니다.

즉, 메모이제이션은 중복된 계산의 반복을 줄임으로서 성능 개선, 프로그램의 효율성 증가를 기대해 볼 수 있는 기법이다.
재귀 함수를 이용한 피보나치 수열 계산하는 코드를 통해 일반 코드와 메모이제이션 코드를 비교해 보자.
ChatGPT에게 비교를 위해 일반적인 코드와 메모이제이션을 사용한 코드를 작성해달라고 했다.

피보나치 수열 계산 - 일반

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

console.log(fibonacci(10)); // 55

피보나치 수열을 계산하는 일반적인 재귀 함수이다.
이 방식은 간단하지만 `fibonacci(n - 1) + fibonacci(n - 2)`를 계산할 때 중복된 계산이 많이 발생할 수 있다.

피보나치 수열 계산 - 메모이제이션

function memoize(func) {
  let cache = {};
  
  return function(n) {
    if (n in cache) {
      return cache[n];
    } else {
      let result = func(n);
      cache[n] = result;
      return result;
    }
  };
}

let fibonacci = memoize(
  n => (n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2))
);

console.log(fibonacci(10)); // 55

동일한 함수를 메모이제이션으로 구현한 코드이다.
`memoize` 함수는 `fibonacci` 함수의 계산 결과를 캐싱하고, 필요할 때 캐시에서 해당 결과를 가져온다.

즉, `fibonacci(n - 1) + fibonacci(n - 2)`를 계산할 때 중복된 계산들을 줄일 수 있다.
좀 더 이해하기 쉽도록 저 함수에서 `cache`를 console.log로 출력해보자.

function memoize(func) {
  let cache = {};
  
  return function(n) {
    console.log(cache);
    if (n in cache) {
      console.log(`n == ${n}`);
      return cache[n];
    } else {
      let result = func(n);
      cache[n] = result;
      return result;
    }
  };
}

let fibonacci = memoize(
  n => (n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2))
);

console.log(fibonacci(10)); // 55

메모이제이션을 사용한 피보나치 함수에서 console.log(cache)를 추가해 함수가 실행될 때마다 cache를 출력하게 했으며, (n in cache)인 경우 n이 무엇인지 출력되게 코드를 추가해 보았다.

결과를 보면 반복 실행되면서 cache에 property가 추가되는 것을 볼 수 있다.
처음에는 빈 object였다가 최종적으론 0~9의 key를 가지는 property가 생성되었으며,
`n == 1`인 구간에선 `return cache[n];`을 통해 cache object의 key가 1인 값을 return 하는 것이니 cache에 저장된 1을 반환해 준다.
즉, 일반적인 방법으로 피보나치 수열을 계산하면 이미 한 번 계산을 했던 결과값을 또 계산하기 위해 반복문이 돌지만, 메모이제이션 기법을 사용하게 되면 저장되어 있는 계산된 결과를 가져오므로 중복된 반복 작업을 줄 일 수 있는 것이다.

그리고 또한, fibonacci 함수 안의 cache는 계속 유지되므로, fibonacci 함수의 n 값을 변경해서 다시 계산할 때도 저장되어 있는 cache에서 값을 가져오게 된다.

fibonacci(10)을 계산한 뒤에 fibonacci(5)를 계산하게 되면, cache에 이미 n이 5인 결과값이 저장되어 있기 때문에 반복문을 실행하지 않고 바로 결과값인 5를 출력해준다.

fibonacci(11)을 실행하면, 기존 cache에 저장되어 있는 값들을 통해 89 결과를 계산했으며,
다시 한번 fibonacci(11)을 실행하면 cache에 이제 key가 11인 property가 존재하므로 저장되어 있는 값을 가져오는 모습을 볼 수 있다.

ChatGPT를 통해 메모이제이션에 대해 공부해 보는 시간을 가졌다.
메모이제이션은 JavaScript뿐만 아닌 다른 프로그래밍 언어에서도 동일하게 사용할 수 있는 기법이니 알아두면 분명 도움이 될 것으로 보인다.

정리하자면,
메모이제이션은 이전에 계산한 결과를 저장함으로써 중복 계산을 방지하고 프로그램의 성능을 향상시키는 기법이다.
이 방법은 시간이 많이 소요되는 함수나 반복적으로 동일한 결과를 요구하는 함수의 효율성을 높일 수 있다.