메모이제이션

정의 :

어떠한 문제에서 어떤 값을 구하는 데 그 이전의 값이 필요할 때, 한 번 구한 값을 또 다시 구하지 않기 위해 값들을 저장해 놓는 방법

캐시(cache)에 이미 계산한 값을 저장해 둔다.

구현하는 방법

: 캐시 배열 생성해 각 입력에 대한 반환 값을 저장한다.

함수 호출 시 배열에 접근해 값이 저장되어 있는지 확인한 후 저장되어 있다면 사용, 저장되어 있지 않다면 새로 저장

​

입력이 고정되어 있을 때 그 결과가 항상 같은 함수의 경우에만 적용할 수 있다.

작성 코드

#include<iostream>
using std::cin;
using std::cout;

int fibonacci(int n);
int data[200]={0,};
const int MODULE=10009;

int main()
{


  int N(0),ans(0);

  cin >> N;

  if(N<=200)

  {

     ans=fibonacci(N);
     cout << ans;
  }
}


int fibonacci(int n)
{
  int & ret = n;
  if(n<=2)
  {
     return 1;
  }

  if(data[n]!=0)
   {
    return data[n]%MODULE;
   }

   else
   {
     data[n]= fibonacci(n-2)+ fibonacci(n-1);
     return data[n]%MODULE;
   }
}