14. 피보나치 수 (Level 1, JavaScript)

피보나치 수 (Level 1)

문제

피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다.

2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요. 예를 들어 n = 3이라면 2를 반환해주면 됩니다.

풀이

function fibonacci(num) {
  let arr = [0,1];
  for (let i = 2; i <= num; i++ ) {
      arr.push(arr[i-1]+arr[i-2])
  }
  return arr[num]
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(fibonacci(4))

재귀 함수로 풀어보려 했으나 시간초과로 다른 방법으로 접근

내가 푼 방법이 Dynamic Programming이 맞는지 모르겠지만 따라하려 해봄ㅋㅋ

배열에 fibonacci(0), fibonacci(1)을 할당해놓고 다음 순서를 push로 배열뒤에 삽입하는 식으로 연산에서 중복되는 결과를 최대한 줄이려 함

다른 사람의 풀이

function fibonacci(num) {
  if(num < 2) return num;

  return fibonacci(num-1) + fibonacci(num-2);
}

// 아래는 테스트로 출력해 보기 위한 코드입니다.
console.log(fibonacci(3))
console.log(fibonacci(10))

나는 이렇게 쓰면 통과 안되던데 어떻게 되는거지..

아무튼 위에서 말한 재귀함수로 구현한 방법이 이것!