Fibonacci Modified

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

기존 피보나치 수열을 변환하여 새로 만든 규칙을 적용하려고 한다. 새로 만든 피보나치 규칙은 다음과 같다.

t[i + 2] = t[i] + (t[i + 1]^2)

아래 예시를 한번 살펴보자.

t1 = 0
t2 = 1
n = 6

t3 = 0 + (1^2) = 1
t4 = 1 + (1^2) = 2
t5 = 1 + (2^2) = 5
t6 = 2 + (5^2) = 27

1. 나의 풀이

BigInt를 사용할 수 없는 환경이라서 일단 BigInt를 처리하는 것은 제외하고 작성해 보았다. 피보나치 수열은 전형적인 dp로 해결할 수 있는 문제라서 어렵지 않게 작성했다.

function fibonacciModified(t1, t2, n) {
    // Write your code here
    const dp = [t1, t2];
    
    for (let i = 2; i < n; i++) {
        dp[i] = dp[i - 2] + Math.pow(dp[i - 1], 2);
    }

    return dp[n - 1];
}

해당 문제를 풀고 다른 사람들의 풀이 방법이 궁금해서 찾아봤는데, 공간 복잡도 조건도 같이 부합해야 한다는 내용을 보게 되어 위 로직을 수정해 보았다.

설명에서는 시간 복잡도와 공간 복잡도를 각각 아래와 같이 표현하였다.

Time complexity: O(n)
Space complexity: O(1)

수정된 로직은 아래와 같다.

function fibonacciModified(t1, t2, n) {
    // Write your code here
    let t3 = t1 + Math.pow(t2, 2);
    
    for (let i = 2; i < n; i++) {
        t3 = t1 + Math.pow(t2, 2);
        t1 = t2;
        t2 = t3;
    }
    
    return t3;
}

알고리즘 문제를 작성하면서 공간 복잡도를 계산하는 방식이 익숙하지 않지만, t3 변수를 추가함으로써 O(3)의 공간 복잡도를 가지고 상수는 1로 생략되기 때문에 총 O(1)의 공간 복잡도를 가지게 하였다.

O(3)인 이유는 각각 t1, t2, t3 변수가 사용되기 때문이다.

기존 작성된 로직은 n 만큼 배열의 길이가 늘어나기 때문에 O(n) 공간 복잡도를 가지며, 수정된 로직을 사용하면 공간 복잡도를 개선할 수 있다.

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.