[Python] 다이나믹 프로그래밍(2) - 피보나치 수열(일반)

• 피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있습니다.
  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• 점화식이란 인접한 항들 사이의 관계식을 의미합니다.
• 피보나치 수열을 점화식으로 표현하면 다음과 같습니다.
  • a(n) = a(n-1) + a(n-2)
  • a(1) = 1, a(2) = 1
• 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있습니다.
  • 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현합니다.

피보나치 수열

• 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있음
  • n번째 피보나치 수를 f(n)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같음

피보나치 수열: 단순 재귀 소스코드 (Python)

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

피보나치 수열의 시간 복잡도 분석

• 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됩니다.
• 다음과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있습니다. (중복되는 부분 문제)

• 피보나치 수열의 시간 복잡도는 다음과 같습니다.
  • 세타 표기법: 𝜃(1.618⋯ᴺ)
  • 빅오 표기법: O(2ᴺ)
• 빅오 표기법을 기준으로 f(30)을 계산하기 위해 약 10억가량의 연산을 수행해야 함

피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍

• 다이나믹 프로그래밍의 사용 조건을 만족하는지 확인합니다.
  • 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있습니다.
  • 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결합니다.
• 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족합니다.