📕 문제

문제설명

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

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

🤔 고민과정

• 테스트 7부터 14번까지 실패 했다. 이유가 뭘까?

▶ 실패 코드

function solution(n) {
    let fibonacci = [0, 1];

    // 2번째 항부터 계산하여 배열에 추가
    for (let i = 2; i <= n; i++) {
        fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
    }

    return fibonacci[n] % 1234567;
}

• 피보나치 수열은 매우 빠르게 값이 커집니다. 따라서 피보나치 수를 계산할 때 값이 커지면, 계산 도중에 숫자가 매우 큰 값이 되어 정수 오버플로우나 메모리 문제를 일으킬 수 있습니다.
• 실패 코드에서는 최종 결과를 반환할 때만 모듈러 연산(% 1234567)을 적용하기 때문에, 배열 fibonacci 내에 있는 값들이 매우 커질 수 있습니다. 이는 중간 계산에서 큰 숫자가 발생하여 오버플로우가 일어나거나, 값이 매우 커져 메모리를 많이 사용하게 되며 결과적으로 올바른 값을 얻지 못할 수 있습니다.
• 성공 코드에서는 매 단계마다 fibonacci[i] 값을 1234567로 나눈 나머지 값을 저장합니다. 이렇게 하면 큰 수가 계속해서 계산되지 않고, 항상 1234567 이하의 작은 값으로 유지됩니다.

모듈러 연산
어떤 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, "나머지 연산"이라고도 불립니다.
모듈러 연산을 사용하는 이유는, 큰 숫자를 다룰 때 메모리나 연산 시간 측면에서 효율성을 높이고, 프로그램이 정상적으로 동작하도록 하기 위함입니다.
큰 숫자를 그대로 사용하면 계산 성능이 저하되거나, 메모리 오버플로우와 같은 문제들이 발생할 수 있기 때문입니다.

✅ 결과물

function solution(n) {
    // 피보나치 수는 0번째 항은 0, 1번째 항은 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
    let fibonacci = [0, 1];

    // 2번째 항부터 계산하여 배열에 추가
    for (let i = 2; i <= n; i++) {
        fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % 1234567;
    }

    return fibonacci[n];
}