[자바스크립트] 피보나치 수

Lv. 2. 피보나치 수

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어

• $F(2)$ = $F(0)$ + $F(1)$ = 0 + 1 = 1
• $F(3)$ = $F(1)$ + $F(2)$ = 1 + 1 = 2
• $F(4)$ = $F(2)$ + $F(3)$ = 1 + 2 = 3
• $F(5)$ = $F(3)$ + $F(4)$ = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

제한사항

• n은 2 이상 100,000 이하인 자연수입니다.

 

 

입출력 예

 

 

자료구조

① 정수: MOD

② 정수형 배열: d

 

 

알고리즘

① 피보나치 수열에서 n번째 값을 계산:

• $F(0)$ = 0
• $F(1)$ = 1
• $F(2)$ = 1
• $F(n)$ = $F(n-1)$ + $F(n-2) $ (2 ≤ n)
• 피보나치 수열의 첫 두 항 $ F(1) $ 과 $ F(2) $ 는 각각 1로 초기화됩니다.

② 반복문을 통한 피보나치 수 계산:

• 피보나치 수열의 각 항을 계산하여 배열 d에 저장합니다.

 

 

소스 코드 

function solution(n) {
  const MOD = 1234567;
  const d = [0, 1, 1];

  for (let i = 3; i <= n; i++) {
    d[i] = (d[i - 1] + d[i - 2]) % MOD;
  }

  return d[n];
}

 

• 테뷸레이션(Tabulation)
  • 상향식(Bottom-up)은 반복문을 사용합니다.
  • 메모를 하나의 테이블로 만듭니다. 이를 DP 테이블이라고 합니다.
  • 재귀는 공간 복잡도로 문제가 있을 수 있지만, 상향식 방법은 공간 제약을 덜 받습니다.
  • 알고리즘의 시간 복잡도는 $O(N)$입니다.
• 시간 복잡도:
  • 이 알고리즘은 $O(N)$ 의 시간 복잡도를 가지며, 이는 n번째 피보나치 수를 계산하는 데 매우 효율적입니다.
• 공간 복잡도:
  • 배열 d는 n 크기의 메모리를 사용하므로, 공간 복잡도는 $O(N)$ 입니다. 이 메모리 사용을 줄이기 위해, 단순히 두 개의 변수만을 사용하여 계산을 수행하는 방법도 고려할 수 있습니다.
• 최적화 가능성:
  • 이 문제에서 공간 복잡도를 줄이기 위해, 배열 대신 $F(n-1)$ 과 $F(n-2)$를 저장하는 두 개의 변수만을 사용하여 메모리 사용량을 $O(1)$ 로 줄일 수 있습니다.

 

 

 

 

✔ 출처

https://school.programmers.co.kr/learn/courses/30/lessons/12945