알고리즘(C++) - 피보나치 수열

피보나치수열:

첫째항은 0 둘째 항이 1이며 그다음 항부터는 바로 앞 두항의 합이다.

ex) 0,1,1,2,3,5,8,13,21,34,55,89 ㆍㆍㆍㆍㆍㆍ

 

#include <iostream>
#include <vector>
using namespace std;
int fibo(int n);
int main()
{
	int n;
	cin >> n;
	cout << fibo(n);
}
int fibo(int n)
{
	int result;
	if (n < 2) //F[0]=0, F[1]=1 저장
	{
		return n;
	}
	else
	{
		result= fibo(n - 1) + fibo(n - 2); //F[n]=F[n-1]+F[n-2]
	}
	return result;
}

재귀로 만든 피보나치 수열이다.

이 코드는 비효율적인 코드이다. 왜 일까?

재귀로 만든 피보나치의 시간 복잡도는 exponentially하다.

→그냥 안 좋다는 뜻이다.

왜 비효율적일까?

이유는 재귀를 사용해서 피보나치수열을 계산하면 중복된 계산이 있다는 점이다.

예를 들어

1. F(4)를 구하기 위해서는 F(3)과 F(2)가 필요하다.
2. F(3)을 구하기 위해서는 F(2)과 F(1)이 필요하다.
3. F(2)를 구하기 위해서는 F(1)과 F(0)이 필요하다.

여기서 중복계산은 몇 번 일어날까?

재귀로 푼다면 F(3)을 구하는데 fibo(2), fibo(1), fibo(0)이 호출됐다.

F(2)를 구하는데 fibo(2), fibo(1), fibo(0)이 호출됐다.

피보나치를 재귀적으로 푼다면 필연적으로 중복계산이 일어날 수밖에 없다.

그러면 이러한 피보나치수열을 구할 때 어떻게 하면 더 효율적으로 짤 수 있을까?

 

만약 F(n)을 구하고 F(n)이 필요할 때 꺼내서 쓴다면

→ 중복 계산을 피할 수 있을 것이다.

이렇게 계산을 하고 계산 값을 저장해서 필요할 때 꺼내서 쓰는 것을 memoization이라고 한다.

#include <iostream>
#include <vector>
using namespace std;
int fibo(int n);
vector<int>F;
int main()
{
	int n;
	cin >> n;
	cout << fibo(n);
}
int fibo(int n)
{
	int result;
	F.push_back(0); //F[0]=0
	F.push_back(1); //F[1]=1
	if (n < 2) //F[0]=0, F[1]=1 저장
	{
		return n;
	}
	else
	{
		for (int i = 2; i <= n; i++)
		{
			F.push_back(F[i - 1] + F[i - 2]); 
            //F[i-1],F[i-2]를 다시 계산하지 않고 저장된 값을 꺼내서 씀.
		}
	}
	return F[n];
}

이처럼 알고리즘을 구현할 때는 시간 복잡도와 공간 복잡도를 고려해서 효율적으로 짜는 것이 중요하다.

시간 복잡도와 공간 복잡도는 다음에 할 것이다.

 

출처:대학교 강의자료,알고리즘 기초 교재