[백준 #2747] 피보나치 수 - C

사실 피보나치 수열과 관련된 문제는 지난 피신 때 재귀를 사용해서 푼 적이 있다.

피보나치 수열은 모든 항이 앞선 두 항의 합으로 이루어진 수열이기 때문에 일반화가 쉬워서 재귀를 사용하면 깔끔하고 짧은 코드를 짤 수 있을 것이라고 생각했다.  

#include <stdio.h>

int fib(int n)
{
	if (n < 0)
		return (-1);
	if (n == 0)
		return (0);
	if (n == 1 || n == 2)
		return (1);
	return (fib(n - 2) + fib(n - 1));
}

int main(void)
{
	int n = 0;
	int result;
	scanf("%d", &n);

	result = fib(n);
	printf("%d", result);
}

그래서 위와 같이 코드를 작성해서 제출했더니

 

코드는 짧았으나 시간은 짧지 못했다...

시간 초과가 나왔다. 

시간복잡도를 간과했던 것이다.

 

피보나치 수열의 세 번째 항을 구하기 위해서는 첫 번째와 두 번째 항의 값이 필요하다.

네 번째 항을 구하기 위해서는 두 번째와 세 번째 항의 값이 필요한데,

따로 메모리에 값을 저장하지 않는 이상

네 번째 항을 구하기 위해 필요한 세 번째 항의 값을 구하기 위해서는

다시 세 번째 항을 구하는 과정을 거쳐야 한다.

 

즉, 어떤 항을 구하기 위해서는 그 항을 구하기 위해 필요한 모든 항의 값을 매번 새로 구해야한다는 뜻이다.

 

위의 트리와 같이 재귀 함수를 사용하면 피보나치 수열의 경우 n번째 항을 구하기 위해

n-1과 n-2 각각의 경우에 새로 재귀 호출을 하기 때문에 시간복잡도가 O(2^n)이 된다.

코드는 깔끔할지 몰라도 상당히 비효율적인 시간복잡도를 가진다.

 

이러한 시간복잡도를 줄이기 위해 재귀 함수 대신 반복문을 사용해봤다.

#include <stdio.h>

int fib(int n)
{
	if (n < 0)
		return (-1);
	if (n == 0)
		return (0);
	if (n == 1 || n == 2)
		return (1);

	int a = 1;
	int b = 1;
	int i = 3;
	while (i <= n)
	{
		int c = a + b;
		a = b;
		b = c;
		i++;
	}
	return (b);
}

int main(void)
{
	int n = 0;
	int result;
	scanf("%d", &n);

	result = fib(n);
	printf("%d", result);
	return (0);
}

a == n - 2

b == n - 1

c == n

으로 생각해서 변수를 설정해주고

c에 a와 b의 합을 대입한 후 인덱스를 한 칸 씩 뒤로 옮겨주었다.

이 경우에는 n만큼 while문을 돌면 결과를 얻을 수 있기 때문에

시간복잡도가 O(N)으로 줄어들게 된다.

 

동적 프로그래밍 카테고리 안에 포함된 문제라 반복문보다는 DP로 푸는 게 더 적합했겠지만

당장 생각나는 게 반복문밖에 없었다. DP에 조금 더 익숙해지면 새로운 방식으로 풀어봐야겠다.