[JS] 프로그래머스 코딩테스트 연습 | 피보나치 수열

문제 링크: 피보나치

1. 문제

피보나치 수는 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을 완성해 주세요.

---

2. 입출력 예

n	return
3	2
5	5

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

---

3. 나의 풀이

function solution(n) {
  // 이 부분은 안해줘도 통과됨
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }
  //
  
  let fibo = [0, 1];
  for (let i = 2; i <= n; i++) {
    fibo.push((fibo[i - 1] + fibo[i - 2]) % 1234567);
  }

  return fibo.pop();
}

테스트케이스 7번부터 오답이 나오는 이유
이렇게 fibo에 1234567의 나머지를 넣지 않고 피보나치 수열의 마지막 즉, n번째에만 % 1234567을 해주면 피보나치 수열의 경우 수가 빠르게 커지다보니 정수 자료형의 범위를 넘어서기 때문에 에러가 발생

---

4. 다른 사람 풀이

function fibonacci(n) {
  var a = 0, b = 1, f = 1;
  for (var i = 2; i <= n; i++) {
    f = a + b;
    a = b;
    b = f;
  }
  return f;
}

배열을 따로 만들지 않고 변수로 설정해서 푼 경우

---

5. 재귀를 사용해 피보나치 수열 구하기

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

보기에는 쉽지만 시간복잡도가 굉장히 높아짐