[백준] 2748번 - 피보나치 수2

문제 링크 : https://www.acmicpc.net/problem/2748

문제 탐색하기

1) 문제 분석

비포나치 수는 0과 1로 시작.
2번째 부터는 바로 앞 두 비포나치 수의 합이 된다.
식 : Fn = Fn - 1 + Fn -2 ( n >= 2)
n이 주어졌을 때, n번째 비포나치 수를 구하는 프로그램 작성.

2) 가능한 시간복잡도

(1) 입력 처리

입력으로 숫자 하나를 받고, 상수 개수의 입력을 처리하므로 -> O(1)

(2) Bottom-Up 연산 처리

피보나치 수를 반복문으로 구할 때, 2부터 n까지 순서대로 진행된다.
각 단계에서 상수 시간 연산을 하며 값을 저장하거나 업데이트 하므로 -> O(N)

(3) 결과 출력

최종 계산된 값 하나를 출력한다 -> O(1)

(4) 전체 시간 복잡도

입력 처리 : O(1)
피보나치 계산 : O(N)
결과 출력 O(1)-> 총합 : O(N)

3) 알고리즘 선택 이유

피보나치 수열은 바로 이전의 두 항만 필요하므로, 반복문을 활용한 Bottom-Up 방식으로 효율적으로 해결할 수 있다.
메모이제이션이나 재귀 없이도 단순 반복문으로 충분히 최적화가 가능하다고 생각했다.
따라서 이 문제는 Bottom-Up 방법으로 풀 때 가장 효율적이고 직관적이라고 보았다.

잠깐! Dynamic Programming(DP, 동적 프로그래밍)에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.

코드 설계하기

1. 실행 구조

1) 피보나치 수를 입력 받는다.

2) 입력된 수를 함수에 넣고 결과를 출력한다.

n이 0이면 0, 1이면 1을 반환한다.
n이 2 이상이면 피보나치 수를 계산한다.
F(n) = F(n-1) + F(n-2)
계산한 피보나치 수를 반환한다.

2. 고민이 되었던 부분

이번 문제는 정말 많이 틀리고 맞고를 반복했었다. 이를 통해서 몇 가지 고민하고, 배웠던 점들을 정리해보려고 한다.

1) Number vs BigInt

: Number 타입은 부동소수점 기반(64비트 실수형)이기 때문에, 정확하지 않은 계산이 발생할 수 있었다. 특히 덧셈 연산에서 부동소수점 오차가 발생하면, 문제에서 요구하는 정확한 값을 출력하지 못하게 된다는 점을 알게 되었다. 반면, BigInt는 정확한 정수 값으로 연산과 출력을 진행할 수 있었다. 쉽게 말해서 피보나치 수가 커지면서 Number 타입의 정확도가 깨져서 백준 채점 시 틀렸다는 결과를 마주해야 했었다. 따라서 숫자가 커진다면 정확도 손실 발생을 막기 위해 BigInt 타입도 사용할 수 있어야 한다는 점을 배웠다.

2) BigInt 사용 시 유의할 점

BigInt는 숫자 뒤에 n을 붙여야 한다. (ex. 0n, 1n, 2n)
또한, 반복문에서도 Index 변수 값이 BigInt 타입이어야 한다.
하지만, 배열 인덱스는 Number 타입이어야 한다는 점을 유의해야 한다.
BigInt는 직접 출력하면, 백준에서 에러가 나기 때문에 문자열로 변환해서 .toString() 으로 출력해야 한다.

3) 단순히 빠르고 짧은 코드로 최적화 하기

JavaScript

const fs = require('fs');
const n = BigInt(fs.readFileSync('/dev/stdin').toString().trim());

let a = 0n;
let b = 1n;

for (let i = 0n; i < n; i++) {
    [a, b] = [b, a + b];
}

console.log(a.toString());

: 이렇게까지 단순화 할 순 있지만, 조금 더 가독성을 고려해서 아래와 같은 정답 코드를 사용했다.

정답 코드

JavaScript

// 사용 언어 : Javascript

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

function fibonacci(n) {
    // n이 0일 때 0 반환, n이 1일 때 1 반환
    if (n === 0n) return 0n;
    if (n === 1n) return 1n;

     // n이 2 이상일 때 피보나치 수를 계산
    let fib = [0n, 1n]; // 0번째와 1번째 피보나치 수 초기화
    for (let i = 2n; i <= n; i++) {
        fib[Number(i)] = fib[Number(i - 1n)] + fib[Number(i - 2n)];
    }

    // n번째 피보나치 수 반환
    return fib[Number(n)];
}

console.log(fibonacci(input).toString());

마무리하며

여전히 JavaScript 문법에 대해 내가 부족하다는 점을 다시 한 번 느낄 수 있었던 문제였다. 문법적으로 더 알고 있으면 도움이 될 부분이 많다는 것을 직접 체감할 수 있었고, 특히 데이터 타입에 대해서는 어느 정도 알고 있다고 생각했지만, 실제로는 부족한 부분이 많다는 것도 깨달을 수 있었다.

그럼에도 불구하고 흥미롭고 감사한 점은, 이렇게 새로운 것들을 배워가고 부족한 부분을 채워나갈 수 있다는 점이다. 특히 DP 같은 부분을 개인적으로 많이 약하다고 느꼈는데, 이번 문제를 풀어가면서 그 부족함을 조금씩 메워가고 있다는 점에서 의미 있는 경험이었다고 생각한다.

앞으로도 단순히 문제를 푸는 것에 그치지 않고, 이렇게 성장의 기회로 삼아가고 싶다.

최근 글