피보나치( Fibonacci )란?

1 1 2 3 5 8 13 21 ...

• 피보나치 수열이란 이번 항의 숫자가 이전 두 항의 숫자를 더한 값이 되는 수열을 말합니다.

피보나치 풀이

#include<iostream>
#include<unordered_map>

int RecursiveFibo(int number){
  // 메모이제이션을 위한 hash_map
  static std::unordered_map<int,int> m;

  if(number <= 1)
      return number;

  auto iter = m.find(number);
  if(iter != m.end()){
      return iter->second;
  }

  int result = RecursiveFibo(number - 1) + RecursiveFibo(number - 2);
  m.insert(std::make_pair(number,result));
  return result;
}

int main(){
    int number;

    std::cin >> number;

    std::cout << RecursiveFibo(number);

    return 0;
}

• hash map을 둠으로써 이전에 수행했던 계산 결과를 input 값과 맵핑하여 저장합니다. 이후 동일한 input 값이 들어올 경우 hash map에서 이전에 계산했던 값인지 확인하여 불필요한 반복적인 로직 수행을 방지합니다.

메모이제이션( Memoization )

• 메모이제이션( Memoization )은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.