[피보나치 수열] 2가지 방법

알고리즘 테스트에서 거의 자주 나오는 것 중 하나는 피보나치 수열이다.

피보나치 수열에 대한 자세한 내용은 따로 검색해서 찾자!

 

피보나치 수열을 해결하는 방법은 2가지가 있다.

1) 재귀를 이용한다. (Recursion 개념 이용)

2) 재귀를 이용하지 않는다. (Memoization 개념 이용)

 

두 개의 코드를 간단히 구현하고 어떤 차이점이 있는지 시간 복잡도 측면에서 살펴보겠다.

#include <iostream>
#include <vector>

using namespace std;

// n의 범위에 따라 자료형을 변경한다.
vector<int> fibo;

// 재귀 방식
int FiboRecursion(int n)
{
  if(n == 0) return 0;
  else if(n == 1) return 1;
  return FiboRecursion(n - 1) + FiboRecursion(n - 2);
}

// 메모이제이션 방식
void FiboMemoization(int n)
{
  fibo[0] = 0, fibo[1] = 1, fibo[2] = 1;
  if(n == 0 || n == 1) return;
  
  for(int i = 3; i <= n; i++)
  {
    fibo[i] = fibo[i-1] + fibo[i-2];
  }
}

int main(void)
{
  int n = 0; // n번째 피보나치 수 찾기
  cin >> n;
  fibo.resize(n+1, 0);

  FiboMemoization(n);
  cout << "재귀 이용 값: " << FiboRecursion(n) << "\n";
  cout << "메모이제이션 이용 값: " << fibo(n) << "\n";
  return 0;
}

코드는 정말 간단하다!

메모이제이션 개념을 사용하면 배열의 중복되는 계산에 대해선 계산을 진행하지 않고 미리 저장해두어 꺼내오는 방식을 채택한 것이다.

재귀를 이용하면 N개의 depth에 대하여 각 노드가 2개씩 생겨 시간 복잡도는 O(2^N) 이지만

메모이제이션을 이용하면 N개에 대하여 시간 복잡도는 O(N)이다.