99클럽 코테 스터디 2일차 TIL - 피보나치 비스무리한 수열(DP)

Hyejin·2025년 4월 1일

99클럽 BigInt TIL 개발자취업 동적프로그래밍 코딩테스트준비 피보나치수열 항해99

99Club

목록 보기

3/21

문제: https://www.acmicpc.net/problem/14495
알고리즘 분류: 다이나믹 프로그래밍

초기 접근 방식

점화식 이해: f(n) = f(n-1) + f(n-3)는 현재 값이 바로 전 값과 3단계 전 값의 합임
초기값 설정: f(1) = f(2) = f(3) = 1로 명확하게 설정
효율적인 메모리 사용: 수열을 계산할 때 이전 값들을 재사용하는 동적 프로그래밍 접근법이 필요

내 코드(1차 시도)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let fib = [1, 1, 1]; // 배열초기화
    
    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return fib[n-1];
    }
    
    // n이 4 이상이면 수열 계산
    for (let i = 3; i < n; i++) {
        // f(n) = f(n-1) + f(n-3) 공식 적용
        fib[i] = fib[i-1] + fib[i-3];
    }
    
    return fib[n-1];
}

console.log(fibonacciLike(n));

추가 설명

let fib = [1, 1, 1];

for (let i = 3; i < n; i++) {
  fib[i] = fib[i-1] + fib[i-3];
}

fib[0]은 f(1), fib[1]은 f(2), fib[2]는 f(3)

그러므로,

f(n)은 fib[n-1]
f(n-1)은 fib[n-2]
f(n-3)은 fib[n-4]

for루프에서 i는 배열의 인덱스이고,

fib[i]는 f(i+1)
fib[i-1]은 f(i)
fib[i-3]은 f(i-2)

결과적으로, 이 코드는 f(i+1) = f(i) + f(i-2)를 계산하는데, 이는 수학적 표기법으로는 f(n) = f(n-1) + f(n-3)와 동일
➡️ 인덱스와 수열의 위치 사이에 1의 차이가 있어서(fib[i]가 f(i+1)을 나타냄)

배열 인덱싱과 관련된 오류와 코드수정(2차 시도)

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let dp = new Array(n+1);
    dp[1] = dp[2] = dp[3] = 1;
    
    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return dp[n];
    }
    
    // n이 4 이상이면 수열 계산
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-3];
    }
    
    return dp[n];
}

console.log(fibonacciLike(n));

추가 설명

배열 이름변경: fib → dp (동적 프로그래밍 접근임을 명시)
배열을 0부터가 아닌 1부터 인덱싱하도록 변경 (new Array(n+1) 사용)
➡️ 코드의 가독성을 높이기 위해 배열의 인덱스를 수열의 위치와 일치
dp[1], dp[2], dp[3]을 직접 1로 초기화
반복문은 i = 4부터 시작하여 i <= n까지 실행
dp[n]을 반환하여 n번째 값을 리턴

1-based indexing 방식

배열 자체는 여전히 0부터 시작하지만, 우리가 0번 인덱스를 의도적으로 무시하고 1번부터 사용하는 것

new Array(n+1)로 배열을 생성하면:

크기가 n+1인 배열이 만들어 짐
예를 들어 n=5라면 크기가 6인 배열이 생성되고, 이 배열은 0번 인덱스부터 n번 인덱스까지 가짐
[undefined, undefined, undefined, undefined, undefined, undefined]

이제 0번 인덱스는 사용하지 않고, 1번부터 n번 인덱스를 사용:

dp[1]은 수열의 첫 번째 항
dp[2]는 수열의 두 번째 항
dp[3]은 수열의 세 번째 항
...
dp[n]은 수열의 n번째 항

이렇게 하면 코드에서 dp[i]가 정확히 수열의 i번째 항을 가리키게 되어, 수학적 표기법과 코드의 표기법이 일치하게 됨
따라서, 점화식 f(n) = f(n-1) + f(n-3)을 그대로 dp[i] = dp[i-1] + dp[i-3]으로 구현할 수 있어 코드가 더 직관적이고 이해하기 쉬워짐

런타임에러와 구현범위와 BitInt(최종 코드)

구현범위가 n이 최대 116까지 갈 수 있다고 명시되어 있으므로, 피보나치 비스무리한 수열의 값이 JavaScript의 Number 타입으로 표현할 수 있는 범위를 초과할 수 있음
JavaScript에서 안전하게 표현할 수 있는 정수의 최대값은 Number.MAX_SAFE_INTEGER로 약 9007조(9,007,199,254,740,991)
n이 116일 때의 값은 이 범위를 넘어갈 가능성이 높음
따라서, BigInt를 사용하여 코드를 수정 → 큰 수에 대한 처리가 필요

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();

let n = Number(input);

// 피보나치 비스무리한 수열 계산
function fibonacciLike(n) {
    // 기본 케이스: f(1) = f(2) = f(3) = 1
    let dp = new Array(n+1);
    dp[1] = dp[2] = dp[3] = 1n; // BigInt 리터럴 사용 ✅
    
    // n이 3 이하면 바로 결과 반환
    if (n <= 3) {
        return dp[n];
    }
    
    // n이 4 이상이면 수열 계산
    for (let i = 4; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-3];
    }
    
    return dp[n];
}

console.log(fibonacciLike(n).toString()); // BigInt를 문자열로 변환하여 출력