메모이제이션 : 중복 연산 해결 (러시안 페인트공 알고리듬)

 이 포스팅에서는 메모이제이션을 논하려고 합니다. 메모이제이션은 중복되는 연산의 결과를 저장하여, 연산 횟수를 줄이는 소프트웨어 엔지니어링 기술입니다. 소프트웨어 개발 중에는 항상 하게 되는  선택이 cpu를 사용하는가 메모리를 사용하는가입니다. 이 기술은 컴퓨팅 리소스 중 cpu의 사용량을 줄이는 대신 메모리의 사용량을 늘려줍니다. 메모이제이션을 잘 사용하면 다양한 알고리듬을 가속화할 수 있는 아주 중요한 기술입니다.

 긴 글과 개념적인 설명은 여기서 마치겠습니다. 자세한 설명을 원하시면... 전공서적이나 위키피디아를 참고하세요.  여기선 간단한 예제로 설명하겠습니다. 사용하는 예제는 피보나치수열입니다. 피보나치 수열의 알고리듬 구조상 설계는 자연스럽게 재귀 호출이 되고, 메모이제이션을 이용하면 구동 시간을 크게 단축시킵니다. 자세한 설명은 이전 포스트를 참고해 주세요.

2021.03.22 - [Program Language and Algorithm] - C++를 이용한 피보나치 수열 구현 (fibonacci)

C++를 이용한 피보나치 수열 구현 (fibonacci)

추가로 피보나치수열을 메모이제이션 없이 구현하는 것은 일종의 러시안 페인트공 알고리듬입니다. 이것도 개념적인 부분은 이전 포스트를 참고해주세요.

2021.03.25 - [Program Language and Algorithm] - 러시안 페인트공 알고리듬

러시안 페인트공 알고리듬

그럼 서론은 마치고, 재귀 호출을 이용한 피보나치수열 예제입니다.

#include <iostream>
#include <vector>

using namespace std;

int fibonacci(int i){
    if(2 > i){
	return i;
    }

    return fibonacci(i-1) + fibonacci(i-2);
}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    cout << fibonacci(n) << endl;

    return 0;
}

이 코드를 이용했을 때 fibonacci함수의 호출 횟수는 어떻게 될까요? 전역 변수를 만들고 함수의 호출 횟수를 기록하겠습니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> nCall;

int fibonacci(int i){
    nCall[i]++;
    if(2 > i){
	return i;
    }

    return fibonacci(i-1) + fibonacci(i-2);
}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    long long tCount = 0ll;

    nCall.resize(n+1);

    for(int i = 0 ; n >= i ; i++){
	nCall[i] = 0;
    }

    cout << fibonacci(n) << endl;

    for(int i = 0 ; n >= i ; i++){
	if(0 == i%10){
	    cout << endl;
	}
	cout << nCall[i] << "\t";

	tCount += static_cast<long long>(nCall[i]);

    }
    cout << endl;

    cout << tCount << " times called" << endl;

    return 0;
}

 코드가 많이 길어지긴 했지만, 전역 변수의 초기화와 호출 횟수의 출력이 추가되었을 뿐입니다. 그럼 이 코드를 구동했을 때 결과를 아래 스냅숏으로 확인해보죠.

 두 가지 결과를 출력해 봅니다. 첫 번째는 f_5이고, 두 번째는 f_46입니다. 출력 값은 각각 5와 1,836,311,903 이군요. 이전 포스트에서 언급 한 바와 같이 32비트 정수형을 사용했을 때 최대 피보나치수열 값입니다. 재귀 호출을 이용한 위 예제에서 f_5가 fibonacci함수를 호출한 횟수는 15회입니다. f_46일 때는 5,942,430,145회입니다. 결과를 보면 fibonacci(1)은 수열의 값과 동일 횟수로 호출됩니다. 거기에 다른 호출까지 더해져 호출 횟수는 급증합니다. 이렇게 함수를 마구 호출하니 구동 시간이 길어질 수밖에 없죠.

 그럼 이번엔 메모이제이션을 이용하겠습니다. 피보나치수열의 값을 저장하기 위한 전역 변수를 만들고, 호출된 기록이 없는 경우에만 재귀 호출을 이용해서 값을 경신합니다.

#include <iostream>
#include <vector>

using namespace std;

vector<int> nCall;

vector<int> fibo;

int fibonacci(int i){
    nCall[i]++;
    if(-1 == fibo[i]){
	fibo[i] = fibonacci(i-1) + fibonacci(i-2);
    }
    return fibo[i];

}

int main(int argc, char ** argv){
    int n = atoi(argv[1]);

    long long tCount = 0ll;

    nCall.resize(n+1);

    fibo.resize(n+1);

    for(int i = 0 ; n >= i ; i++){
	nCall[i] = 0;
    }
    fibo[0] = 0;
    fibo[1] = 1;
    for(int i = 2 ; n >= i ; i++){
	fibo[i] = -1;
    }

    cout << fibonacci(n) << endl;

    for(int i = 0 ; n >= i ; i++){
	if(0 == i%10){
	    cout << endl;
	}
	cout << nCall[i] << "\t";

	tCount += static_cast<long long>(nCall[i]);

    }
    cout << endl;

    cout << tCount << " times called" << endl;

    return 0;
}

 수열이 갱신되었는지 확인해야 하는데 0은 0번째 수열의 값이기 때문에 -1로 초기화하고, 0번째와 1번째 수열은 초기화 때 갱신해 줍니다. 이후엔 함수 자체에서 fibo[i]가 -1인 경우에만 재귀 호출하고, 아니면 fibo[i]의 값을 반환하죠. 메모이제이션을 이용함으로 인해 구동 시간은 크게 감소됩니다. (정확한 비교는 이전 글을 참고해 주세요.)

 위 예제와 똑같이 f_5와 f_46의 결과를 출력해 봅니다. 결과는 당연히 재귀 호출만 이용한 결과와 동일합니다. 호출 횟수는 크게 감소합니다. f_5가 9회 f_46이 91회 이죠. 이 예제는 f_n에 대해서 정확히 2 * n - 1 회의 호출 횟수를 가집니다.

 두 예제의 호출 횟수를 비교해 보면 f_n에 대해서 재귀 호출을 이용하는 경우 f_n의 결과 값만큼의  fibonacci(1)의 호출이 이루어지고, 1이 아닌 i에 대해서 fibonacci(i)의 호출이 추가되어 호출 횟수가 급증합니다. 메모이제이션을 이용하면 전체의 호출 횟수가 2 * n - 1 이죠. 당연히 빠르게 결과를 얻을 수 있습니다.

 이렇게 메모이제이션은 중복 연산을 감소시킴으로써 알고리듬을 가속화시키는 기술입니다. 단, 가속화의 대가로 메모리를 사용하게 된다는 점은 유의해야 합니다.

 

그럼 이상 마치겠습니다.

 

감사합니다.