1. 문제
2. 풀이
3. 결과
4. 참고

1. 문제

---

피보나치 수

문제 링크

문제 설명

피보나치 수는 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, ... 와 같이 이어집니다.

---

분류

• 다이나믹 프로그래밍

2. 풀이

---

다이나믹 프로그래밍을 이용하여 계산 결과를 memoization한다.

피보나치 수열을 구현하는 방법에는 크게 3가지가 있다.

1. 재귀
2. 동적 프로그래밍(top-down, bottom-up)
3. 반복문

해당 문제는 동적 프로그래밍 bottom-up 방식을 사용하여 해결할 수 있다.

주의할 점

1. 시간 초과
   • 처음에는 일반적인 재귀로 문제를 풀었는데, 테스트 케이스 7번부터 시간 초과가 발생한다.
   • 다음으로는 동적 프로그래밍 top-down 방식으로 문제를 풀었는데, top-down 방식도 재귀를 이용한 것이므로 시간 초과가 발생하였다.
   • 마지막으로 동적 프로그래밍 bottom-up 방식을 이용하여 문제를 해결하였다.
2. 1234567으로 나누는 위치
   • 동적 프로그래밍 bottom-up 방식을 이용했는데, 최종 반환할 때 나머지 연산을 하였더니 테스트 케이스 7번부터 실패가 발생한다. 실패하는 이유는 for문으로 피보나치 수열을 계산하는 와중에, 결과가 자료형의 크기를 초과하여 정확한 값을 계산하지 못하기 때문이다. 그러므로 계산을 한 결과에 바로바로 나머지 연산을 해준 값을 저장하면 자료형을 초과하지 않은 계산 결과가 출력될 수 있다.

제출

// // 재귀: 실패
// function fibo(n) {
//     if(n === 0) return 0;
//     if(n === 1) return 1;
//     return fibo(n - 1) + fibo(n - 2);
// }

// // 동적 계획법(top-down): 실패
// function fibo(n, d = []) {
//     if(n < 2) return n;
//     if(d[n]) return d[n];
    
//     d[n] = fibo(n - 1) + fibo(n - 2);
    
//     return d[n] % 1234567;
// }

function solution(n) {
    let arr = [0, 1];
    
    // 동적 계획법(bottom-up): 성공
    for(let i = 2; i <= n; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567; // 나누는 위치 주의
    }
    
    return arr[n];
}

3. 채점 결과

테스트 1 〉	통과 (0.05ms, 29.2MB)
테스트 2 〉	통과 (0.05ms, 30.3MB)
테스트 3 〉	통과 (0.04ms, 30.1MB)
테스트 4 〉	통과 (0.04ms, 29MB)
테스트 5 〉	통과 (0.04ms, 30.3MB)
테스트 6 〉	통과 (0.04ms, 30.2MB)
테스트 7 〉	통과 (0.25ms, 30MB)
테스트 8 〉	통과 (0.10ms, 30.3MB)
테스트 9 〉	통과 (0.07ms, 30.3MB)
테스트 10 〉	통과 (0.15ms, 30.4MB)
테스트 11 〉	통과 (0.11ms, 30.3MB)
테스트 12 〉	통과 (0.12ms, 30MB)
테스트 13 〉	통과 (4.72ms, 34.3MB)
테스트 14 〉	통과 (4.51ms, 34.6MB)

• 정확성 : 100.0
• 합계 : 100.0 / 100.0

4. 참고