피보나치 수 런타임 에러

문제

피보나치 수는 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을 완성해 주세요.

 

문제풀이

function solution(n) {
    let newArr = [0, 1, 1]
    
    let fib = (n) => {
        if(newArr[n] !== undefined){
        return newArr[n]
        }
        newArr[n] = fib(n-1) + fib(n-2)
        return newArr[n]
    }
    
    console.log(newArr)
    return fib(n)%1234567
}

 

#1

피보나치 수를 구하는 함수를 만듬. 그 과정에서 재귀함수를 사용했음

⇒ 재귀함수를 사용하게 되면, 시간복잡도가 급격하게 올라가게 된다고 한다.

 

#2

메모이제이션을 사용하여, 배열을 만들어 놓고 그 배열안에 n번째에 해당하는 수가 존재하지않으면 피보나치 함수를 이용해 n번째 수를 구한다. 수가 존재한다면 그냥 배열에 있는걸 꺼내어 쓴다.

⇒ 왜인지 모르겠으나 자꾸 오류가 뜸. 이상해서 찾아보니

 

자바스크립트는 자료형을 지정해주지 않아도 알아서 할당해준다.

그러나 피보나치수는 n이 클수록 수가 급격하게 늘어나는 특징이 있음. n이 매우 큰 경우 언어가 표현할 수 있는 자료형의 범위를 넘어서서 오버플로우가 난것이다.

 

#3

배열에 저장하기 전, 문제에서 제시한 1234567로 나눠 저장한다.

function solution(n) {
    // 정해진 피보나치 수 초기화
    let fib = [0, 1];
    
    for (let i = 2; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
    }
    
    return fib[n];
}

 

경험해 보지 못한 에러를 겪어볼 수 있어서 한번 풀어볼만한 문제였다.