메모이제이션(Memoization)이란 동적 계획법(Dynamic programming)의 핵심 기술로 동일한 계산을 반복해야 할 때, 이전에 계산한 값들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법입니다. 보통 예시로 피보나치 수열을 사용합니다.
피보나치 수열
피보나치 수열(Fibonacci sequence)은 제0항을 0, 제1항을 1로 두고, 제2항부터는 바로 앞의 두 수를 더한 수로 놓습니다. 제0항부터 제10항까지 표현하면 다음과 같습니다.
이는 C 언어에서 재귀 함수를 사용해서 다음과 같이 구현할 수 있습니다.
int fibonacci(int n) {if (n == 0)return 0;else if (n == 1)return 1;elsereturn fibonacci(n - 1) + fibonacci(n - 2);}
입력받은 n을 더 작은 단위인 과 로 나누고 나눠진 단위를 더 작은 단위로 다시 나눠서 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
배열에 저장합니다.
저장하는 작업은 한 번만 수행하면 다음에 같은 연산이 나왔을 때 연산량을 줄일 수 있습니다.
정리
동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나눠서 푸는 방법입니다. 예시로 들었던 피보나치 수열을 생각하면 좋습니다. 여기에 메모이제이션을 통해 다른 공간을 만들어 이용하면 더욱 빠르게 문제를 해결할 수 있습니다. 피보나치 수열을 다시 예로 들면 시간 복잡도가 걸리던 문제를 시간 복잡도로 풀 수 있습니다.