[피보나치] 피보나치 DP방식 코드

C++ 사용, 스마트 포인터 및 STL Map 컨테이너 사용.

재귀호출을 이용한 피보나치 수열의 n번째 값을 리턴 하는 함수이다.

STL Map 컨테이너를 사용하여 결과 값을 저장하고 중복된 계산을 하지 않는 동적 계획 방식을 사용하여 속도를 줄였다.

 

// n은 얻고자 하는 인덱스, pDpMapPtr은 Map의 포인터로써 입력 하지 않아도됨

int Fibo( int n, std::shared_ptr<std::map<int, int>> *pDpMapPtr = nullptr )
{
 if( 1 >= n )
  return 0;

 std::shared_ptr<std::map<int, int>> stSharedPtr;
 if( nullptr == pDpMapPtr )
 {
  auto map = new std::map<int, int>();
  map->emplace( std::map<int, int>::value_type(2, 1) );
  stSharedPtr.reset( map );
  pDpMapPtr = &stSharedPtr;
 }
 else
  stSharedPtr = *pDpMapPtr;

 auto map = stSharedPtr->find(n);
 if( stSharedPtr->end() == map )
 {
  map = stSharedPtr->emplace( std::move( std::map<int, int>::value_type( n, Fibo( n - 2, &stSharedPtr ) + Fibo( n - 1, &stSharedPtr ) ) ) ).first;
 }
 return map->second;
}

 

void main()

{

cout << Fibo(10) << endl;

}

 

일반 적인 재귀 호출과 비교 했을때, 수십배 빠른성능을 보인다.

N이 커질 수록 갭은 더 커진다.

함수 호출 전에 위의 공유 포인터를 먼저 만들고 사용하면, 위 함수를 여러번 호출하는 경우( ex) Fibo(5); Fibo(4); 이런식으로 반복호출 될 경우 ) 더 빠른 성능을 보여준다.