피보나치수열의 표현 및 최적화

1. 일반적인 표현방법

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

장점: 코드가 직관적이고 이해가 쉬움 

단점: 똑같은 연산을 여러번 함으로써 굉장히 비효율적이고 함수가 호출될 때 또다른 함수2개를 호출하므로 연산시간이 길어짐

깊이가 2의 제곱꼴로 깊어짐(1->2->4->8->16 . . )

시간복잡도: 연산의 횟수가 2의 거듭제곱꼴로 지속되므로 O(2^N)

2. 최적화 기법 1 : 동적프로그래밍

핵심 : 딱 한번만 계산하고 저장된 값(배열에 담음)을 호출만 한다.(메모이제이션 기법)

(위의 그림에서 f(n-5)는 7번호출되므로 메모이제이션기법으로 한번만 계산함)

시간복잡도 : 기존에 함수호출의 깊이가 깊어질수록 2의 N승씩 연산했는데, 메모이제이션으로 단 한번씩만 계산하므로 O(N)

코드

#include<iostream>
using namespace std;
long long dp[50];
long long func(long long x);
int main()
{
	cout << "50번째 피보나치 수열은" << endl;
	cout << func(50) << "입니다." << endl;

}
long long func(long long x)
{
	if (x <= 2)return 1;
	//저장된 값이라면 바로 값을 리턴!
	if (dp[x] != 0)
		return dp[x];
	dp[x] = func(x - 1) + func(x - 2);
	return dp[x];
}

결과

3. 최적화 기법 2 : 행렬의 성질 이용(분할 정복)

아이디어: 2*2크기의 행렬에 피보나치수열을 표현하여 행렬곱연산(거듭제곱 연산)으로 표현하고싶다.

핵심: 분할정복 기법으로, 일단 잘게 나누고, 나눠진 값들을 합쳐서 최종값을 구함

n번째 피보나치 수열 Fn을 행렬로표현하기

10번째 피보나치 구하기

1단계-> 10번째 피보나치 분할

2단계-> 5번째 피보나치 분할(홀수이므로 제곱연산때처럼 4번째 피보나치*첫번째 피보나치로 나눔)

3단계-> 4번째 피보나치 분할

3단계(마지막)-> 2번째 피보나치 분할

모두 나눴으니 이제 거꾸로 계산하며 합치면 됨(분할->정복)

결과

시간복잡도: n번째 피보나치가 n/2번째피보나치의 제곱->n/4번째 피보나치의 제곱 ...순으로 나눠지므로 최초의 행렬을 logN회 제곱하면 되므로 O(logN)

코드

#include<iostream>
using namespace std;
struct M
{
	long long data[2][2];
};
long long func(int x);
M divide(M a, int n);
M multiply(M a, M b);
int main()
{
	cout << "46번째 피보나치 수는" << endl;
	cout << func(46) << "입니다." << endl;
}
long long func(int x)
{
	M a;
	//F(1)설정
	a.data[0][0] = 1, a.data[0][1] = 1;
	a.data[1][0] = 1, a.data[1][1] = 0;
	//분할
	a = divide(a, x);
	//F(n)출력)
	return a.data[0][1];
}
M divide(M a, int n)
{
	if (n > 1)
	{
		//n=1이 될때 까지 분할한다.(분할)
		a = divide(a, n / 2);
		//분할된 행렬을 다시 곱함(정복)
		a = multiply(a, a);
		//n이 홀수면
		if (n % 2 == 1)
		{
			M b;
			b.data[0][0] = 1, b.data[0][1] = 1;
			b.data[1][0] = 1, b.data[1][1] = 0;
			//구한 a와 f(1)곱해줌.
			a = multiply(a, b);
		}
	}
	return a;
}
M multiply(M a, M b)
{
	M c;
	//행렬곱셈
	c.data[0][0] = a.data[0][0] * b.data[0][0] + a.data[0][1] * b.data[1][0];
	c.data[0][1] = a.data[0][0] * b.data[0][1] + a.data[0][1] * b.data[1][1];
	c.data[1][0] = a.data[1][0] * b.data[0][0] + a.data[1][1] * b.data[1][0];
	c.data[1][1] = a.data[1][0] * b.data[0][1] + a.data[1][1] * b.data[1][1];
	return c;
}

코드가 어려울 수 있는데, 노트에 직접 적어보면 분할 정복의 과정이 보일겁니다.

결과