[프로그래머스 1단계] 알고리즘 3. 피보나츠 수열

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 3. 피보나츠 수열을 작성하시오

#include<iostream>

using namespace std;

long long fibonacci(int n)

{

return 0;

}

int main()

{

int testCase = 10;

long long testAnswer = fibonacci(testCase);

cout<<testAnswer;

}

풀이 : 일반적으로 피보나츠 수열은 재귀함수로 풀 수 있다. 피보나츠 수열은 f(0) = 0 f(1) = 1이고 f(n) = f(n-1) + f(n-2) (n>=2) 이다. 따라서 재귀함수로는 이렇게 작성할 수 있다.

long long fibonacci(int n)

{

if(n <= 1)

return n;

return fibonacci(n-1) + fibonacci(n-2);

}

그러나 이렇게 하면 프로그래머스로 제출해본 결과 시간 초과때문에 틀린것으로 간주된다. 왜냐하면 이것은 n이 커질수록 기하급수적으로 문제를 푸는 시간이 늘어나기 때문이다. 그렇다면 어떻게 해야 할까? 동적 프로그래밍의 메모이제이션 기법을 사용할까 한다. 메모이제이션이란 어떤 데이터 공간안에 결과들을 저장해놓고 만약 그 값이 호출된다면 이 공간을 이용하는 일종의 캐싱기법이다. 메모이제이션을 적용한 피보나츠 함수의 본체이다.

long long fibonacci(int n)

{

  long long memo[n]; //메모이제이션 공간 생성

  memo[0] = 0;         //f(0) = 0

  memo[1] = 1;         //f(1) = 1

  

  //f(n) = f(n-1) + f(n-2) [n >= 2]

  for(int i=2; i<=n; i++)                    

      memo[i] = memo[i-1] + memo[i-2];            

return 0;

}

컬렉션인 vector를 사용하고 싶다면 다음과 같이 작성할 수도 있다.

long long fibonacci(int n)

{

  vector<long long>memo;

  memo.push_back(0);

  memo.push_back(1);

  for(int i=2; i<=n; i++)

      memo.push_back(memo.at(i-1) + memo.at(i-2));

return 0;

}

다음은 내가 푼 전체 코드이다.

#include<iostream>

#include<vector>

using namespace std;

// 1. 일반적인 재귀함수

// long long fibonacci(int n)

// {

//   return (n<=1) ? n : (fibonacci(n-1) + fibonacci(n-2));

// }

// 2. 배열을 이용한 메모이제이션

// long long fibonacci(int n)

// {

//   long long memo[n];

  

//   memo[0]=0;

//   memo[1]=1;

  

//   for(int k=2; k<=n; k++)

//     memo[k] = memo[k-1] + memo[k-2];

  

//   return memo[n];

// }

// 3. 벡터 사용한 메모이제이션

long long fibonacci(int n)

{

  vector<long long> memo;

  

  memo.push_back(0);

  memo.push_back(1);

  

  for(int k=2; k<=n; k++)

    memo.push_back(memo.at(k-1) + memo.at(k-2));

  

  return memo.at(n);

}

int main()

{

int testCase = 5;

long long testAnswer = fibonacci(testCase);

cout<<testAnswer;

}