fibonacci

🌴 문제

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

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

 

🌴 출력

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

 

---

 

🌴 문제 풀이

// 1번

function fibonacci(n) {
    // TODO: 여기에 코드를 작성합니다.
    // 0 1 1 2 3 4 5.....
    if(n<=1) return n;

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

// 2번 

function fibonacci(n) {
    // TODO: 여기에 코드를 작성합니다.
    // 0 1 1 2 3 4 5.....

    const arr = [0,1];

    function helper(h){
        if(arr[h] !== undefined) return arr[h];

        arr[h] = helper(h-2)+helper(h-1);
        return arr[h];
    }

    return helper(n);
  }

 

위 두개의 식은 모두 피보나치 수열을 구할 수 있다. 겉으로 보기에는 1번 식이 더 간단해 보여 좋아보일 수 있지만 시간복잡도를 생각한다면 2번식이 더 좋은 식이다.

 

1번 식을 다 보자. 1번 식에서는 다음 항을 알기 위해서는 앞의 두 개의 항을 알아야하기 때문에, n번째 항을 알기 위해서는 n-1, n-2번째 항을 재귀호출한다.(시간복잡도로 O(2^N)이다.)

 

만약 1번 식에서 앞서 계산한 값을 다시 계산하지 않고 계산 한 것을 한 곳에 저장한 수 다시 가져올 수 있게 한다면 어떨게 될까?

 

그렇게 작성한 식이 2번 식이다. 2번 식에서는 값을 가지고 있다면 재귀호출을 하지 않고 값만을 가져다 준다. 이렇게 작성하면 2번씩 반복되는 일이 없어지기 때문에 시간 복잡도는 O(n)이 된다.