메모이제이션이란?📄

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) 시간 복잡도로 풀 수 있다.