Programmers: 피보나치 수

문제

문제 설명

피보나치 수는 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

풀이 과정

풀이1

처음에는 당연히도 재귀 함수로 풀려고 했다.


const getFibonacci = (value) => {
    if(value === 1 || value === 0) return value;
    return getFibonacci(value - 1) + getFibonacci(value - 2);
}

function solution(n) {
    return getFibonacci(n) % 1234567
}

구현 내용을 보면 알 수 있지만, 문제에서 말하고자 하는 바를 그대로 구현했다.

결과는 아래와 같다.

시관 초과와 런타임 에러 등이 난 것을 봐서는 js에서 허용하는 recursion limit을 넘어간 듯 했다.

성능을 위해서는 recursive function을 사용하지 않는 것이 좋을 듯 하여 반복문을 사용하기로 했다.

풀이2


function solution(n) {
    const memoizedFibonacci = [0, 1];
    
    for(let i = 2; i < 100001; i++){
        memoizedFibonacci[i] = memoizedFibonacci[i - 1] + memoizedFibonacci[i - 2];
    }
    
    return memoizedFibonacci[n] % 1234567;
}

결과는 아래와 같았다.

실패가 왜 나는거지 라는 생각으로 최대 입력 값인 100,000을 직접 input으로 넣어 함수를 실행해보니, 출력 값이 NaN이 나오는 것 아닌가?

일단 방식을 바꿔보기로 하고, 왜 이런 일이 일어난건진 풀고 나서 알아보기로 했다.

풀이3

아무래도 NaN이 나온 이유는 수가 커서 이지 않을까? 라는 생각에 어차피 값은 1234567로 나눈 값의 나머지만 필요한 것이기에, 저장할 때부터 나머지 값을 저장하기로 했다.


function solution(n) {
    const memoizedFibonacci = [0, 1];
    
    for(let i = 2; i < 100001; i++){
        memoizedFibonacci[i] = (memoizedFibonacci[i - 1] + memoizedFibonacci[i - 2]) % 1234567;
    }
    
    return memoizedFibonacci[n];
}

바로 성공했다.

풀이2 이슈 확인

평소에 개발하면서도 이런 상황을 본 적이 없어서 chatgpt에게 물어보았다.

나는 따로 BigInt 자료형을 쓰고있는 것은 아니었기 때문에, 테스트 중 배열 요소에 들어가는 값이 2^53 - 1보다 큰 경우가 있었나보다.

염두해두자..

python 풀이


def solution(n):
    memoized_fibonacci = [0 for _ in range(100001)]
    memoized_fibonacci[1] = 1
    for i in range(2, 100001):
        memoized_fibonacci[i] = (memoized_fibonacci[i - 1] + memoized_fibonacci[i - 2]) % 1234567
        
    return memoized_fibonacci[n]

Programmers: 피보나치 수 - #12945

문제