1. 개요
Memoization[1]컴퓨터 알고리즘 용어로, 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다. 동적 계획법의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식이다. 메모아이제이션은 아무래도 학술적인 용어라 실제 현장에서는 캐싱(caching)이라는 단어를 더 많이 사용한다.
2. 예시
가장 흔하게 사용되는 예시는 피보나치 수열이다. 피보나치 수열을 구하는 재귀함수를 fib 라고 하자. 예를 들어 4번째 피보나치 수열은 fib(4), 즉 fib(4) = fib(3) + fib(2) 이다. 다시 fib(3)는 fib(2) + fib(1)이므로 결국 fib(4) = fib(2) + fib(1) + fib(2)이다. 이런 과정을 반복해서 표현한 최종적인 fib(4)는 fib(1) + fib(0) + fib(1) + fib(1) + fib(0)와 같다. 아래의 그림을 통해 구체적으로 시각화해 보자.위와 같이 5번째 피보나치 수열을 구하는 데 함수 f를 호출하는 횟수는 총 15번이다. 위의 예시에서 중복해서 계산하는 값만 따져 봐도 fib(3)이 2번, fib(2)가 3번, fib(1)을 5번, fib(0)을 3번 계산한다. 15번의 계산 중에 무려 11번을 중복해서 계산하는 셈이다. 비록 위 예시는 비교적 작은 값을 제시했지만, 피보나치 수열을 순진(naive[2])한 방법으로 구할 경우 시간복잡도는 피보나치 수열의 값에 따라 폭발적으로 증가한다. 즉 O(1.6N)다.[3]
그러나, 이미 문제를 풀어봤는지 확인하면서 같은 문제의 풀이는 재활용하는 형태로 문제를 풀이하면 그림과 같이 9번의 계산만을 수행하면 되며, 이 중에서도 2번은 계산 없이 기존에 풀이했던 동일한 문제의 정답을 가져오기만 하면 된다. 이처럼 하위 문제에 대한 정답을 계산했는지 확인해가며 하향식으로 문제를 자연스럽게 풀어나가는 방식을 메모이제이션(Memoization)이라고 한다. 메모라이제이션(Memorization)이 아니다. 주의! 또한 상향식 풀이는 타뷸레이션(Tabulation)이라는 용어로 별도로 지칭한다.
2.1. 순진한 방법
순진한 방법을 C++로 구현해 보면 다음과 같다. [4]#!syntax cpp
#include <iostream>
uint64_t fibonacci(uint64_t number)
{
if(number < 2)
{
return number;
}
// f(4) = f(3) + f(2) 임을 상기하자.
return fibonacci(number - 1) + fibonacci(number - 2);
}
int main(int argc, const char *argv[])
{
using namespace std;
uint64_t number;
cin >> number;
cout << fibonacci(number);
return 0;
}
위의 코드는 [다이어그램]과 동일한 방법으로서 계산의 중복이 발생하고 따라서 계산 결과를 산출하기까지 많은 시간이 소요된다.
2.2. 메모이제이션을 활용한 방법
이번에는 메모이제이션 기법을 활용해 피보나치 수열을 구해 보자.#!syntax cpp
#include <array>
#include <iostream>
using namespace std;
// 피보나치 수는 94번째부터 8 byte의 자료형으로 표현할 수 없을 만큼 큰 값이다.
// size_t는 표준 C++의 메모리 포인터 크기이며 32 bit 환경에서 4 byte, 64 bit 환경에서 8 byte이다.
// 주로 메모리의 크기나 위치를 지정할 때 사용한다.
// uint64_t는 표준 C++의 8 byte 크기의 부호 없는 정수형이다.
// CPU의 연산 단위와 상관없이 고정된 크기이므로 64 bit 환경에서만 size_t와 크기가 같다.
constexpr size_t array_size = 92;
array<uint64_t, array_size> memory = { 0, }; // 계산한 피보나치 수열을 메모이제이션할 고정된 크기의 배열
uint64_t fibonacci(size_t number)
{
uint64_t result;
if(number < 2)
{
result = number; // 수열의 0번째와 1번째 수는 명백하므로 계산할 필요가 없다.
}
else
{
size_t index = number - 2;
if(memory[index]) // 이미 계산해서 기억하고 있는 피보나치 수열이라면...
{
result = memory[index]; // ...메모리에서 꺼내서 돌려주자.
}
else // 한 번도 계산한 적이 없다면...
{
result = memory[index] = fibonacci(number - 1) + fibonacci(number - 2); // ...계산한 후 배열 memory에 기억해 두자
}
}
return result;
}
int main(int argc, const char *argv[])
{
size_t number;
cout << "본 예제는 0번째부터 93번째까지의 피보나치 수열만 계산 가능하도록 설계되었습니다\n몇 번째: ";
cin >> number;
cout << fibonacci(number);
return 0;
}
혹은
#!syntax cpp
#include <array>
#include <iostream>
using namespace std;
// 피보나치 수는 94번째부터 8 byte의 자료형으로 표현할 수 없을 만큼 큰 값이다.
// size_t는 표준 C++의 메모리 포인터 크기이며 32 bit 환경에서 4 byte, 64 bit 환경에서 8 byte이다.
// 주로 메모리의 크기나 위치를 지정할 때 사용한다.
// uint64_t는 표준 C++의 8 byte 크기의 부호 없는 정수형이다.
// CPU의 연산 단위와 상관없이 고정된 크기이므로 64 bit 환경에서만 size_t와 크기가 같다.
constexpr size_t array_size = 94;
array<uint64_t, array_size> memory = { 0, 1, }; // 계산한 피보나치 수열을 메모이제이션할 고정된 크기의 배열
uint64_t fibonacci(size_t number)
{
uint64_t result;
if(!number < || memory[number]) // 이미 계산해서 기억하고 있는 피보나치 수열이라면...
{
result = memory[number]; // ...메모리에서 꺼내서 돌려주자.
}
else // 한 번도 계산한 적이 없다면...
{
result = memory[number] = fibonacci(number - 1) + fibonacci(number - 2); // ...계산한 후 배열 memory에 기억해 두자.
}
return result;
}
int main(int argc, const char *argv[])
{
size_t number;
cout << "본 예제는 0번째부터 93번째까지의 피보나치 수열만 계산 가능하도록 설계되었습니다\n몇 번째: ";
cin >> number;
cout << fibonacci(number);
return 0;
}
미리 구한 f(n)의 값을 메모리에 저장해서 다음에 또다시 f(n)을 계산해야 할 경우 그 과정을 생략할 수 있도록 설계한 위의 코드는 시간복잡도를 O(N)으로 줄인다. 메모리(Memo[])를 더 사용한 대가로 계산 시간을 획기적으로 단축한 것이다.
3. 타뷸레이션(Tabulation)
메모이제이션과 비슷하지만, 값을 미리 계산해둔다. 즉, 메모이제이션이 결과가 필요해질 때 계산한다면(Lazy-Evaluation) 타뷸레이션은 필요하지 않은 값도 미리 계산해둔다(Eager-Evaluation)는 차이가 있다. 초기화 오버헤드가 있지만 일단 계산해둔 값은 시간복잡도가 상수 시간(O(1))이 된다.#!syntax cpp
#include <array>
#include <iostream>
using namespace std;
// 피보나치 수는 94번째부터 8 byte의 자료형으로 표현할 수 없을 만큼 큰 값이다.
// size_t는 표준 C++의 메모리 포인터 크기이며 32 bit 환경에서 4 byte, 64 bit 환경에서 8 byte이다.
// 주로 메모리의 크기나 위치를 지정할 때 사용한다.
// uint64_t는 표준 C++의 8 byte 크기의 부호 없는 정수형이다.
// CPU의 연산 단위와 상관없이 고정된 크기이므로 64 bit 환경에서만 size_t와 크기가 같다.
constexpr size_t array_size = 94;
array<uint64_t, array_size> memory = { 0, 1, }; // 계산한 피보나치 수열을 저장할 고정된 크기의 배열
void init_fib(void)
{
int i;
for(i = 2; i < array_size; i++)
memory[i] = memory[i - 1] + memory[i - 2];
}
uint64_t fibonacci(size_t number)
{
uint64_t result;
assert(number < array_size);
return memory[number];
}
int main(int argc, const char *argv[])
{
size_t number;
init_fib();
cout << "본 예제는 0번째부터 93번째까지의 피보나치 수열만 계산 가능하도록 설계되었습니다\n몇 번째: ";
cin >> number;
cout << fibonacci(number);
return 0;
}
어떤 수가 소수인지 확인하기 위해서는 그 수의 제곱근보다 작은 소수로 나눠봐야 한다. 미리 이런 작은 소수를 구해서 테이블에 저장해 두면, 빠르게 계산해 볼 수 있다.