n번째 피보나치 수열 구하기

알고리즘 면접 대비용으로 작성하는 시리즈!

문제와 설명은 알고엑스퍼트를 참고했다.

 

목표:

두가지 이상의 풀이방법을 구현하고 설명하기

시간/공간 복잡도를 나타내기

왜 이 풀이가 저 풀이보다 성능이 나은지 논리적으로 설명하기

면접질문에 대답한다고 생각하고, 핵심을 설명하되 말을 너무 길게 하지 않기 (개인적으로는 세 문장이 적절하다고 생각)

분명하고 적절한 용어를 사용해서 설명하기

 

질문:

n번째 피보나치 수열을 구해보세요

 

예시1

Input:

2

Output:

1

예시2

Input:

6

Output:

5

 

Idea

피보나치 수열은 0, 1, 1, 2, 3, 5.. 와 같이, 처음 두 수는 0과 1에서 시작하며, n>2 인 n번째 수는 n-1번째 수 + n-2번째 수이다.

 

Solution 1

재귀(Recursive)를 사용해서 풀어보자

function getNthFib(n) {
  if (n === 1)
    return 0;
  if (n === 2)
    return 1;

  return getNthFib(n-1) + getNthFib(n-2)
}

· getNthFib(n) = getNthFib(n-1) + getNthFib(n-2) 라는 점을 염두하여 재귀로 풀었다.

· 피보나치 수열의 첫 번째, 두 번째 숫자는 예외적인 항목이므로 재귀 함수를 빠져나가기 위한 조건인 Base case가 되어, if문을 통해 먼저 값을 반환한다.

 

· 시간복잡도/공간복잡도: O(2^n)/O(n)

사실 불필요한 계산이 많아, 시간복잡도가 좋지 않기 떄문에 이러한 방식은 naive하다고 표현할 수 있다. 예를 들면 getNthFib(6)을 구하기 위해 getNthFib(5)와 getNthFib(4)를 계산하는데, getNthFib(5)는 다시 getNthFib(4)와 getNthFib(3)을 계산하게 되므로 같은 값을 여러번 계산하게 되기 때문이다.

재귀의 경우 콜스택을 사용하게 되므로 Base case에 도달하기 전까지 최대 n개의 스택이 쌓일 수 있어 공간복잡도는 O(n)이 된다.

 

 

 

 

🧐 Solution1보다 성능을 향상시킬 수 있는 방법이 있을까? 생각해보자.

 

 

 

 

Solution 2

Memoization(캐싱)을 사용해서 풀어보자

let fib = [null, 0,1];
function getNthFib(n) {
  if (typeof fib[n] !== "undefined") return fib[n];

  fib[n] = getNthFib(n-1) + getNthFib(n-2);
  return fib[n];
}

· Memoize란, 계산한 값을 어딘가에 메모(저장)해두는 것이다.

· 피보나치 수열을 저장할 fib라는 배열을 둔다.

· 배열에 값이 있는 경우에는 저장된 값을 반환하고 없는 경우에는 값을 계산하여 저장한다.

(나는 배열을 사용했지만 해쉬 테이블을 사용할 수도 있다. 0번째를 고려하지 않아도 되어서 더 나을지도..)

 

· 시간복잡도/공간복잡도: O(n)/O(n)

피보나치 수를 한 번은 계산하게 되며, 계산한 뒤에는 배열에서 꺼내오기만 하면 되므로 O(n)의 시간복잡도를 가진다.

공간복잡도의 경우 값을 저장하는 배열 O(n)과, Solution1에서도 존재하는 콜스택 문제 O(n)가 있으므로 O(n)이 된다.

 

 

 

 

🧐 Solution2보다 성능을 향상시킬 수 있는 방법이 있을까? 생각해보자.

 

 

 

 

Solution3

Iterative하게 구현해보자

function getNthFib(n) {
  let prevPrevN = 0;
  let prevN = 1;
  let curr = null;

  if (n === 1) return prevPrevN;
  if (n === 2) return prevN;
  
  for (let i = 3; i <=n; i++){
    curr = prevPrevN + prevN;
    
    prevPrevN = prevN;
    prevN = curr;
  }

  return curr;
}

· n번째 피보나치 수를 구하기 위해서는 n-1번째와 n-2번째의 피보나치 수를 알기만 하면 된다는 점에서 착안하여 Iterative한 함수를 작성할 수 있다.

· 예외적인 첫 번째, 두 번째 숫자는 미리 반환하며, n>2인 경우에는 현재 값(n)을 이전 값(n-1, prevN) + 더 이전 값(n-2, prevPrevN)으로 계산한다.

· prevN과 prevPrevN에는 다음 값(n+1)을 계산하기 위해 값을 업데이트한다.

 

· 시간복잡도 / 공간복잡도: O(n) / O(1)

피보나치 수열을 한 번은 계산해야하기 때문에 시간복잡도는 O(n)이며, 상수에 값을 저장하기만 하며 콜스택을 신경쓸 필요가 없어서 공간복잡도는 O(1)이 된다.