[CS Fundamental] 피보나치 수의 함수 f(n)을 작성하는 여러가지 방법에 대해서 떠오르는대로 모두 얘기해 보라.

- 피보나치 수열을 구현하는 방법에는 여러 가지가 있으며,

  각 방법은 시간 복잡도, 공간 복잡도, 직관성 등 다양한 측면에서 차이가 있습니다.

  아래에 떠오르는 다양한 방법들을 설명하겠습니다.

 

1. 재귀적 구현 (Recursive Implementation)

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

 

가장 간단하고 직관적인 방식은 재귀적으로 피보나치 수를 계산하는 것입니다.

이 방법은 수학적으로 정의된 피보나치 수의 정의와 동일하게 구현됩니다.

장점:

• 코드가 매우 간결하고 직관적임.

단점:

• 시간 복잡도는 O(2^n)으로 매우 비효율적입니다. 같은 값을 여러 번 중복 계산하는 문제가 있기 때문입니다.
• 큰 값의 n에 대해서는 성능이 매우 떨어짐.

 

2. 메모이제이션 (Memoization)

재귀적 접근의 비효율성을 해결하기 위해, 이미 계산된 값을 저장하여 재사용하는 메모이제이션을 사용할 수 있습니다.

이를 통해 중복 계산을 피할 수 있습니다.

 

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
    return memo[n]

장점:

• 시간 복잡도는 O(n)으로 개선됩니다.
• 중복 계산을 제거하여 효율적으로 처리.

단점:

• 공간 복잡도는 O(n)으로, 메모리를 더 많이 사용함.
• 재귀 구조는 여전히 남아 있으므로, 스택 오버플로우 문제가 있을 수 있음.

3. 동적 계획법 (Dynamic Programming)

재귀 구조를 없애고, 반복문을 사용하여 피보나치 수를 계산하는 방법입니다. 이전에 계산된 값을 테이블에 저장하면서 순차적으로 값을 계산합니다.

 

장점:

• 시간 복잡도는 O(n).
• 반복문을 사용하므로 재귀 구조로 인한 스택 오버플로우 문제가 없음.

단점:

• 공간 복잡도는 O(n), 하지만 배열 크기만큼의 추가 메모리를 사용함.