트리보나치 숫자 (Tribonacci Number)

Tribonacci Number : 트리보나치 숫자

피보나치 수열은 $F_n = F_{n-1} + F_{n-2}$ 와 같이 이전에 계산된 두개의 값을 이용해 새로운 값을 찾는 개념이죠.

트리보나치 수열은 피보나치 수열과 비슷한 개념으로 이전에 계산된 값이 두개가 아닌 세개의 값으로 새로운 값을 찾는 개념입니다. 쉽게 생각하면, 트리보나치는 피보나치의 세개짜리 버젼이라 생각하시면 됩니다.

$$F_n = F_{n-1} + F_{n-2} + F_{n-3}, F_0 = F_1 = 0 \ and \ F_2 = 1$$

트리보나치 숫자를 나열하면 다음과 같습니다.

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852

프로그래밍 문제로 이 개념을 활용하면 어떻게 변할까요? 예상하셨듯이, 양의 정수 $N$ 을 입력 받았을때, $N$ 번째 트리보나치 숫자를 찾으면 되는 문제로 변하게 됩니다.

예제 :

입력값 : 5
출력값 : 0, 0, 1, 1, 2

입력값 : 10
출력값 : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44

입력값 : 20
출력값 : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44,
         81, 149, 274, 504, 927, 1705, 3136, 
          5768, 10609, 19513

---

이 문제에 대한 가장 간단한 솔루션은 트리보나치 숫자를 찾는 재귀 함수를 작성하는 것입니다.

# n 번째 트리보나치 숫자를 찾는
# 단순 재귀 python 프로그램

def printTribRec(n) :
    if (n == 0 or n == 1 or n == 2) :
        return 0
    elif (n == 3) :
        return 1
    else :
        return (printTribRec(n - 1) +
                printTribRec(n - 2) +
                printTribRec(n - 3))
         
 
def printTrib(n) :
    for i in range(1, n) :
        print( printTribRec(i) , " ", end = "")
         
 
# 테스트를 위한 드라이버 코드
n = 10
printTrib(n)
 
 
# 이 코드는 Nikita Tiwari 가 작성했습니다.

출력값

0 0 1 1 2 4 7 13 24 44 

재귀 함수는 상당히 이해하기는 편하지만 비효율적인 함수입니다. 시간 복잡도는 지수 형태의 복잡도를 띄며 입력값 $N$ 이 조금만 높아져도 overflow 에러를 발생시킵니다.

다음은 동적 계획법 (DP) 를 활용한 솔루션 입니다.

# n 번째 트리보나치 숫자를 찾는
# DP 를 기반으로한 python 프로그램

# bottom up 방식으로 접근
def printTrib(n) :
 
    dp = [0] * n
    dp[0] = dp[1] = 0;
    dp[2] = 1;
 
    for i in range(3,n) :
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
 
    for i in range(0,n) :
        print(dp[i] , " ", end="")
         
# 테스트를 위한 드라이버 코드
n = 10
printTrib(n)
 
# 이 코드는 Nikita Tiwari 에 의해 작성되었습니다.

위 코드의 시간복잡도는 선형 형태를 보이지만 n 이 커지면 배열에 의한 추가적인 공간들이 필요합니다. 즉, 시간 복잡도와 공간 복잡도는 모두 $O(n)$ 입니다. 하지만 i 번째 트리보나치 숫자를 구하기 위해서는 전에 계산된 값들은 총 3개만 필요하죠. 이를 이용해 공간 복잡도를 최적화 시킬수 있습니다.

# n 번째 트리보나치 숫자를 찾는
# DP 를 기반으로한 python 프로그램
# 공간을 최적화 시킴.

def printTrib(n) :
    if (n < 1) :
        return
  
    # 처음 세개의 숫자들을 초기화 시킨다.
    first = 0
    second = 0
    third = 1
 
    print( first , " ", end="")
    if (n > 1) :
        print(second, " ",end="")
    if (n > 2) :
        print(second, " ", end="")
 
	# 이전에 계산한 첫번째 두번째 세번째 값들을 이용해
    # 새로운 값을 찾고, 차례로 앞으로 옮긴다. 
    # (두번째는 첫번째 값이 되고, 세번째는 두번째 값, 
    # 계산된값은 마지막 세번째 값으로 들어옴)
    for i in range(3, n) :
        curr = first + second + third
        first = second
        second = third
        third = curr
 
        print(curr , " ", end="")
        
# 테스트를 위한 드라이버 코드
n = 10
printTrib(n)
 
# 이 코드는 Nikita Tiwari 에 의해 작성되었습니다.

더더욱 최적화 할 수 있는 방법은 무엇이 있을까요? 행렬 멱법(matrix exponentiation)을 이용해 시간복잡도를 $O(n)$ 에서 $O(log(n))$ 으로 만들 수 있습니다. 행렬 멱법에 대한 자세한 내용은 여기를 참고해 주세요.

이 포스팅에서는 위의 포스팅을 보고 오신뒤 행렬 멱법의 개념을 아신다는 가정하에 설명드리겠습니다. 트리보나치의 $n$ 번째 숫자인 $F(n)$ 을 구하는 수식은 다음과 같습니다.

