피보나치 문제풀이 두가지: O(n),O(n^2)

문제:

아래와 같이 정의된 피보나치 수열 중 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(n^2)의 시간 복잡도를 가진다.

한마디로 시간이 아주 오래걸리고 성능이 떨어진다는 뜻인데 해당 부분에 대해 더 자세히 알고 싶다면

알기 쉽게 잘 정리한 글이 있어서 링크 첨부한다. 

하지만 메모이제이션(memoization)기법을 이용하면 시간 복잡도를 O(n)으로 낮출 수 있다.

 

 

첫번째 풀이: O(n^2)

function fibonacci(n) {
  //base case
  if(n===0||n===1)return n 
  //recursive case
  else return fibonacci(n-2) + fibonacci(n-1)
}

한번 돌때마다 fibonacci(n-2), fibonnaci(n-1)이 각각 실행된다.

그리고 또 fibinacci(n-2)는 또 fibonacci(n-2-2),fibonacci(n-2-1) 두 함수를,

fibonacci(n-1)은 fibonacci(n-1-2), fibonacci(n-1-1) 가 또 시행된다.

다시말해 두번 도는 동안 함수가 총 2^2만큼 시행되는 것이다. 

 

그런데 사실 fibinacci(n-2)은  fibonacci(n-1-1)과 동일하고,

fibonacci(n-2-1)은  fibonacci(n-1-2)와 동일한데 매번 다시 연산되고 있는 것이므로

이미 수행했던 연산이 아주 많이 되풀이 되고 있는 것이다.

 

따라서 n의 값이 커질수록 쓸모없는 연산으로 시간복잡도만 커질 것이다.

그래서 이런식으로 문제를 푸니 시간초과로 패스가 나지 못했다.

 

 

첫번째 풀이: O(n) 메모이제이션 활용

function fibonacci(n) {
  //base case:
  const memo = [0,1]
  //recursive case:
  const aux = (n) => {
  	//이미 연산했던 값이라 memo배열에 들어있다면 그 값을 사용
    if(memo[n]!== undefined) return memo[n]
    //이미 연상했던 값이 없다면 값을 계산 후 저장
    memo[n] = aux(n-2) + aux(n-1) 
    //memo[2] = aux(2-2) + aux(2-1) => memo[0] + memo[1] = memo[2]저장
    //memo[3] = aux(3-2) + aux(3-1) => memo[1] + memo[2] = memo[3]저장
    //memo[4] = aux(4-2) + aux(4-1) => memo[2] + memo[3] = memo[4]저장
    //memo[5] = aux(5-2) + aux(5-1) => memo[3] + memo[4] = memo[5]저장
    return memo[n]; 
  }
  return aux(n) //aux(5)
}

이미 구한 값을 메모리에 저장해두고 다시 사용하는 기법을 메모이제이션(memoization)이라고 한다.

이렇게 되면 이미 저장되어 있는 연산값은 그걸 불러와서 쓰기 때문에,

반복되어 실행되는 연산이 사라진다. 

실질적으로는 배열의 앞두요소를 더해서 새로운 요소로 넣어주고를 되풀이 하는 것 뿐이다.

 

클로저를 사용해서 외부 memo배열에 저장되는 형태를 기억하자.

 

추가로 아래와 같은 배열의 성질도 확인해 둔다.

const arr = [1,2]
arr[4] = 5
arr // (5) [1, 2, empty × 2, 5]

 

---

추가:

 재귀함수 문제 풀이

 

Hooible했던 코드를 메모이제이션을 활용하면 Fair하게 만들 수 있다.