5-4. DP: 피보나치 수열

1. 피보나치 수열과 동적 프로그래밍 (DP)의 만남

피보나치 수열은 고대 수학자 피보나치가 제시한 수열로, 앞선 두 항의 합으로 다음 항이 결정되는 특징을 가집니다. 수학적 정의는 다음과 같습니다.

$$F_n = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F_{n-1} + F_{n-2}, & \text{if } n \ge 2 \end{cases}$$

이 수열은 자연 현상, 수학, 컴퓨터 과학 등 다양한 분야에서 발견됩니다. 예를 들어, 꽃잎의 수, 벌집의 구조, 주식 시장의 분석 등에서 피보나치 수열과 관련된 패턴을 찾아볼 수 있습니다.

피보나치 수열을 계산하는 가장 기본적인 방법은 재귀 호출을 사용하는 것입니다. 하지만, 이 방법은 동일한 계산을 반복 수행하는 비효율성을 가지고 있어, 입력 크기가 커질수록 성능 저하가 심각해집니다. 이러한 문제를 해결하기 위해 동적 프로그래밍 (Dynamic Programming, DP) 이라는 강력한 알고리즘 설계 기법을 활용할 수 있습니다. DP는 복잡한 문제를 작은 부분 문제로 나누어 풀고, 부분 문제의 해결 결과를 저장하여 중복 계산을 피함으로써 효율성을 향상시키는 방법입니다. 피보나치 수열은 DP를 적용하기에 매우 적합한 문제입니다.

2. 재귀적 해결 방식의 문제점

피보나치 수열을 재귀적으로 구현하면 다음과 같습니다.

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

이 코드는 단순하고 이해하기 쉽지만, 심각한 시간 복잡도 문제를 가지고 있습니다. 예를 들어, fibonacci_recursive(5)를 계산하는 과정을 살펴보면, fibonacci_recursive(3)과 fibonacci_recursive(2)가 여러 번 중복 계산되는 것을 확인할 수 있습니다.

fibonacci_recursive(5)
  fibonacci_recursive(4) + fibonacci_recursive(3)
    fibonacci_recursive(3) + fibonacci_recursive(2) + fibonacci_recursive(2) + fibonacci_recursive(1)
      fibonacci_recursive(2) + fibonacci_recursive(1) + fibonacci_recursive(2) + fibonacci_recursive(1) + fibonacci_recursive(2) + fibonacci_recursive(1) + 1
        fibonacci_recursive(1) + fibonacci_recursive(0) + 1 + fibonacci_recursive(1) + fibonacci_recursive(0) + 1 + 1 + 1 + 1
          1 + 0 + 1 + 1 + 0 + 1 + 1 + 1 + 1

이러한 중복 계산은 fibonacci_recursive(n)의 시간 복잡도를 지수적으로 증가시킵니다. 즉, O(2ⁿ)의 시간 복잡도를 가지게 되어, 큰 입력 값에 대해서는 실행 시간이 매우 길어집니다.

3. 메모이제이션 (Memoization)

메모이제이션은 DP의 한 가지 접근 방법으로, 계산된 결과를 저장하여 동일한 계산을 반복하지 않도록 하는 기법입니다. 재귀 함수를 사용하면서 계산 결과를 저장함으로써 재귀 호출의 비효율성을 개선합니다.

1) 구현 방법

메모이제이션은 일반적으로 딕셔너리 또는 배열을 사용하여 구현합니다. 각 항의 계산 결과를 저장하고, 동일한 입력에 대한 계산이 필요할 때 저장된 값을 반환합니다.

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

2) 성능 분석

메모이제이션을 적용하면 시간 복잡도를 O(n)으로 개선할 수 있습니다. 각 n에 대해 한 번만 계산을 수행하고, 결과를 저장하기 때문입니다. 공간 복잡도는 계산된 결과를 저장하기 위한 메모리 공간이 필요하므로 O(n)입니다.

메모이제이션을 그림으로 표현하면 다음과 같습니다.

4. 탭ulated 방식 (Tabulation)

탭ulated 방식은 DP의 또 다른 접근 방법으로, 가장 작은 부분 문제부터 해결하여 최종 문제의 해답까지 순차적으로 계산하는 방식입니다. 메모이제이션과 달리, 재귀 호출을 사용하지 않고 반복문을 사용하여 문제를 해결합니다.

1) 구현 방법

탭ulated 방식은 일반적으로 배열을 사용하여 구현합니다. F[0]과 F[1]을 초기값으로 설정하고, 반복문을 통해 F[2]부터 F[n]까지 값을 계산합니다.

def fibonacci_tabulation(n):
    if n <= 1:
        return n

    F = [0] * (n + 1)
    F[0] = 0
    F[1] = 1

    for i in range(2, n + 1):
        F[i] = F[i-1] + F[i-2]

    return F[n]

2) 성능 분석

탭ulated 방식 역시 시간 복잡도 O(n)을 가집니다. 0부터 n까지의 배열을 한 번씩 순회하기 때문입니다. 공간 복잡도 또한 O(n)으로, n+1 크기의 배열을 사용하기 때문입니다.

탭ulated 방식을 플로우차트로 표현하면 다음과 같습니다.

5. 메모이제이션 vs 탭ulated 방식 비교

메모이제이션과 탭ulated 방식 모두 O(n)의 시간 복잡도를 가지지만, 구현 방식과 메모리 사용량에서 차이가 있습니다.

6. 공간 최적화

피보나치 수열은 이전 두 개의 값만 알면 현재 값을 계산할 수 있다는 특징을 가지고 있습니다. 따라서, 메모이제이션과 탭ulated 방식에서 사용되는 O(n) 공간을 O(1)으로 줄일 수 있습니다.

def fibonacci_space_optimized(n):
    if n <= 1:
        return n

    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b

    return b

이 코드는 이전 두 개의 값(a, b)만을 저장하고, 반복문을 통해 값을 갱신합니다.

7. 실용적인 고려 사항

1) 문제의 특성

피보나치 수열과 같은 DP 문제는 부분 문제의 중복 여부와 최적 부분 구조를 가지고 있어야 합니다. 즉, 큰 문제를 작은 부분 문제로 나눌 수 있고, 부분 문제의 최적 해가 전체 문제의 최적 해를 구성해야 합니다.

2) 입력 크기

입력 크기에 따라 적절한 방법을 선택해야 합니다. 입력 크기가 작다면 재귀 방식도 괜찮을 수 있지만, 크기가 커질수록 메모이제이션 또는 탭ulated 방식을 사용하는 것이 좋습니다. 공간 최적화는 메모리 제약이 있는 환경에서 유용합니다.

3) 추가 팁

• DP 문제를 풀 때는, 먼저 재귀적으로 문제를 정의하고, 중복 계산을 파악하는 것이 중요합니다.
• 메모이제이션과 탭ulated 방식을 모두 이해하고, 문제의 특성에 맞는 방법을 선택합니다.
• 공간 최적화를 통해 메모리 사용량을 줄일 수 있는지도 고려합니다.

8. 결론

피보나치 수열은 DP의 기본 원리를 이해하고 적용하는 데 매우 유용한 문제입니다. 재귀 방식의 문제점을 이해하고, 메모이제이션, 탭ulated 방식, 공간 최적화를 통해 효율적인 해결 방법을 익힐 수 있습니다. DP는 다양한 알고리즘 문제 해결에 활용되는 중요한 기법이므로, 꾸준한 연습을 통해 숙달하는 것이 중요합니다.