nthFibonacci - 피보나치 수열의 n번째 숫자 찾기

JavaScript로 작성

---

피보나치는 앞의 두 숫자의 합으로 이어진 수열이다. 첫번째는 0, 두번째는 1로 정해져 있고, 그 뒤부터 법칙에 따라 수열이 만들어짐

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 

조건

1. 매개변수로 n을 받고, 피보나치 수열의 n번째 숫자를 반환한다.

2. 시간복잡도는 O(N)

3. 재귀도 써 보고 반복도 써 봐라 (근데 재귀로 풀면 시간 복잡도는 못 맞추는 것 같다?)

 

피보나치 자주 풀었지만 풀 때마다 걍 새로 푸는 느낌,, 근데 코드 보면 맨날 똑같이 적었.. 소름

 

재귀 ver

 

반복 ver

var nthFibonacci = function (n) {

  var array = [0, 1];
  for(var i=2; i<n; i++){
    array.push(array[i-2]+array[i-1]);
  }

  if(n===0 || n===1){
    return array[n];
  }else{
    return array[n-2] + array[n-1];
  }

};