C++로 구현하는 테트라나치(Tetranacci) 수열 생성 방법

이번 글에서는 C++를 이용해 테트라나치(Tetranacci) 수열을 생성하는 방법을 알아보겠습니다. 테트라나치 수열은 피보나치(Fibonacci) 수열과 유사하지만, 차이점이 있다면 새로운 항을 만들 때 이전 두 항이 아닌 이전 네 개의 항을 모두 더한다는 점입니다.

예를 들어 n번째 항 T(n)을 구하고 싶다면 다음과 같은 점화식을 사용합니다.

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

수열은 초기값 {0, 1, 1, 2}에서 시작합니다.

알고리즘

테트라나치 수열을 생성하는 알고리즘은 매우 간단합니다. 네 개의 변수에 초기값을 저장한 뒤, 반복문 안에서 네 항의 합을 계산하고 값을 한 칸씩 이동시키며 갱신하면 됩니다.

tetranacci(n):
Begin
    first := 0, second := 1, third := 1, fourth := 2
    print first, second, third, fourth
    for i in range n – 4, do
        next := first + second + third + fourth
        print next
        first := second
        second := third
        third := fourth
        fourth := next
    done
End

C++ 예제 코드

아래는 위 알고리즘을 C++로 구현한 코드입니다. 함수 tetranacci_gen()은 인자로 받은 개수만큼의 테트라나치 수를 화면에 출력합니다.

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

실행 결과

위 코드를 실행하여 첫 15개의 테트라나치 수를 출력하면 다음과 같습니다.

0 1 1 2 4 8 15 29 56 108 208 401 773 1490 2872

동작 원리 정리

코드의 핵심 로직을 요약하면 다음과 같습니다.

1. 네 개의 변수(first, second, third, fourth)에 초기값 0, 1, 1, 2를 저장합니다.
2. 반복문이 실행될 때마다 네 변수의 합으로 다음 항(next)을 계산해 출력합니다.
3. 그런 다음 각 변수의 값을 한 단계씩 앞으로 이동시켜(첫 번째 값은 버리고 새 항을 마지막에 추가) 다음 반복을 준비합니다.
4. 이 과정을 원하는 개수에서 4를 뺀 만큼 반복하면 전체 수열이 완성됩니다.

이 방식은 각 항을 상수 시간 O(1)에 계산할 수 있어, 재귀 호출을 사용하는 방법보다 훨씬 효율적이라는 장점이 있습니다.