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;
}코드가 어려울 수 있는데, 노트에 직접 적어보면 분할 정복의 과정이 보일겁니다.
결과
