[Programmers] 피보나치 수(JavaScript)

 

알림

 

본 포스팅은 공부 목적으로 작성된 글이며 상업적 목적으로 절대 사용되지 않았음을 밝힙니다.

 

문제

 

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

코딩테스트 연습 - 피보나치 수

 

피보나치 수는 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) {
    if(n < 2) return n;
    return solution(n - 1) + solution(n - 2);
}

 

 

이처럼 재귀함수를 사용하면 자기 자신을 한 번 더 불러내기 때문에 성능이 매우 느립니다. 보시다시피 위 이미지처럼 테스트 7부터는 받아오는 값이 큰지, 일정 수부터는 시간이 초과되고 런타임 에러까지 나게 됩니다.

 

코드(정확성 테스트 통과)

 

function solution(n) {
    let arr = [0, 1]; // 0, 1
    
    if(n < 2) return arr[n]; // 2보다 작으면 0 or 1 출력
    
    for(let i = 2; i <= n; i++) {
        arr.push((arr[i - 1] + arr[i - 2]) % 1234567);
        // 2일시, arr.push((1 + 0) % 1234567) = arr.push(1)
        // 3일시, arr.push((1 + 1) % 1234567) = arr.push(2)
        // 4일시, arr.push((2 + 1) % 1234567) = arr.push(3)
        // 5일시, arr.push((3 + 2) % 1234567) = arr.push(5)
    }
    
    return arr[n] // arr[2] = 1 / arr[3] = 2 / arr[4] = 3 / arr[5] = 5 ...
}

 

0과 1이 있는 배열을 만듭니다. 입력 받은 숫자가 2보다 작으면, 피보나치 수는 F(0)일 땐 0, F(1)일 땐 1을 출력하기 때문에, 바로 그 숫자의 자리수를 출력하면 됩니다.(0 = 0, 1 = 1이 출력됨.)

 

그리고 반복문을 통해, 초기값이 2부터 시작해 n까지 점차 증가하며, 피보나치 수를 1234567로 나눈 수를 배열에 넣고, 2 이상의 입력값 n은, 배열에서 본인 수의 위치를 리턴하면 됩니다.

 

왜냐하면 0과 1은 바로 0과 1로 출력되게끔 코드를 작성했고, 반복문이 2부터 시작해 n의 크기까지 계속 증가하기 때문에, 2 이상의 n 값은 arr[n]과 같기 때문입니다.