시작 값과 끝 값으로 구성된 범위가 주어졌을 때, 그 범위 사이에 존재하는 피보나치 수의 총 개수를 O(log n) 시간 복잡도와 O(1) 공간 복잡도로 계산하는 방법을 알아봅니다.
피보나치 수란 무엇인가?
피보나치 수는 '피보나치 수열'로 알려진 숫자들의 나열로, 수열의 모든 새로운 숫자는 바로 앞에 있는 두 숫자의 합으로 정의됩니다.
이때 f(0) = 0, f(1) = 1은 고정된 값이며, 실제 계산은 세 번째 숫자부터 시작됩니다.
수열을 계산하는 데 사용되는 공식은 다음과 같습니다 −
Fn = Fn-1 + Fn-2
여기서,
F0 = 0, F1 = 1
예제
입력 − start = 6, last = 100 출력 − 수열 내 피보나치 수의 개수는 6개
설명 − 6과 100 사이의 피보나치 수는 8, 13, 21, 34, 55, 89이며, 총 개수는 6개입니다.
입력 − start = 0, last = 8 출력 − 수열 내 피보나치 수의 개수는 7개
설명 − 0과 8 사이의 피보나치 수는 0, 1, 1, 2, 3, 5, 8이며, 총 개수는 7개입니다.
프로그램에서 사용된 접근 방식
범위를 만들기 위해 시작 값(start)과 끝 값(last)을 입력받습니다.
fib1은 0, fib2는 1, fib3는 1로 선언하고 초기화합니다.
임시 변수 res를 선언하고 0으로 초기화합니다. 이 변수는 범위 내 피보나치 수의 개수를 저장합니다.
fib1이 끝 값(last)보다 작거나 같은 동안 반복문을 실행합니다.
반복문 안에서 fib1이 시작 값(start)보다 크거나 같으면 res를 1 증가시킵니다.
fib1을 fib2로, fib2를 fib3로 설정하고, fib3는 fib1 + fib2로 갱신하여 다음 피보나치 수로 이동합니다.
반복문이 종료되면 res 값을 반환합니다.
결과를 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// start부터 last까지 범위 내 피보나치 수의 개수를 세는 함수
int count_fibonacci(int start, int last){
// 첫 세 개의 피보나치 수
int fib1 = 0, fib2 = 1, fib3 = 1;
// 피보나치 수의 개수를 세기 위한 변수
int res = 0;
while (fib1 <= last){
if (fib1 >= start){
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// main 함수
int main(){
int start = 6, last = 100;
cout << "수열 내 피보나치 수의 개수는 "
<< count_fibonacci(start, last);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
수열 내 피보나치 수의 개수는 6
시간 및 공간 복잡도 분석
피보나치 수는 황금비(약 1.618)의 거듭제곱 속도로 기하급수적으로 증가합니다. 따라서 n 이하의 피보나치 수는 대략 logφ(n)개 정도만 존재하며, 위 반복문 역시 이 횟수만큼만 실행됩니다. 이러한 이유로 전체 시간 복잡도는 O(log n)이 되고, fib1, fib2, fib3, res와 같은 상수 개수의 변수만 사용하므로 공간 복잡도는 O(1)입니다.