메모이제이션이란?

메모이제이션(Memoization)이란 동적 계획법(Dynamic programming)의 핵심 기술로 동일한 계산을 반복해야 할 때, 이전에 계산한 값들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법입니다. 보통 예시로 피보나치 수열을 사용합니다.

피보나치 수열#

피보나치 수열(Fibonacci sequence)은 제0항을 0, 제1항을 1로 두고, 제2항부터는 바로 앞의 두 수를 더한 수로 놓습니다. 제0항부터 제10항까지 표현하면 다음과 같습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

이는 C 언어에서 재귀 함수를 사용해서 다음과 같이 구현할 수 있습니다.

int fibonacci(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

입력받은 n을 더 작은 단위인 (n - 1)과 (n - 2)로 나누고 나눠진 단위를 더 작은 단위로 다시 나눠서 n을 0이나 1이 되게 만듭니다. 트리 형식으로 보면 한눈에 확인할 수 있습니다.

예를 들어 fibonacci(5)의 경우에는 다음과 같은 트리가 나옵니다.

숫자를 조금씩 늘려가면서 트리를 확인하다 보면 트리가 걷잡을 수 없이 커지는 모습을 볼 수 있습니다. 실제로 코드를 작성해서 n에 40만 집어넣어도 실행 시간이 굉장히 오래 걸립니다. 계산은 계속하고 있지만 연산량이 많기 때문입니다. 이러한 문제를 해결하기 위해서 메모이제이션을 사용합니다.

메모이제이션#

앞에 예시로 사용한 트리에서 n이 5일 때 fibonacci(3)이 두 번 등장합니다.

한번 수행한 fibonacci(3)의 결괏값을 저장해두면 다음에 다시 fibonacci(3)을 사용할 때 반복되는 연산을 줄일 수 있게 됩니다. 이 부분이 메모이제이션의 핵심입니다. n이 커지면 커질수록 반복되는 부분이 늘어나기 때문에 메모이제이션의 효율은 크게 상승합니다.

다음은 앞서 작성한 코드에 메모이제이션을 적용해서 수정한 코드입니다.

int mem[100] = {0};

int fibonacci(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else if (mem[n] != 0)
    return mem[n];
  else {
    mem[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return mem[n];
  }
}

결과가 mem 배열에 있으면 더 이상 연산하지 않고, 결괏값을 반환합니다. mem 배열에 결괏값이 없으면 연산을 수행하고, mem 배열에 저장합니다.

저장하는 작업은 한 번만 수행하면 다음에 같은 연산이 나왔을 때 연산량을 줄일 수 있습니다.

정리#

동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나눠서 푸는 방법입니다. 예시로 들었던 피보나치 수열을 생각하면 좋습니다. 여기에 메모이제이션을 통해 다른 공간을 만들어 이용하면 더욱 빠르게 문제를 해결할 수 있습니다. 피보나치 수열을 다시 예로 들면 O(2^n) 시간 복잡도가 걸리던 문제를 O(n) 시간 복잡도로 풀 수 있습니다.