[프로그래머스] 피보나치 수

피보나치 수

문제 설명

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

---

나의 풀이

1. F(0) = 0, f(1) = 1 을 변수로 생성한 뒤 for 문을 f(2) 부터 돌린다.

2. F(n)이 될 때 까지 answer = F(n-2) + F(n-1) % 1234567의 값을 answer에 넣어준다.

3. F(n)이 되기 전까지 F(n-2) 즉 num1의 값은 F(n-1) 즉 num2로 바꿔준다.
   (왜냐하면 다음 피나치보 수의 F(n-2)의 값은 현재 피나치보 수의 F(n-1)의 값이기 때문이다.)

4. F(n)이 되기 전까지 F(n-1) 즉 num2의 값은 answer 값으로 바꿔준다.
   (3번의 이유와 동일)

5. answer를 return 한다.

function solution(n) {
    var answer = 0;
    let num1 = 0;
    let num2 = 1;
  
    for(let i=2; i<=n; i++) {
        answer = (num1 + num2) % 1234567;
        num1 = num2;
        num2 = answer;
    }
  
    return answer;
}

배운점

처음 코드는 아래와 같았다. 하지만 에러가 났는데 이유는 다음과 같다.

function solution(n) {
    var answer = 0;
    let num1 = 0;
    let num2 = 1;
  
    for(let i=2; i<=n; i++) {
        answer = (num1 + num2);
        num1 = num2;
        num2 = answer;
    }
  
    return answer % 1234567;
}

n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가 오버플로우가 납니다.

예를 들어

47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다.
100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다.

💡 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있습니다.

💡 적용 코드

for(let i=2; i<=n; i++) {
        answer = (num1 + num2);
        num1 = num2;
        num2 = answer;
    }
return answer % 1234567;

for(let i=2; i<=n; i++) {
        answer = (num1 + num2) % 1234567; // 매번 계산 결과에 나머지 값을 넣는다.
        num1 = num2;
        num2 = answer;
    }
return answer;

느낀점

맨 처음에는 왜 1234567의 나머지 값을 return 하는지 의아했는데 위의 개념을 알고 나니 이해가 갔다. 컴퓨터 공학에 대해서 알았더라면 왜 틀렸는지 곰곰히 생각하다보면 알 수 있었을텐데 전혀 모르는 상황에서는 왜 오답인지 알 수 없었다. 프로그래머스의 좋은 점은 질문하기 기능을 통해 많은 개발자분들께 힌트를 얻을 수 있는 점인 것 같다. 그리고 컴퓨터 공학의 개념도 코딩할 때 필요하다는 것을 느꼈다..