[프로그래머스] 연습문제 > 피보나치 수 - 자바스크립트

문제 설명

피보나치 수는 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은 1이상, 100000이하인 자연수입니다.

입출력 예

nreturn

3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

<아이디어>

피보나치의 수의 아이디어는 없다. 그냥 피보나치 -> 재귀, 그러나 효율성을 따지면 다른 방법이 필요하다.

<내 코드>

function solution(n) {
    let answer = 0;
    let test = [0,1];
    if(n < 2) return n;
    answer = fibonacci(n) % 1234567;
    return answer;
}

function fibonacci(num) {
  if(num < 2) return num;
  return fibonacci(num-1) + fibonacci(num-2);
}

시간초과와 런타임 에러가 둘다 뜬다. 

런타임 에러는 이름 그대로 돌아가는 도중에 터지는 것이다. 피보나치에서 터지는 이유는 하나다. 자바스크립트 엔진의 콜스택이 넘어서 터지던가, 아니면 number의 표현을 넘어서는 경우일때이다.

2021.03.17 - [개발/자바스크립트] - [자바스크립트] number 타입에 대하여

[자바스크립트] number 타입에 대하여

이전 글에서 number 타입에 대해 정리하면서 표현가능한 값의 한계가 있음을 알게되었다. 자바스크립트의 number는 64비트 부동소수점을 이용하기 때문이다. 그래서 여러가지 필요한 비트를 빼고  2의 53승까지 표현가능했던 걸로 기억한다. 

쨋든 숫자 표현에는 한계가 있고 어느 순간 터지는 한계가 있다. 

번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수

해서 문제에서도 이렇게 특정값으로 나눈 나머지라는 제한을 둔다. 

근데 저 위에 코드에서는 마지막 값에 대해서만 1234567로 몫을 구한다. 아시다시피 피보나치 수는 뒤로 갈수록 급격하게 증가한다. 따라서 목표에 도달하기 전에 터지는 수가 있다. 그러니 다음 수를 구할때마다 1234567로 나눈 몫을 계산해두면 좋다.

두번째로 시간초과이다.

위에 구현한 피보나치 로직은 재귀적으로 동작한다. 로직은 재귀적으로 돌아가나 이전 값을 구하기 위해 그 아래값을 구하고 그 값의 아래값을 또 구하는 방식이다.

따라서 피보나치 로직을 최적화하는 방법은 배열을 이용해서 이전 값을 계속 저장하면서 하는 것이다.

function solution(n) {
  let answer = 0;
  let fiboArray = [0, 1, 1];
  if (n < 3) return n;
  for (let i = 3; i < n + 1; i++) {
    fiboArray[i] = (fiboArray[i - 1] % 1234567) + (fiboArray[i - 2] % 1234567);
  }
  answer = fiboArray[n];
  answer = answer % 1234567;

  return answer;
}

보면 fiboArray를 이용하여 계속 추가해나간다.  이제 다음 값을 구하기 위해 이전에 구해놨던 배열값을 가져와서 빠르게 계산할수 있다. 

에러없이 통과됬다. 다만 여기서 한발짝 더 나아가서 이젠 메모리를 최적화 해보자.

아주 간단하다. 위의 로직은 하나의 값이 들어올때마다 배열의 크기가 늘어난다.

하지만 피보나치는 전, 전전의 값만 필요하다. 극단적으로 3가지 크기의 배열만 가지고도 계산이 가능하다.

이것을 한번 이용해보자.

function solution(n) {
  let answer = 0;
  let test = [0, 1, 1];
  if (n < 3) return n;
  for (let i = 3; i < n + 1; i++) {
    test[i % 3] = (test[(i - 1) % 3] % 1234567) + (test[(i - 2) % 3] % 1234567);
  }
  answer = test[n % 3];
  answer = answer % 1234567;

  return answer;
}

거의 비슷한 로직인데 이번엔 for문의 index에도 %3를 넣어서 원형 배열처럼 이용하도록 만들었다.

그리고 그 크기는 언제나 처음 선언한 길이 3의 배열이다.

이로써 시간복잡도, 공간복잡도 둘다 해결을 했다. 

시간복잡도는 O(2^n) -> O(n)으로
공간복잡도는 O(n) -> O(3)        // 이 표현이 맞는지 모르겠다. 아무튼 길이 3짜리 배열 하나다.

다만 시간복잡도는 행렬을 이용하는 로직으로 O(log2(N))까지 줄일수 있다.