[프로그래머스] Lv.2 피보나치 수 JavaScript

문제 설명

피보나치 수는 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 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

문제풀이

💡 문제풀이 과정

• 피보나치 수에는 다음과 같은 규칙이 있다.

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

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

       a1 + b1 = c1
       a2(=b1) + b2(=c1) = c2(=a2+b2)
       a3(=b2) + b3(=c2) = c3(=a3+b3)

• 주어진 매개변수 n은 2이상이라는 조건이 있는데, F(2) = F(0) + F(1) = 0 + 1 = 1이므로,
  a = 0, b = 1, result = 1이라는 초기값을 각각 주었다. 해당 식은 누적되어야 하며, 수열의 횟수를 지정하기 위해 for() 반복문을 사용한다.
• ❓ 7번째 테스트 부터 실패하는 경우: 마지막에 1234567로 나눈값의 나머지를 리턴하게되면, 오버플로우가 발생한다고 한다. 따라서 반복문 안에서 결과값에 % 1234567을 함으로써 오버플로우가 발생하지 않게 해야 통과 가능하다.
  (cf. Overflow란? 말그대로 ‘넘치다’, ‘초과하다’라는 사전적 의미로, 한정된 메모리의 용량을 초과하는 값이 들어갈때 발생하는 오류이다.)
  ⬇️ 자세한 설명은 아래 프로그래머스 답변 참고.
  - "n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다. 예를 들어 47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다. 100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다. 💡그럼 코드를 어떻게 바꾸면 좋나요? 모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주세요."

---

• 답안 2번: 다른 사람의 풀이 참고

✅ 답안 #1

function solution(n) {
  let a = 0, b = 1, result = 1;
  for (let i = 1; i < n; i++) {
    result = (a + b) % 1234567;
    a = b;
    b = result;
  }
  return result;
}

✅ 답안 #2

function solution(n) {
   var result = [0 , 1];
   while ( result.length !== n + 1) {
       var fibonacci = (result[result.length - 2] + result[result.length - 1]) % 1234567
       result.push(fibonacci);
   }
    return result[n];
}