백준 10870, 피보나치 5

문제

 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

 

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

55

 

 피보나치 수열을 구하는 문제는 심심치 않게 나왔었다. 푸는 문제도 여러가지 있는 데, 대표적으로 지금 이 문제를 풀 방법인 재귀 함수의 형태로 구현하는 것과 동적 계획법을 이용하는 방법을 들 수 있다. 이 문제의 경우 n이 그렇게 크지 않아서 재귀를 쓸 수 있으나 추천하지는 않는다. 그 이유는 재귀로 구현할 시, n의 값에 비례하여 2^n 꼴로 연산량이 증가하기 때문이다.  그러나 이 문제에서는 재귀 함수를 사용하였다. 백준에서 추천하는 단계별로 문제를 풀고 있는데, 이 문제의 카테고리가 재귀였기 때문이다. 다음은 구현한 코드이다.

#include <iostream>

long long fibonacci(int num) {
	if (num == 0) {
		return 0;
	}
	else if (num == 1) {
		return 1;
	}
	else {
		return fibonacci(num-2)+ fibonacci(num-1);
	}
}

int main() {
	int num;
	std::cin >> num;

	std::cout << fibonacci(num);

	return 0;
}

 동적 계획법의 장점에 대해서 간단히만 언급하자면 과거의 값을 기억함으로써 재귀 함수의 형태는 유지하나 재귀 내에서도 연산량을 압도적으로 줄여주는 역할을 한다. 예를 들어 피보나치 수여 n 번째에 대한 값을 구함에 있어서 재귀만을 이용할 경우에는 (n-1)번째 수를 구하는 재귀함수와 (n-2)번째 수를 구하는 재귀함수를 구해야하는 반면 동적 계획법을 같이 사용하는 경우 (n-2)번째 수를 구하였다면, (n-1)번째 수를 구함에 있어서는 이미 (n-2)번 째 수와 (n-3)번 째 수를 모두 기억하고 있기에 그대로 사용하기만 하면된다. 

 문제가 어렵다기보다는 "아 재귀가 이런거구나" 정도를 익힐 수 있었다. 이 것으로 글을 마친다.