피보나치 수열이란?
피보나치 수열은 이전 두 항의 합이 다음 항이 되는 규칙을 가진 수열입니다. 첫 번째 항은 0, 두 번째 항은 1로 시작하며, 그 이후의 모든 항은 앞의 두 항을 더한 값이 됩니다.
이 문제에서는 피보나치 수열의 n번째 숫자를 구하는 것이 목표입니다. 이를 위해 수열의 모든 값을 차례대로 계산한 뒤, n개의 항을 화면에 출력하는 프로그램을 작성해 보겠습니다.
입력 및 출력 예시
입력: 8
출력: 0 1 1 2 3 5 8 13
동작 원리
피보나치 수열은 다음과 같은 방식으로 진행됩니다.
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
즉, 매 단계마다 이전 두 항의 값을 더해 다음 항을 만들어 나가는 것입니다. 이 과정을 for 반복문으로 구현하면 원하는 개수만큼의 피보나치 수를 손쉽게 생성할 수 있습니다.
C++ 구현 예제
아래 코드는 반복문을 사용해 n번째까지의 피보나치 수를 출력하는 프로그램입니다.
#include<iostream>
using namespace std;
int main() {
int t1 = 0, t2 = 1, n, i, nextTerm;
n = 8;
for (i = 1; i <= n; ++i) {
if(i == 1) {
cout << " " << t1;
continue;
}
if(i == 2) {
cout << " " << t2 << " ";
continue;
}
nextTerm = t1 + t2;
t1 = t2;
t2 = nextTerm;
cout << nextTerm << " ";
}
}
실행 결과
0 1 1 2 3 5 8 13
코드 설명
코드의 핵심 로직은 다음과 같습니다.
- t1, t2: 각각 현재 항과 그다음 항의 값을 저장하는 변수로, 초기값은 0과 1입니다.
- 첫 번째와 두 번째 항 처리: i가 1 또는 2일 때는 미리 저장된 값(0, 1)을 그대로 출력하고 continue로 건너뜁니다.
- nextTerm 계산: 세 번째 항부터는 t1과 t2를 더해 새로운 항을 만들고, 변수 값을 한 칸씩 밀어 갱신합니다.
이 알고리즘은 각 항을 한 번씩만 계산하므로 시간 복잡도는 O(n)이며, 공간 복잡도 역시 상수 개수의 변수만 사용하므로 O(1)입니다. 재귀 호출 방식(O(2ⁿ))에 비해 훨씬 효율적이기 때문에 실무에서도 반복문 기반 구현이 널리 사용됩니다.