Memoization

Memoization은 주어진 입력값에 대한 결과를 저장함으로써 같은 입력값에 대해 함수가 한 번만 실행되는 것을 보장한다.

피보나치수열을 예로 들어보자.

함수 내에서 자기 자신을 다시 호출하여 작업을 수행하는 재귀함수를 구현할 때 동일한 계산을 반복해야하는 경우가 많다.

메모이제이션을 설명하기 가장 적합한 예제일 것이다.

f(n) 을 n 번째 피보나치 수 라고 했을 때, f(2)를 구할 때 f(1)은 1번 호출되고, f(4)를 구할 때는 3번, f(6)을 구할 때 8번...

이런식으로 중복되게 호출을 해야한다.

이런 중복 호출을 막기 위해서 이전에 호출된 값을 저장 해놓고 다음계산에 필요할 시 값만 가져와서 사용하면 실행시간을 대폭 줄일 수 있게된다.

let callCount = 0; // 연산 횟수

function fiboByMemoization(num, memo) {
  callCount++; // 연산 횟수 +1
  memo = memo || [];
  
  if(memo[num] !== undefined) {
    return memo[num];
  }  
  
  if(num <= 1) {
    memo[num] = num;
    return num;
  }
  
  memo[num] = fiboByMemoization(num - 2, memo) + fiboByMemoization(num - 1, memo);
  
  return memo[num];
}

fiboByMemoization(10);
console.log(callCount); // 19