Fibonacci(피보나치), Tribonacci 문제 풀이 DP, Recursion, Bottom Up

Tribonacci 수열

피보나치 수열이란, 특정 항이 앞의 두 항의 합과 같은 수열을 의미한다. 첫번째와 두번째 항의 값은 0, 1로 고정된다.

피보나치 수열의 n 번째 값이 무엇인지 계산하는 것이 코딩 기본 문제에 종종 등장한다.

 

Tribonacci 수열은, 피보나치 수열에서 1개의 항을 더 추가하는 것이다. 즉, 특정 항의 값이 앞의 세개 항의 합과 같은 수열이다. 이때 첫번째, 두번째, 세번째 항의 값은 각각 0, 1, 1로 고정된다.

 

예를 들어, Tribonacci의 4번째 항은 0 + 1 + 1 = 2이다. 5번째 항은 1 + 1 + 2 = 4가 되는 것이다.

Tribonacci 수열의 n번째 값을 계산하는 문제도 종종 코딩 문제로 나온다. 문제 풀이 방식은 피보나치와 다를게 없다. 연습해보고 싶으면 LeetCode의 75번 문제인 1137.N-th Tribonacci Number 를 풀어보면 된다.

 

https://leetcode.com/problems/n-th-tribonacci-number/?envType=study-plan-v2&envId=leetcode-75 

N-th Tribonacci Number - LeetCode

Tribonacci 수열 문제 풀이

위 문제를 푸는 방식은 3개 있고 각각 Recursion, Dynamic Programming, Bottom Up 이다.

이 문제는 Recursion과 Dynamic Programming을 사용하면 보통 Time Limit에 걸린다. 그리고 Bottom Up을 사용하면 무난히 통과된다. 그럼 위 문제를 푸는 알고리즘을 각 방법 별로 살펴보고 마지막에는 시간 비교도 해보자.

1. Recursion

특정 항의 값을 계산하는 함수를 반복해서 호출하는 방식이다. Recursion은 Time Complexity : (3^n)인 가장 연산량이 많은 방식이다. 이는 각 항의 값을 계산하는 과정을 Tree로 그려보면 금방 이해 된다. 피보나치 수열의 경우 2^n이 된다.

int tribonacci_Recursion(int n) {
    int RetVal = 0;
    int ans[38] = { 0 };

    ans[0] = 0;
    ans[1] = 1;
    ans[2] = 1;

    if (n == 0){
        RetVal = 0;
    }
    else if (n == 1){
        RetVal = 1;
    }
    else if (n == 2){
        RetVal = 1;
    }
    else{
        RetVal = tribonacci_Recursion(n - 1) + tribonacci_Recursion(n - 2) + tribonacci_Recursion(n - 3);
    }

    return RetVal;
}

2. Dynamic Programming

Recursion의 방식에서, 이미 계산된적이 있는 항은 그 값을 가져다 쓰는 것이다. 계산된 적있는 값인걸 어떻게 알까? 1D array 변수를 0으로 초기화 및 선언해놓고, 특정 항의 인덱스에 값이 0이면 계산된적 없는 값, 0이 아니면 계산된적 있는 값이다. 계산된적 없는 값은 Recursion과 같이 계산한 후, 1D array 변수에 값을 저장해주면 된다.

즉, Recursion 대비 메모리를 사용하여 연산 횟수를 줄이는 방법이다.

int tribonacci_DP(int n) {
    int DpTable[38] = { 0 };
    int RetVal = 0;

    if (n == 0){
        RetVal = 0;
    }
    else if (n == 1){
        RetVal = 1;
    }
    else if (n == 2){
        RetVal = 1;
    }
    else if (DpTable[n] != 0){
        RetVal = DpTable[n];
    }
    else{
        RetVal = tribonacci_DP(n - 1) + tribonacci_DP(n - 2) + tribonacci_DP(n - 3);
        DpTable[n] = RetVal;
    }

    return RetVal;
}

3. Bottom Up

위 방법들 중 가장 빠른 방법이다. 앞쪽 인덱스부터 차례대로 계산해나가면 되고 이는 Time Complexity O(n)이다.

int tribonacci_BottomUp(int n) {
    int RetVal = 0;
    int ans[38] = { 0 };

    ans[0] = 0;
    ans[1] = 1;
    ans[2] = 1;

    if (n == 0){
        RetVal = 0;
    }
    else if (n == 1){
        RetVal = 1;
    }
    else if (n == 2){
        RetVal = 1;
    }
    else{
        for (int i = 3; i != (n + 1); ++i)
        {
            ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
        }

        RetVal = ans[n];
    }

    return RetVal;
}

각 방법 별 연산 시간 비교

Tribonacci 수열의 30번째 항의 값을 계산하는데 소요되는 시간을 비교하였다.

각 함수가 호출되고 반환되는데 걸리는 시간을 ctime 헤더를 사용해 측정하였다.

Tribonacci, 30번째 항의 값은?
Recursion : 2.349000 (s)
Dynamic Programming : 1.866000 (s)
Bottom Up : 0.000000 (s)

결과적으로 Bottom Up 방식이 역시 가장 빨랐고, 그 다음이 DP, 가장 느린건 Recursion이었다.

 

예시 문제

아래 LeetCode 문제도 재밌다.

https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=leetcode-75 

House Robber - LeetCode