백준) 2748 - 피보나치 수2 JS

📌 문제 링크

https://www.acmicpc.net/problem/2748

---

📌 문제 탐색하기

• Fn = Fn-1 + Fn-2 (n ≥ 2)는 피보나치 수입니다.
• n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하세요.

시간복잡도

• O(n)

---

📌 코드 설계하기

1. 문제의 input을 숫자로 변환합니다.
2. fib 함수를 만들어 n이 0이면 0을 return, 1과 2이면 1을 return합니다.
3. n+1 크기의 배열을 만들고 모든 요소를 BigInt(1)로 초기화합니다.
4. dp배열의 0번째 인덱스를 0으로 설정합니다.
5. 3부터 n까지 반복하면서 피보나치 수열의 값을 계산하여 dp 배열에 저장합니다.

---

📌 시도 회차 수정 사항 (Optional)

1회차

• 4달 전에 풀었던 문제인데 그때도 한번에 해결하지 못하고 구글링을 통해 자바스크립트의 숫자 한계임을 알게 된 후 `BigInt`를 사용해서 해결했었다.
• 하지만 오늘도 `BigInt`를 전혀 기억하지 못하고 기존 풀었던 방식이 아닌 다른 방법을 시도 했다가 오히려 이 방법이 아닌가 하고 다시 기존 방식인 for문으로 돌아왔다.... 그래도 계속 틀리길래 생각나게 된 `BigInt`🤦🏻‍♀️
• 그러니 다시 한번 정리해본다.

자바스크립트에서 일반적으로 사용되는 Number 타입은 64비트 부동소수점 형식

정확하게 표현할 수 있는 가장 큰 정수는 Number.MAX_SAFE_INTEGER, 즉 2^53 - 1 (9,007,199,254,740,991)

피보나치 수열은 매우 빠르게 증가하기 때문에 78번째 피보나치 수는 이미 Number.MAX_SAFE_INTEGER를 초과
피보나치 수열의 큰 수를 정확하게 표현하기 위해서는 BigInt를 사용해야 함

마지막에 출력할 때 BigInt 리터럴의 마지막에 알파벳 n이 붙기 때문에 문자열로 변환하여 출력

• 같은 실수를 반복한 것이니 이제는 까먹지 않겠지... 🤷🏻‍♀️

---

📌 정답 코드

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
const input = Number(fs.readFileSync(filePath).toString().trim());

const fib = (n) => {
  if (n === 0) return 0;
  if (n === 1 || n === 2) return 1;

  const dp = new Array(n + 1).fill(BigInt(1));
  dp[0] = 0;

  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 1];
  }
  return dp[n].toString();
};

console.log(fib(input));

 

기존 + 오늘 풀었던 방법은 위와 같다.

다르게 시도했던 방식(객체 이용)에 다시 `BigInt`를 적용하니 정답이 되었다!!!

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const input = Number(fs.readFileSync(filePath).toString().trim());

const fib = (n: number, memo: { [key: number]: bigint } = {}): bigint => {
  if (n === 0) return BigInt(0);
  if (n <= 2) return BigInt(1);
  if (memo[n]) return memo[n];

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

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