피보나치 수열은 0에서 시작하며, 앞의 두 수를 더한 값이 다음 수가 되는 수학적 수열입니다. 예를 들어 첫 번째 수는 0, 두 번째 수는 1이며, 이 둘의 합인 1이 세 번째 수가 됩니다.
F0=0, F1=1
일반적인 점화식으로 표현하면 다음과 같습니다.
Fn = Fn-1 + Fn-2
F2 = F0 + F1
F2 = 0 + 1
F2 = 1
이어서 1과 1을 더하면 다음 수는 2가 됩니다.
F1=1, F2=1
Fn = Fn-1 + Fn-2
F3 = F1 + F2
F3 = 1 + 1
F3 = 2
피보나치 수열의 이해
위 규칙을 따르면 피보나치 수열은 다음과 같이 전개됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
문제 정의: 피보나치 수의 제곱합
이번 문제는 N번째까지의 피보나치 수를 각각 제곱한 뒤, 그 값들을 모두 더한 결과를 구하는 것입니다.
입력 : 4
출력 : 15
설명 : 0² + 1² + 1² + 2² + 3² = 0 + 1 + 1 + 4 + 9 = 15
즉, 먼저 N까지의 피보나치 수를 차례대로 구하고, 각 수를 제곱한 후 누적하여 합산하면 됩니다.
C++ 구현 예제
아래 코드는 반복문을 사용해 피보나치 수를 생성하고, 동시에 각 항의 제곱을 누적합에 더하는 방식으로 동작합니다.
#include <iostream>
using namespace std;
int main(){
int n = 4, c;
int first = 0, second = 1, next;
int sum = 0;
for ( c = 0 ; c < n+1 ; c++ ){
if ( c <= 1 )
next = c;
else{
next = first + second;
first = second;
second = next;
}
sum += next * next;
}
printf("%d", sum);
return 0;
}
코드 동작 원리
- first, second: 현재 계산에 필요한 앞의 두 피보나치 수를 저장합니다.
- next: 새로 계산된 피보나치 수를 담습니다. 인덱스가 0 또는 1일 때는 그 값을 그대로 사용합니다.
- sum += next * next: 매 반복마다 현재 피보나치 수의 제곱을 합계에 누적합니다.
실행 결과
15
n이 4일 때 피보나치 수열은 0, 1, 1, 2, 3까지 생성되며, 각각을 제곱해 더하면 0 + 1 + 1 + 4 + 9 = 15가 출력됩니다. 이처럼 하나의 반복문 안에서 수열 생성과 제곱합 계산을 함께 처리하면 시간 복잡도 O(n)으로 효율적으로 문제를 해결할 수 있습니다.