Prm 2 : fibonacci

fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n

• number 타입의 n (n은 0 이상의 정수)

출력

• number 타입을 리턴해야합니다.

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

let output = fibonacci(0); console.log(output); // --> 0 output = fibonacci(1); console.log(output); // --> 1 output = fibonacci(5); console.log(output); // --> 5 output = fibonacci(9); console.log(output); // --> 34

Advanced

• 피보나치 수열을 구하는 효율적인 알고리즘(O(N))이 존재합니다. 재귀함수의 호출을 직접 관찰하여 비효율이 있는지 확인해 보시기 바랍니다.

 

---

기본 풀이

O(2^n)의 시간복잡도를 갖는 방법은 pseudo code로 다음과 같다.

 

return fibonacci(n - 1) + fibonacci(n - 2)

 

 

---

나의 풀이

O(n) 시간복잡도를 갖도록 한다.

피보나치 수열의 초기 2개 값을 지정해놓고, 2개 값을 가리키는 변수들을 증가시켜 가면서 n 값은 1씩 감소시킨다.

 

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  // n이 줄어들어야 한다.
  // base, recursion case
  let [cur, tmp] = [0, 1];
  let aft = 0;
  return recurFunc(0, 1, n);
}
 
const recurFunc = (cur, tmp, n) => {
  if(n === 0) {
    return cur;
  } else {
    aft = cur + tmp;
    cur = tmp;
    tmp = aft;
    return recurFunc(cur, tmp, n - 1);
  }
}

 

 

---

풀이

O(n)의 시간복잡도를 갖는다.

 

fibonacci(10) = fibonacci(8) + fibonacci(7) + fibonacci(7)+fibonacci(6)

과 같이, 중복되서 fibonacci(7) 등이 계산되지 않도록 memo 라는 배열에 정답값을 기록해놓는 방법이다.

 

 

let fibonacci = function (n) {
  const memo = [0, 1];
  const aux = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};

 

memo[n] = aux(n - 1) + aux(n - 2);에서 현재 index 이전과 그 이전값을 더한다는 논리는 같지만, 답을 구한 부분이 있으면 바로 return을 해버린다는 점이 다른 점이라고 할 수 있다.