자바스크립트로 파도반(Padovan) 수열의 n번째 항 구하기

파도반 수열이란?

파도반 수열은 다음과 같은 초기값으로 정의되는 정수 수열 P(n)입니다.

P(0) = P(1) = P(2) = 1

그리고 다음 점화식을 따릅니다.

P(n) = P(n-2) + P(n-3)

즉, 각 항은 두 번째 앞 항과 세 번째 앞 항의 합으로 계산됩니다. 파도반 수열의 첫 몇 개 값은 다음과 같습니다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, …

문제 정의

숫자 n을 입력받아 파도반 수열의 n번째 항을 반환하는 자바스크립트 함수를 작성해야 합니다.

해결 방법

가장 효율적인 방법은 재귀 호출 대신 반복문을 사용하는 것입니다. 세 개의 변수에 이전 값들을 저장해 두고, 루프를 돌면서 새로운 값을 계산하면 시간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

예제 코드

const num = 32;
const padovan = (num = 1) => {
    let secondPrev = 1, pPrev = 1, pCurr = 1, pNext = 1;
    for (let i = 3; i <= num; i++){
        pNext = secondPrev + pPrev;
        secondPrev = pPrev;
        pPrev = pCurr;
        pCurr = pNext;
    };
    return pNext;
};
console.log(padovan(num));

실행 결과

5842

코드 설명

위 코드에서는 secondPrev(두 단계 이전 값), pPrev(세 단계 이전 값 역할), pCurr(현재 값), pNext(다음 값) 네 개의 변수를 사용합니다. 매 반복마다 두 번째 이전 항과 세 번째 이전 항을 더해 새로운 항을 만들고, 변수들을 한 칸씩 앞으로 이동시킵니다.

이 방식은 이미 계산한 값을 변수에 보관하기 때문에 단순 재귀 구현에서 발생하는 중복 계산을 완전히 피할 수 있으며, n이 커져도 빠르게 결과를 얻을 수 있습니다.