동적 계획법(Dynamic Programming, DP)

동적 계획법(DP)은 복잡한 문제를 해결하기 위해 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 해답을 저장하여 재사용하는 방법입니다. 이는 중복된 계산을 줄이고, 문제를 효율적으로 해결하는 방법으로 널리 사용됩니다.

동적 계획법(Dynamic Programming)

DP의 원칙

1. 최적 부분 구조(Optimal Substructure): 문제의 최적해는 그 하위 문제들의 최적해로 구성될 수 있습니다.
2. 중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 반복되어 나타나는 경우, 이를 한 번만 계산하고 저장하여 재사용합니다.

특징

• 메모이제이션(Memoization): 재귀적 접근 방식에서 계산된 하위 문제의 결과를 캐시에 저장하여 중복 계산을 방지합니다.
• 타뷸레이션(Tabulation): 반복문을 통해 하위 문제를 먼저 계산하고, 이를 이용해 상위 문제를 해결하는 방식입니다.
• 시간 복잡도 개선: 중복 계산을 줄임으로써 시간이 크게 절약됩니다. DP 알고리즘은 일반적으로 O(n^2)이나 O(n)의 복잡도를 가집니다.

python 구현 - 피보나치 수열(재귀)

# 재귀적 접근(비효율적)
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

python 구현 - 피보나치 수열(DP)

# DP접근(효율적)
def fibonacci_dp(n):
    if n <= 1:
        return n
  
    dp = [0] * (n + 1)
    dp[1] = 1
  
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
  
    return dp[n]

# 사용 예
print(fibonacci_dp(10))  # 출력: 55

시간복잡도

DP 접근법의 시간 복잡도는 문제에 따라 다르지만, 위의 피보나치 수열은 O(n)입니다.