[js, node.js]백준 2748:제출

문제 요약

백준 2748:피보나치 수 2

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
• 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
• n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
• n은 90보다 작거나 같은 자연수이다.

입력

10

출력

55

문제 분석

• 피보나치의 규칙을 이해해야한다.
  • 피보나치 수열의 n번째 항은 (n-2)번째의 피보나치 수와 (n-1)번째의 피보나치 수를 더한 것이 된다.
• 재귀 함수로 실행하면, 중복 계산이 많아지면서 입력 값이 커질수록 실행 시간이 기하급수적으로 증가한다.
• BigInt에 대해 고려해야한다.

문제 설계

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const n = Number(input);
const dp = Array.from({ length: 91 }, () => 0n);
dp[1] = 1n;

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

console.log(dp[n].toString());

배열 전체를 BigInt로 초기화하기 Array.from BigInt

const n = Number(input);
const dp = Array.from({ length: 91 }, () => 0n);
dp[1] = 1n;

• $n$이 최대 90이라고 제시되어있기 때문에, 배열의 인덱스가 최대 90까지 접근해야한다. 그래서 $n+1$ 꼴인 length는 91이다.
• js의 Number는 최대 정밀도가 15~16자리까지 제한되므로, 90번째 피보나치 수를 계산할 때 값이 손실된다.
• 큰 정수를 안전하게 처리하기 위해 BigInt 타입을 사용한다.
• 0n, 1n은 BigInt 리터럴이다.

// e.g) js의 리터럴 표기법
// BigInt는 같은 타입끼리만 산술 연산이 가능하다.
BigInt: 123n, 456n

배열 dp를 이용해 동적 계획법(Dynamic Programming) 으로 접근 for 문

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

• 각 피보나치 수는 이전 두 개의 피보나치 수를 더한 값으로 계산하므로 for 문으로 접근한다.

출력 toString()

console.log(dp[n].toString());

• js에서 BigInt 타입은 출력할 때 문자열로 변환해야한다. 그렇지 않으면 n 뒤에 n 이 포함된 형식(123n)으로 출력된다.

결론

로직은 맞게 접근했으나, 큰 수 처리에 대한 고려를 하지않아 처음에 계속 틀렸었다. 로직에 대한 타입의 이해도 또한 중요하다.