74. 피보나치 수 Javascript

https://programmers.co.kr/learn/courses/30/lessons/12945

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

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - n 번째 피보나치 수를 1234567로 나눈 나머지를 구하라
• 주어진 자료는 무엇인가?
   - 숫자 n
• 조건은 무엇인가?
   - n은 2 이상 100,000 이하인 자연수이다.
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
   - 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 이다.

2. 계획

1. numbers = [0,1]을 만든다 (F(0)과 F(1)을 의미)
2. 반복문을 실행하면서 numbers에 수를 더하고 마지막 값을 리턴한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (n) => {
 let numbers = [0, 1];
  for (i = 2; i <= n; i++){
     numbers.push((numbers[i - 1] % 1234567) + (numbers[i - 2] % 1234567) % 1234567);
  }

  return numbers[n] % 1234567;
};

test('fibonacci', () => {
  expect(fibonacci(3)).toEqual(2);
  expect(fibonacci(5)).toEqual(5);
});

4. 반성

• 처음에 재귀로 문제를 풀었다가 시간 초과로 테스트 통과가 되지 않았다. 그래서 반복문을 사용하였다.
• numbers에 값을 넣는 부분을 numbers.push((numbers[i - 1] % 1234567) + (numbers[i - 2] % 1234567) % 1234567); 이렇게 해준 이유는  자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다. 라는 질문글에 올라온 설명을 보고 해결할 수 있었다.