C++로 구현하는 트리보나치 워드(Tribonacci Word) 생성 방법

트리보나치 워드(Tribonacci Word)는 숫자들로 이루어진 특수한 수열입니다. 이름에서 알 수 있듯이 피보나치 워드(Fibonacci Word)와 매우 유사하지만, 차이점은 두 개가 아닌 세 개의 이전 문자열을 반복적으로 연결하여 새로운 문자열을 만든다는 점입니다.

수열의 점화식은 다음과 같습니다.

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

시작 문자열은 {1, 12, 1213}이며, 그다음 문자열은 앞의 세 문자열을 연결한 1213 + 12 + 1 = 1213121이 됩니다.

알고리즘

트리보나치 워드를 생성하는 알고리즘은 다음과 같습니다. 세 개의 변수에 초기 문자열을 저장한 뒤, 반복문을 통해 이전 세 문자열을 계속 연결해 나가는 방식입니다.

tribonacci_word(n):
시작
    first := 1, second := 12, third := 1213
    first, second, third 출력
    i를 3부터 n까지 반복:
        temp := third
        third := third + second + first
        third 출력
        first := second
        second := temp
    반복 종료
종료

C++ 예제 코드

아래는 위 알고리즘을 C++로 구현한 예제입니다. n번째 항까지의 트리보나치 워드를 순서대로 출력합니다.

#include<iostream>
using namespace std;

long tribonacci_word_gen(int n){
    // n개의 트리보나치 워드를 생성하는 함수
    string first = "1";
    string second = "12";
    string third = "1213";
    cout << first << "\n" << second << "\n" << third << "\n";
    string tmp;
    for (int i = 3; i <= n; i++) {
        tmp = third;
        third += (second + first);
        cout << third << endl;
        first = second;
        second = tmp;
    }
}

main(){
    tribonacci_word_gen(6);
}

실행 결과

n = 6으로 실행하면 다음과 같이 총 7개의 문자열이 출력됩니다. 각 단계마다 문자열의 길이가 빠르게 증가하는 것을 확인할 수 있습니다.

1
12
1213
1213121
1213121121312
121312112131212131211213
12131211213121213121121312131211213121213121

정리

트리보나치 워드는 세 개의 이전 문자열을 연결하는 간단한 규칙만으로 만들어지지만, 반복될수록 문자열 길이가 지수적으로 증가한다는 특징이 있습니다. 피보나치 워드와 마찬가지로 문자열 처리와 재귀적 패턴 생성을 연습하기에 좋은 예제이므로, 직접 코드를 변형해 다양한 n값으로 실험해 보시길 권장합니다.