[Algorithms] 피보나치수

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

프로그래머스

 

쉬워보이죠? 저도 그래보였어요. 당연히 재귀로 풀면 될 줄 알았습니다.

근데 시간복잡도에서 아작이 나버렸죠. 이걸 재귀로 풀면 매우 매우 매우 매우 매우 매우 매우 매우 느려집니다.

코드부터 던지고 설명하겠습니다.

function solution(n) {    
    let f0 = 0
    let f1 = 1
    
    for(let i = 2; i <= n; i++) {
        const next = (f0 + f1) % 1234567
        f0 = f1
        f1 = next
    }

    return n === 0 ? 0 : f1
}

피보나치 수열의 시작 값인 F(0) = 0, F(1) = 1 이 두 개를 f0, f1에 담아둡니다.

그리고 이제 2부터 n까지 반복문을 돌면서 피보나치 수를 계산합니다.

• 현재까지의 두 수(f0 + f1)를 더한 게 다음 수입니다.
• 더한 값을 1234567로 나눈 나머지를 구해서 next에 저장합니다.
• 그리고 f0, f1을 한 칸씩 앞으로 밀어주면서 갱신합니다.

즉, 값을 갱신해가면서 n번째 피보나치 수까지 가보는 거죠.

끝-