[알고리즘/기초] 피보나치 수

알고리즘의 기초 이론 중 하나인 피보나치 수에 대하여 간단하게 기록한 글입니다.

 

정의

피보나치 수는 첫째 항, 둘째 항이 1이고 N번째 항이(N>=2) 직전 두 항의 합을 값으로 가지는 수열입니다.

 

1. 연습 문제

기본적인 피보나치 수 관련 문제입니다. 

2747번: 피보나치 수

 

1-1. 방법 (시간 초과)

재귀적인 방식으로 솔루션을 작성할 수 있습니다. 허나 이 방식으로는 연습 문제를 해결할 수 없습니다. 연습 문제의 시간 제한이 1초이기 때문입니다.

#include<iostream>
using namespace std;

int fib(int idx){
    if(idx==0) { return 0; }
    else if(idx==1) { return 1; }
    
    return fib(idx-1) + fib(idx-2);
}

int main(){
    int N, answer;
    cin >> N;
    
    answer = fib(N);
    cout << answer;
    
    return 0;
}

 

1-2. 방법

배열을 하나 만들어 반복문을 활용하여 연습 문제를 풀 수 있습니다.

#include<iostream>
using namespace std;

int fib[46] = {0, };

int main(){
    int N;
    cin >> N;
    
    fib[1] = 1;
    for(int i=2; i<= N; i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    cout << fib[N];
    
    return 0;
}

 

2. 연습 문제

첫 번째 연습 문제와 달리 분할 정복을 알고 있어야 해결할 수 있는 문제입니다.

11444번: 피보나치 수 6

 

출처

피보나치 수 - 위키백과, 우리 모두의 백과사전