[DP] 동적 프로그래밍 또는 동적 계획법(Dynamic Programming)

동적 프로그래밍 (Dynamic Programming, DP)

동적 프로그래밍은 복잡한 문제를 작은 하위 문제로 나누고, 각 하위 문제를 한 번만 풀어 그 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 알고리즘 기법입니다. 이는 재귀적 접근법(분할정복)과 메모이제이션(결과 저장)을 결합한 방식으로, 중복 계산을 줄이는 것이 핵심입니다.

동적 프로그래밍의 특징

1. 최적 부분 구조 (Optimal Substructure): 문제를 더 작은 하위 문제로 나눌 수 있으며, 이 하위 문제들의 해결 방법을 조합해 전체 문제를 해결할 수 있어야 합니다.
2. 중복되는 하위 문제 (Overlapping Subproblems): 동일한 하위 문제가 여러 번 반복되어 계산될 경우, 이전 계산 결과를 저장해 재사용할 수 있습니다.

---

동적 프로그래밍의 구현 방식

1. 메모이제이션 (Memoization): 재귀 방식으로 구현되며, 계산된 결과를 테이블(배열, 맵 등)에 저장해 중복 계산을 방지합니다.
2. 탑다운 (Top-Down): 큰 문제에서 시작해 작은 문제를 해결하는 방식 (재귀적).
3. 보텀업 (Bottom-Up): 작은 문제부터 차례로 해결해 큰 문제로 확장하는 방식 (반복적).

---

DP과 재귀적 호출의 차이점?

 

하향식(Top-down) vs 상향식(Bottom-up) 접근

재귀적 호출은 주로 하향식(top-down) 접근 방식을 사용합니다. 즉, 큰 문제를 작은 하위 문제로 나누어 해결하는 방식입니다. 반면에 동적 계획법은 주로 상향식(bottom-up) 접근 방식을 사용합니다. 작은 하위 문제들부터 시작하여 그 결과를 저장하고, 이를 이용하여 점진적으로 큰 문제의 해를 구해나갑니다.

 

메모이제이션(Memoization)

동적 계획법은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용합니다. 이를 통해 이전에 계산한 값을 캐시하고, 다시 필요할 때 해당 값을 가져와 재사용합니다. 이는 재귀적 호출에서의 중복 계산을 방지하고 계산 속도를 향상시킵니다.

 

---

간단한 예시: 피보나치 수열

피보나치 수열은 아래와 같이 정의됩니다:

피보나치

​

 

1. 재귀적 접근 (비효율적):

def fib_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib_recursive(n-1) + fib_recursive(n-2)

print(fib_recursive(10))  # 55

• 문제점: 동일한 값을 여러 번 계산하여 시간 복잡도가 O(2^n)에 가까움.

 

2. 동적 프로그래밍 (메모이제이션):

def fib_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        return 0
    elif n == 1:
        return 1
    memo[n] = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)
    return memo[n]

print(fib_memoization(10))  # 55

• 장점: 중복 계산을 방지하여 시간 복잡도가 O(n) 으로 줄어듦.

3. 동적 프로그래밍 (보텀업):

def fib_bottom_up(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    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(fib_bottom_up(10))  # 55

• 장점: 반복문을 사용해 추가적인 재귀 호출을 피하며 O(n) 시간 복잡도를 가짐.

---

응용 분야

1. 최적 경로 탐색: 예) 다익스트라 알고리즘, 벨만-포드 알고리즘.
2. 배낭 문제 (Knapsack Problem): 한정된 용량의 배낭에 최대 가치를 담는 문제.
3. 문자열 문제: 예) 문자열 정렬, 편집 거리(Edit Distance).
4. 게임 이론 및 확률 문제: 예) 님 게임(Nim Game), 확률 계산.