$$ \begin{bmatrix} F(n) \cr F(n-1) \cr F(n-2) \end{bmatrix} = { \begin{bmatrix} 1 & 1 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \end{bmatrix}}^{n-2} \times \begin{bmatrix}F(2) \cr F(1) \cr F(0) \end{bmatrix} = { \begin{bmatrix} 1 & 1 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \end{bmatrix}}^{n-2} \times \begin{bmatrix} 1 \cr 0 \cr 0 \end{bmatrix}$$

위 방식대로라면 행렬 $\{\{1, 1, 1\}, \{1, 0, 0\}, \{0, 1, 0\}\}$ 을 $n-2$ 번 곱한다음 그 행렬을 $T$ 라 한다면, $F(n) = 1 * T[0][0] + 0 * T[0][1] + 0 *T[0][2] = T[0][0]$ 이므로, 행렬 $T$ 의 첫번째 열 과 첫번째 행 자리에 있는 값이 $F(n)$ 이 되겠습니다.

아래는 행렬 멱법을 이용해 구현한 $N$ 번째 트리보나치 숫자를 구하는 C++ 프로그램 입니다.

#include <iostream>
using namespace std;

// n 번째 트리보나치 숫자를 구하기 위한 프로그램
// 3*3 행렬을 위한 행렬 곱 함수 
// for 반복문을 사용하지 않은것은 시간 단축을 위해서 입니다.
void multiply(int T[3][3], int M[3][3])
{
    int a, b, c, d, e, f, g, h, i;
    a = T[0][0] * M[0][0] + T[0][1] * M[1][0] + T[0][2] * M[2][0];
    b = T[0][0] * M[0][1] + T[0][1] * M[1][1] + T[0][2] * M[2][1];
    c = T[0][0] * M[0][2] + T[0][1] * M[1][2] + T[0][2] * M[2][2];
    d = T[1][0] * M[0][0] + T[1][1] * M[1][0] + T[1][2] * M[2][0];
    e = T[1][0] * M[0][1] + T[1][1] * M[1][1] + T[1][2] * M[2][1];
    f = T[1][0] * M[0][2] + T[1][1] * M[1][2] + T[1][2] * M[2][2];
    g = T[2][0] * M[0][0] + T[2][1] * M[1][0] + T[2][2] * M[2][0];
    h = T[2][0] * M[0][1] + T[2][1] * M[1][1] + T[2][2] * M[2][1];
    i = T[2][0] * M[0][2] + T[2][1] * M[1][2] + T[2][2] * M[2][2];
    T[0][0] = a;
    T[0][1] = b;
    T[0][2] = c;
    T[1][0] = d;
    T[1][1] = e;
    T[1][2] = f;
    T[2][0] = g;
    T[2][1] = h;
    T[2][2] = i;
}
 
// 2차원 행렬 T 를 n 번 곱하는 재귀 함수 
void power(int T[3][3], int n)
{
    // 기본 조건 (base case)
    if (n == 0 || n == 1)
        return;
    int M[3][3] = { { 1, 1, 1 }, { 1, 0, 0 }, 
                                 { 0, 1, 0 } };
 
    // n 의 제곱근의 지수승으로 재귀 형식으로 행렬을 다시 곱한다.
    power(T, n / 2);
 
    // 행렬 T 를 제곱한다. 
    multiply(T, T);
 
    // n 이 홀수면 만들어진 M (기본 T 와 같음) 을
    // 이용해서 한번더 곱한다.  
    if (n % 2)
        multiply(T, M);
}
int tribonacci(int n)
{
    int T[3][3] = { { 1, 1, 1 }, { 1, 0, 0 },
                                 { 0, 1, 0 } };
 
    // 기본 조건 (base case)
    if (n == 0 || n == 1)
        return 0;
    else
        power(T, n - 2);
 
    // 행렬 중 T[0][0] 이 트리보나치 숫자를 가지고 있습니다.
    // 그 값을 반환합니다. 
    return T[0][0];
}
 
// 테스트를 위한 드라이버 코드
int main()
{
    int n = 10;
    for (int i = 0; i < n; i++)
        cout << tribonacci(i) << " ";
    cout << endl;
    return 0;
}

power 함수에서 왜 n 이 짝수와 홀수냐에 따라 취급하는 방법이 다른지 궁금하신 분은 여기를 참조해 주세요.

행렬 멱법에 관련된 포스팅에 적어놓은 코드와 크게 다르지 않습니다. 다른 부분이 있다면 multiply 함수에서 반복문인 for 문을 작성하지 않았다는 점입니다. 말씀드렸듯이 이 알고리즘의 시간복잡도는 $O(log(n))$ 이며, 동적 계획법에 비해 훨씬 시간적으로 단축된 형태를 보입니다. 하지만 다시 power함수에서 재귀 형태를 보이므로, 재귀 방식으로 인한 시간 초과(TLE)와 overflow 를 조심할 필요가 있습니다.

---

이번 포스팅은 간단하게 작성했습니다.
전에 써놓았던 포스팅이 큰 효과를 발휘하네요 ㅋㅋ