피보나치 수(Algorithm)

아이디어!

첫 두항이 0, 1이고

F(n)=F(n-1)+f(n-2), 즉 이전 두 항의 합을 현재 항으로 표기해 주면 된다!

적용

1. 재귀(비효율적)

• 시간 복잡도: O(N^2)
• 중복호출이 많이 발생하기 때문에 비효율적임!

#include <bits/stdc++.h>
using namespace std;
long long fib(int n) {
	if (n <= 1) return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	cout << fib(n);
}

 

2. dp활용

• 시간 복잡도: O(N)
• dp배열에 특정 인덱스일 경우의 값을 저장해두고 사용하기!

#include <bits/stdc++.h>
using namespace std;
long long dp[100];

long long fib(int n) {
	if (n <= 1) return n;
	if (dp[n] != -1) return dp[n];
	return dp[n] = fib(n - 1) + fib(n - 2);
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
	int n;
	cin >> n;
	memset(dp, -1, sizeof(dp));
	cout << fib(n);
}

 

3. 행렬 거듭제곱

• 시간 복잡도: log(N)
• 행렬과 분할정복을 이용한 거듭제곱을 활용하여서 빠르게 해결가능하다.

피보나치 수는 위와 같은 점화식을 따르게 되는 데 이를 행렬 형식으로 나타내면 다음과 같이 나타난다.

행렬을 배운다면 이 식을 쉽게 이해할 수 있기 때문에 행렬을 공부하고 오는 것을 추천한다.

다음은 식을 일반화하게 되면 나오게 되는 결과이다!

이때 N이 1e9,1e10...처럼 커질 수 있기 때문에 분할정복을 활용한 거듭제곱을 활용해 준다면 O(log n)의 시간으로 문제를 해결할 수 있다.

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

vector<vector<long long>> multiply(vector<vector<long long>> A, vector<vector<long long>> B) { //행렬 계산
    vector<vector<long long>> result(2, vector<long long>(2, 0));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return result;
}

vector<vector<long long>> power(vector<vector<long long>> A, long long exp) { //분할정복을 이용한 거듭제곱
    vector<vector<long long>> result = {{1, 0}, {0, 1}}; //단위 백터 => 모르면 행렬 공부!
    while (exp) {
        if (exp % 2) result = multiply(result, A);
        A = multiply(A, A);
        exp /= 2;
    }
    return result;
}

int main() {
    long long n;
    cin >> n;
    if (n == 0) { 
        cout << "0\n";
        return 0;
    }
    
    vector<vector<long long>> fib_matrix = {{1, 1}, {1, 0}};
    vector<vector<long long>> result = power(fib_matrix, n - 1);
    
    cout << result[0][0]; //F(N)출력
}