피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
n | return |
---|---|
3 | 2 |
5 | 5 |
피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.
💡 문제풀이 과정
- 피보나치 수에는 다음과 같은 규칙이 있다.
F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1 F(2) = 0 + 1 = 1 F(3) = 1 + 1 = 2 F(4) = 1 + 2 = 3 F(5) = 2 + 3 = 5 a1 + b1 = c1 a2(=b1) + b2(=c1) = c2(=a2+b2) a3(=b2) + b3(=c2) = c3(=a3+b3)
- 주어진 매개변수
n은 2이상
이라는 조건이 있는데,F(2) = F(0) + F(1) = 0 + 1 = 1
이므로,
a = 0, b = 1, result = 1
이라는초기값
을 각각 주었다. 해당 식은 누적되어야 하며, 수열의 횟수를 지정하기 위해for()
반복문을 사용한다.- ❓ 7번째 테스트 부터 실패하는 경우: 마지막에 1234567로 나눈값의 나머지를 리턴하게되면, 오버플로우가 발생한다고 한다. 따라서 반복문 안에서 결과값에 % 1234567을 함으로써 오버플로우가 발생하지 않게 해야 통과 가능하다.
(cf.Overflow
란? 말그대로 ‘넘치다’, ‘초과하다’라는 사전적 의미로,한정된 메모리의 용량을 초과하는 값이 들어갈때 발생하는 오류
이다.)
⬇️ 자세한 설명은 아래 프로그래머스 답변 참고.
- "n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다. 예를 들어 47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다. 100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다. 💡그럼 코드를 어떻게 바꾸면 좋나요? 모든 단계에서 % 연산을 사용하여, 모든 연산에서 오버플로우가 일어나지 않게 만들어 주세요."
- 답안 2번: 다른 사람의 풀이 참고
✅ 답안 #1
function solution(n) {
let a = 0, b = 1, result = 1;
for (let i = 1; i < n; i++) {
result = (a + b) % 1234567;
a = b;
b = result;
}
return result;
}
✅ 답안 #2
function solution(n) {
var result = [0 , 1];
while ( result.length !== n + 1) {
var fibonacci = (result[result.length - 2] + result[result.length - 1]) % 1234567
result.push(fibonacci);
}
return result[n];
}