Memoization (TIL 71일차)

if (!Memorization) return true;

Memoization

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

위키백과에서는 메모이제이션을 위와 같이 설명하고 있습니다. 반복되는 계산의 결과값 미리 저장해두고 필요할 때마다 바로 사용한다는 것인데요. Dynamic Programming(동적 계획법) 의 핵심이 되는 기술이라고 합니다.

조금 더 풀어보겠습니다. 컴퓨터는 반복적인 연산에 아주 능숙한 모습을 보이죠. 사람이라면 매우 오랜 시간이 걸리는 반복 작업을 컴퓨터는 아주 빠르게 수행할 수 있습니다. 그러나 컴퓨터도 만능은 아니죠. 컴퓨터의 연산 능력에도 분명 한계가 존재합니다. 때문에 불필요한 연산을 줄이고 코드를 효율적으로 구성해야 한정된 자원으로 더 많은 일들을 처리할 수 있게 됩니다.

그렇다면 메모이제이션은 언제, 어떻게 사용될까요? 앞서 말했듯이 메모이제이션은 다이나믹 프로그래밍의 핵심 기법입니다. 따라서 다이나믹 프로그래밍을 먼저 이해하면 메모이제이션 또한 자연스럽게 이해할 수 있을 것 같네요.

Dynamic Programming

다이나믹 프로그래밍이란 주어진 문제를 쪼개어, 더 작게 나뉜 문제들의 풀이를 통해 전체 문제를 해결하는 기법입니다. 다만 무조건 작게 나눈다고 가능한 것은 아니고 다음의 2 가지 조건이 성립해야만 다이나믹 프로그래밍 기법을 적용할 수 있습니다.

1. 큰 문제는 작은 문제들로 나뉜다.
2. 작은 문제에서 구한 답을 큰 문제에서도 사용할 수 있다.

이렇게 보면 재귀의 설명과도 비슷하다는 생각이 드는데요. 실제로 다이나믹 프로그래밍은 재귀와 메모이제이션을 사용하는 탑다운(Top-down) 방식과 반복문을 사용하는 바텀업(Bottom-up) 방식으로 나뉜다고 합니다.

(이유는 아직 잘 모르겠으나, 바텀업 방식에서 결과값을 저장할 때는 tabulation 이라는 용어를 사용한다고 합니다. 계산의 결과값을 저장한다는 점에서는 크게 차이가 없으나 나무위키의 설명에 따르면 메모이제이션이 결과가 필요할 때 계산을 한다면 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다는 차이가 있다고 하네요.)

예시

탑다운 다이나믹 프로그래밍의 가장 유명한 예제는 피보나치 수열입니다. 피보나치 수열은 이전 두 항의 합이 현재의 항이 되는 수열이죠.

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

피보나치는 위처럼 아주 간단한 재귀식으로 구현이 가능합니다. 큰 문제들을 작은 문제들로 나누고, 작은 문제의 답을 큰 문제를 풀 때 적용할 수 있다고 하는 다이나믹 프로그래밍의 조건에도 성립하죠. 그러나 위의 식은 O(2n) 이라는 시간 복잡도를 가지고 있기 때문에 n 이 늘어날 수록 연산 시간이 기하급수적으로 늘어나게 됩니다.

이 때 앞에서 언급한 것처럼 메모이제이션을 사용할 수 있습니다. 크게 어려운 내용은 아니고, 계산한 결과값을 저장했다가 사용할 수만 있으면 됩니다.

const fibonacci = (n, memo = []) => {
  if (n <= 1) {
    memo[n] = 1;
    return memo[n];
  };
  if (memo[n]) return memo[n];
  let result =  fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  memo[n] = result;
  return result;
}

memo 라는 배열이 추가되었고, 계산한 값이 나오면 memo 의 n 번째 요소로 저장하도록 구성되었습니다. debugger 를 사용해보면 n 이 1 이 될 때까지 쪼개진 후, 차례대로 계산값을 memo 에 저장했다가 사용하는 것을 확인할 수 있습니다.

const fibonacci = (n, memo = []) => {
  if (n <= 1) return 1;
  if (memo[n]) return memo[n];
  let result =  fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  memo[n] = result;
  return result;
}

위에서처럼 처음의 if 문에서 메모이제이션 대신 그냥 1을 바로 리턴해주어도 함수는 문제 없이 동작합니다. 내부의 memo 배열의 0, 1 번째 요소가 empty 값이 된다는 차이만 있습니다.