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

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

프로그래머스

 

문제

 

 

 

코드

 

function solution(n) {
    let arr = [100000]
    let m = 1234567
    arr[0] = 0;
    arr[1] = 1;
    
    for(let a = 2; a < n+1; a++){
        arr[a] =  Number(arr[a-1]) % m  + Number(arr[a-2]) % m;
    }
    return arr[n] % 1234567
}

 

• 처음엔 재귀호출로 풀었으나 테스트케이스 7~14에서 런타임 에러 발생
  • 런타임 에러가 나는 이유: 자바스크립트는 재귀 호출을 할 수 있는 횟수가 정해져 있고, 횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있다.
  • 해결방법: 동적계획법
• 동적계획법(Dynamic Programming)이란?
  • for문을 사용해서 첫 번째, 두 번째, 세 번째, ..., n번째 피보나치 수를 순서대로 구해 배열에 저장해 두는 것
• 동적계획법으로 푼 후 7~14번 테스트 케이스에서 "실패"
  • 실패 이유: n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우 발생
  • 해결방법: 모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 한다.

[나머지 연산의 성질]

(a + b) % m = ((a % m) + (b % m)) % m