재귀 (7) - 메모이제이션 (Memoization)

1. 메모이제이션 (Memoization)

Memoization은 앞서 Fibonacci Series 포스트에서 언급했던 재귀함수의 중복호출 문제를 보완할 수 있는 방법이다. 말 그대로 함수의 결과값을 배열등의 자료구조에 메모해놓는 것이다.

 

[그림] 재귀호출의 중복 문제

 

위 그림을 보면 fib(2) 2번, fib(1) 3번, fib(0) 2번 등장하였다. 아직 계산을 하지 않았을 땐 이 값을 모르지만 한번 계산을 하여 값을 알게된다면 두번 세번씩이나 호출할 필요없다. 만약 n이 5가 아니라 45와 같이 큰수라면 이러한 방식으로 구현하면 굉장히 느린 계산 속도를 보여준다.

 

2. 소스 코드

#include <stdio.h>
#include <time.h>

#define max 500

int memo[max];

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

int fibonacci_memo(int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != 0) return memo[n]; // 이미 메모되있는 값이 있으면 꺼내옴.
    else memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2); // memo 에 저장
    return memo[n];
}

void printTime() {
    time_t now;
    time(&now);
    printf("%s", asctime(localtime(&now)));
}

int main() {
    printTime();
    printf("%d\n", fibonacci_memo(45));
    printTime();
    printf("%d\n", fibonacci(45));
    printTime();
    
    /*
    Tue Feb 04 13:12:29 2020
    1134903170
    Tue Feb 04 13:12:29 2020
    1134903170
    Tue Feb 04 13:12:33 2020
    */

    return 0;
}

 

위 소스코드의 fibonacci_memo를 보면 메모배열에 아직 메모가 되지 않은 요소는 fibonacci 함수를 이용하여 값을 저장하고, 만약 메모가 되어있는 값이라면 재귀호출을 하지 않고 메모된 값을 꺼내와서 리턴한다. 때문에 fibonacci의 경우 4초나 소요되었지만 fibonacci_memo는 1초도 소요하지 않고 같은 결과값을 출력하였다.

 

모든 소스코드는 Github에서 확인할 수 있습니다.

gusdnd852/TIL

 

3. Reference