메모이제이션 Memoization(간단 정리)

메모이제이션은 연산에 있어서 중복된 연산을 진행할 때 이러한 중복된 연산을 제거하기 위해 사용된다.

처음에 설명을 들을 때는 이미 계산한 값을 저장해놓고 다시 불러서 사용한다 어쩌구저쩌구~

이러한 설명보다는 직접 코드를 구현해서 보면 이해가 쉽다.

 

< 피보나치 수열 재귀함수 이용 >

#include <iostream>
#include <string.h>

using namespace std;

int data[30];

int dp(int n){

    if(n<=2)
   	 return 1;
     
    data[n]=dp(n-1)+dp(n-2);
    cout << "data[" << n << "] : " << data[n] << endl;
    return data[n];
}
int main()
{
    memset(data,0,sizeof(data));
    cout << dp(10) <<'\n';
    return 0;
}

 

위의 코드를 보면 피보나치 수열에 대해서 구현해 놓은 코드이다.

10번째에 피보나치 수열 값이 무엇인지 계산해주는데 거기까지 가려면

dp(10) = dp(9) + dp(8)

dp(9) = dp(8) + dp(7)

dp(8) = dp(7) + dp(6)

이런식으로 재귀함수에 의해 쫘라락 연산이 진행될 것이다.

그래서 마지막에 n이 2보다 작은 경우인 dp(1)과 dp(2)가 1을 리턴하면서 계산이 다시 좌라락 진행될 것이다.

위의 내용이 자세한 것은 아니지만 저 수식들만봐도 중복되는 함수 호출이 벌써 여러개 있다.

-> dp(9) : 2개, dp(8) : 3개 dp(7) : 2개 

 

 

 

 

 

 

물론 당연히 호출이 되야하지만 만약에 이렇게 사용한다면 어떨까?

< 피보나치 수열 재귀함수 + 메모이제이션 이용 >

#include <iostream>
#include <string.h>

using namespace std;

int data[30];

int dp(int n){

    if(n<=2)
        return 1;
    if(data[n]!=0){
        return data[n];
    }
    else{
        data[n]=dp(n-1)+dp(n-2);
        cout << "data[" << n << "] : " << data[n] << endl;
        return data[n];
    }
}
int main()
{
    memset(data,0,sizeof(data));
    cout << dp(10) <<'\n';
    return 0;
}

위의 코드와 다른 점은 if 문이 하나 더 등장했다는 것이다.

내용은 data[n]에 값이 존재하면 그 값을 그대로 리턴해라 이다.

즉, 값이 있으면 굳이 그 값을 구하기위한 연산을 하지않고 있는 값을 그대로 반환하겠다는 의미이다.

이와 같은 진행을 하게 되면 다수의 중복 연산을 제거할 수 있다.

눈으로 보고싶다면 위의 코드 두개를 직접 실행해보면된다.

 

 

 

 

 

누가봐도 연산의 차이가 난다는 것을 알 수 있다. 이는 굉장히 중요하다.

지금은 겨우 10개짜리를 진행했지만 크기가 클 수록 굉장히 많은 중복을 줄일 수 있게된다.

절대 잊지말자!! 포인트는 쉽게 말해 재활용이다!