[백준] 1003번 피보나치 함수 / C++

#문제

#풀이

#include <iostream>

using namespace std;

int fibonacci(int n)
{
	if (n == 0)
	{
		return 0;
	}
	else if (n == 1 || n < 0)
	{
		return 1;
	}
	else
	{
		int prev1 = 0;
		int prev2 = 1;
		int fn = 0;

		for (int i = 1; i < n; ++i)
		{
			fn = prev1 + prev2;

			prev1 = prev2;
			prev2 = fn;
		}

		return fn;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t, n;
	cin >> t;

	while (t--)
	{
		cin >> n;

		cout << fibonacci(n - 1) << " " << fibonacci(n) << '\n';
	}

	return 0;
}

#정리

n번째 피보나치 수열이 불리는데, 0과 1이 몇번이 호출되는지 차례로 출력하는 문제. 재귀 함수로 된 Fibonacci 함수 예시를 제공한다. 처음 시도에서는 변수 x, y를 만들어 각각 피보나치 함수 내 if (n == 0)과 if (n == 1)에서 증가연산을 하고 호출되는 갯수를 출력했다. 답은 맞았지만 시간초과로 문제는 틀렸다. 하지만 0의 호출 갯수는 Fibonacci(n - 1), 1의 호출 갯수는 Fibonacci(n)과 동일함을 알 수 있었다. 그리고 피보나치 수열을 반복문으로 작성할 경우 O(n)의 시간복잡도를 가지는데, 재귀함수의 경우 O(2^n)의 시간 복잡도를 가지기 때문에 성능 차이가 굉장히 크다. 코드를 반복문으로 변경하여 해결했다.

#문제

#풀이

#정리

Enjoy Reading This Article?