leetcode 75 - 1137. N-th Tribonacci Number

문제) 3개씩 더해 피보나치를 구성하는 tribonacci의 n번째 숫자 구하기

 

기존 풀이)

var tribonacci = function(n) {
    // [0, 1, 1]
    // slice(i, i + 3) => sum 을 원 배열에 push 
    // n번째까지 반복하여 마지막 요소를 return
    const fibonacci = [0, 1, 1]
    
    for (let i = 0; i < n ; i++) {
        let newFib = fibonacci.slice(i, i+3).reduce((acc, cur) => acc + cur)
        fibonacci.push(newFib)
    }

    return fibonacci[n]
};

 

테스트를 통과하고 제출은 가능하나, for문 내에서 reduce를 돌아 중첩 반복이 발생하는게 아쉬웠다.

시간복잡도는 제일 바깥의 for 문이 n번 돌고, 그 안에서 slice 가 3번, reduce가 3번 돌아 결과적으로는 O(n*3) = O(n^2)이다. 

 

알고리즘)

메모이제이션을 사용해 불필요한 연산을 줄이는 것이 좋다. 

var tribonacci = function(n, memo = {}) {
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;

    if (memo[n]) {
        return memo[n];
    }

    memo[n] = tribonacci(n - 1, memo) + tribonacci(n - 2, memo) + tribonacci(n - 3, memo);
    return memo[n];
};

 

-> 하나의 값이 단 한번만 연산되어 시간복잡도가 O(n)으로 줄어듦!