[JS] 연습문제 - 피보나치 수

// function solution(n) {
//     const fibonacci = (n) => {
//         if (n === 0) {
//             return 0;
//         } else if (n === 1) {
//             return 1;
//         } else {
//             return fibonacci(n - 2) % 1234567 + fibonacci(n - 1) % 1234567;
//         }
//     }

//     return fibonacci(n) % 1234567;
// }

function solution(n) {
  let fibonacciArr = new Array(n + 1);
  fibonacciArr[0] = 0;
  fibonacciArr[1] = 1;

  for (let i = 2; i < n + 1; i++) {
    fibonacciArr[i] = (fibonacciArr[i - 2] + fibonacciArr[i - 1]) % 1234567;
  }

  return fibonacciArr[n];
}

 

프로그래머스

코딩테스트 연습 - 피보나치 수

 

1. n = 0과 n = 1일 때, 리턴값이 각각 0 과 1로 해준다.
2. 이 외의 값에 대해서는 재귀를 통해 해당 값(n)에 대해 n-2, n-1에 대한 함수값을 더해서 리턴해준다.
3. 문제에서 주어진 조건으로 1234567로 나눈 나머지 처리를 해준다.
   그런데 웬걸... 런타임 오류 및 시간 초과가 발생하였다.
   해서 아래와 같이 반복문을 이용하여 풀어주었더니 해결되었다.

+추가
(A+B)%C = ((A%C)+(B%C))%C 인 점을 생각하자!
문제에서 1234567로 나눈 나머지에 대한 조건(사실은 힌트)을 건 이유는, 언어마다 각각의 자료형의 최대 크기가 있다.(보통 int형에 대해 4바이트, 즉 32 비트 -> 1이 32개인 이진수가 최대값, 사실 음수까지 따지면 그 절반이 최대값) 그렇기에 나머지 처리를 해서 최대값을 넘어가는 숫자에 대해서 발생하는 문제를 없게 하기 위함이다.