C++로 트리보나치(Tribonacci) 수열 생성하는 방법

이번 글에서는 C++를 이용해 트리보나치(Tribonacci) 수열을 생성하는 방법을 알아보겠습니다. 트리보나치 수는 피보나치 수와 매우 유사하지만, 차이점은 새로운 항을 만들 때 이전 세 개의 항을 더한다는 점입니다.

n번째 항 T(n)을 구하는 공식은 다음과 같습니다.

T(n) = T(n - 1) + T(n - 2) + T(n - 3)

수열은 첫 세 항 {0, 1, 1}에서 시작합니다.

알고리즘

트리보나치 수열을 생성하는 절차는 다음과 같습니다.

tribonacci(n):
시작
    first := 0, second := 1, third := 1
    first, second, third 출력
    n - 3번 반복:
        next := first + second + third
        next 출력
        first := second
        second := third
        third := next
종료

C++ 구현 예제

아래 코드는 n개의 트리보나치 수를 생성하여 출력하는 함수를 보여줍니다.

#include<iostream>
using namespace std;
long tribonacci_gen(int n){
    // n개의 트리보나치 수를 생성하는 함수
    int first = 0, second = 1, third = 1;
    cout << first << " " << second << " " << third << " ";
    for(int i = 0; i < n - 3; i++){
        int next = first + second + third;
        cout << next << " ";
        first = second;
        second = third;
        third = next;
    }
}
main(){
    tribonacci_gen(15);
}

실행 결과

위 프로그램을 실행하면 다음과 같이 15개의 트리보나치 수가 출력됩니다.

0 1 1 2 4 7 13 24 44 81 149 274 504 927 1705

동작 원리 정리

이 알고리즘은 세 개의 변수(first, second, third)에 현재까지의 마지막 세 항을 저장하고, 각 반복마다 이 세 값을 더해 다음 항(next)을 계산합니다. 그런 다음 변수들을 한 칸씩 앞으로 이동시켜 최신 세 항을 유지합니다. 시간 복잡도는 O(n)으로, 단순 재귀 방식(지수 시간)보다 훨씬 효율적입니다.