[BaekJoon 1003][⚪3] 피보나치 함수
❓ 문제
🎯 난이도
Silver ⚪3
🧠 풀이
1. 내 풀이 (DP)
- 알고리즘
Dynamic Programming
- 설명
DP 방식으로 피보나치 수를 구하는 방식이다.
40까지의 모든 피보나치 수의 0과 1의 수를 DP 방식으로 누적해가는 방식으로 원하는 값을 바로 출력할 수 있도록 하는 방식이다. Fibo라는 이름의 구조체를 만들어서 다른 구조체와의 합을 간단하게 해주는 연산자 오버로딩 함수를 만들어 처리했다.
DP로 피보나치 수들을 구하는 과정은 상수 시간이고, 입력값을 받아서 출력하는 O(1)를 N번 반복하는 과정만 유의미하므로 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
using namespace std;
struct Fibo
{
int iZero{};
int iOne{};
// Fibo 구조체 간의 더하기 연산자 오버로딩
Fibo operator+(const Fibo& tOther) const
{
return { iZero + tOther.iZero, iOne + tOther.iOne };
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
vector<Fibo> vecFibo(41);
vecFibo[0] = Fibo{ 1, 0 };
vecFibo[1] = Fibo{ 0, 1 };
// 40까지의 모든 피보나치 수 구하기
for(int i = 2; i < static_cast<int>(vecFibo.size()); ++i)
{
vecFibo[i] = vecFibo[i - 1] + vecFibo[i - 2];
}
while(iT--)
{
int iN{};
cin >> iN;
cout << vecFibo[iN].iZero << ' ' << vecFibo[iN].iOne << '\n';
}
return 0;
}
2. 추가 풀이 (수학적 규칙)
- 알고리즘
Mathematics
- 설명
수학적 규칙을 이용해 피보나치수를 구하는 방식이다.
모든 수는 결국 0과 1의 합의 집합이고, 이는 규칙을 만들게 된다. 각각의 피보나치 수와 0, 1의 수를 구해서 나열해보면 '0'의 수는 'DP[i - 1]'와 같고 '1'의 수는 'DP[i]'와 같다. 따라서 이 규칙을 이용해 문제를 풀 수 있게 된다.
위와 같은 방식으로 전체적인 시간 복잡도는 O(N)이다.
- 코드
내 풀이 코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int iT{};
cin >> iT;
vector<int> vecFibo(41);
vecFibo[0] = 0;
vecFibo[1] = 1;
// 40까지의 모든 피보나치 수 구하기
for(int i = 2; i < static_cast<int>(vecFibo.size()); ++i)
{
vecFibo[i] = vecFibo[i - 1] + vecFibo[i - 2];
}
while(iT--)
{
int iN{};
cin >> iN;
// iN == 0 일때만 예외 처리
if(iN == 0)
{
cout << "1 0\n";
}
// 규칙에 따라 출력
else
{
cout << vecFibo[iN - 1] << ' ' << vecFibo[iN] << '\n';
}
}
return 0;
}
💭 후기
보통 피보나치 수를 구할 땐 재귀적 방식을 많이 생각하지만, 사실 이 방식은 단점이 뚜렷하다. 구하려는 몇번째의 피보나치 수를 구하기 위해서 재귀를 반복하게 되면, 결국 '스택 프레임'의 용량이 꽉차게 되어서 스택 '오버플로우'가 발생할 수 있기 때문이다. 따라서 예외가 없다면 DP방식으로 하는 것이 가장 안전한 방법이라고 볼 수 있다.
Comments