프로그래머스 피보나치 수 문제풀이, 해설

프로그래머스 피보나치 수 문제풀이, 해설

 

 

프로그래머스 피보나치 문제 소개와 해설, 필자의 문제풀이 과정에 대해 소개하겠습니다. 아래 풀이 과정을 보면서 코딩에 있어서 유익한 인사이트를 얻길 바랍니다.  

 

 

프로그래머스 피보나치 수 문제

 

프로그래머스

 

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 주어진 제한 사항에 따라 n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수를 작성해야 합니다.

 

기존 코드

function solution(n) {
  let answer = 0;

  let F1 = 0;
  let F2 = 1;

  for (let i = 2; i <= n; i++) {
    answer = F1 + F2;

    F1 = F2;
    F2 = answer;
  }
  return answer;
}

 

 

문제 발생

코드는 대부분 동작하지만, 특정 케이스에서 오류가 발생합니다. 수가 커질수록 계산을 못하는 듯 했습니다.

 

 

오류 원인

큰 수의 피보나치 수는 자료형의 범위를 넘어가 오버플로우가 발생합니다. 코드 수정 방안 모든 연산에서 % 연산을 사용하여, 오버플로우가 일어나지 않도록 수정해야 했었습니다.

 

 

수정한 코드

function solution(n) {
  let answer = 0;

  let F1 = 0;
  let F2 = 1;

  for (let i = 2; i <= n; i++) {
    answer = F1 + F2;

    if (answer > 1234567) answer %= 1234567;

    F1 = F2;
    F2 = answer;
  }
  return answer;
}

 

코드 설명

1. 초기 두 값을 0과 1로 설정하여 피보나치 수열을 시작합니다.
2. 반복문을 통해 n번째까지의 피보나치 수를 구합니다.
3. 중간 결과값이 1234567보다 큰 경우 % 연산을 통해 나머지를 구합니다.
4. F1과 F2를 갱신하면서 반복문을 진행합니다.

 

예시 설명

예시로 주어진 코드는 3과 5에 대해 각각 2와 5를 반환해야 합니다. 수정한 코드는 모든 연산에서 % 1234567을 적용하여 오버플로우를 방지하고 정확한 결과를 제공할 수 있었습니다.

 

▼ 아래 문제 풀어보셨나요? ▼

 

프로그래머스 문자열 다루기 기본 해설, 인기 있는 문제풀이

 

프로그래머스 시저함수 문제 풀이, 해설, 알고리즘 코딩테스트