DP(다이나믹 프로그래밍, Dynamic Programming)

DP(Dynamic Programming)란?

DP는 문제를 작은 부분 문제(subproblems)로 나누어 해결하고, 그 결과를 저장하여 동일한 문제를 다시 계산하지 않도록 하는 알고리즘 설계 기법입니다. 중복되는 계산을 줄여 효율성을 극대화하는 것이 핵심입니다.

언제 DP를 사용할까?

DP는 문제를 해결하는 데 다음 두 가지 조건이 만족될 때 사용합니다:

1. Overlapping Subproblems (겹치는 부분 문제):
   • 동일한 부분 문제가 여러 번 반복해서 계산됩니다.
   • 예를 들어 피보나치 수열 계산 시, 동일한 피보나치 값이 반복적으로 계산됨.
2. Optimal Substructure (최적 부분 구조):
   • 문제의 최적 해답이 부분 문제의 최적 해답으로 구성됩니다.
   • 즉, 작은 문제들의 최적 결과를 합쳐서 전체 문제의 최적 결과를 구할 수 있습니다.

DP의 핵심 요소

1. 점화식(Recurrence Relation):
   • 큰 문제를 작은 문제로 나누는 규칙.
   • 예를 들어, 피보나치 수열의 점화식: F(n) = F(n−1) + F(n−2)
2. Memoization:
   • 재귀 호출로 문제를 해결하며, 이미 계산한 결과를 저장.
   • "탑다운(Top-Down)" 방식.
3. Tabulation:
   • 반복문으로 문제를 해결하며, 작은 문제부터 차례로 계산.
   • "바텀업(Bottom-Up)" 방식.

DP의 두 가지 구현 방식

1. 탑다운 방식 (Top-Down)

• 큰 문제를 해결하기 위해 재귀 호출로 작은 문제를 계산.
• 작은 문제의 결과를 저장(메모이제이션).
• 예제: 피보나치 수열

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

n = 10
print(fib(n, {}))  # 55

2. 바텀업 방식 (Bottom-Up)

• 작은 문제부터 차례로 계산하여 큰 문제를 해결.
• 반복문을 사용하며, 메모이제이션 테이블을 직접 채움.
• 예제: 피보나치 수열

def fib(n):
    dp = [0] * (n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

n = 10
print(fib(n))  # 55

DP 적용 단계

1. 문제를 작은 문제로 나눌 수 있는지 확인:
   • 큰 문제를 작은 문제로 나눠서 해결 가능한지 확인합니다.
2. 점화식 정의:
   • 작은 문제의 해답을 어떻게 결합해 큰 문제를 해결할지 정의합니다.
3. 메모이제이션 또는 테이블 정의:
   • 부분 문제의 결과를 저장할 자료구조(리스트, 딕셔너리 등)를 정의합니다.
4. 초기값 설정:
   • 가장 작은 문제(기저 조건)의 해답을 설정합니다.
5. 탑다운 또는 바텀업 방식으로 문제 해결.

DP 예제: 계단 오르기 문제

문제

• n개의 계단이 있고, 한 번에 1칸 또는 2칸씩만 오를 수 있다.
• 계단을 오르는 방법의 수를 구하라.

풀이

1. 문제를 작은 문제로 나눌 수 있음:
   • 계단을 오르는 방법은 마지막에 1칸을 오르거나, 2칸을 오른 경우의 합.
2. 점화식:
   • dp[n] = dp[n−1] + dp[n−2]
3. 초기값:
   • dp[1] = 1, dp[2] = 2

바텀업 구현

def climb_stairs(n):
    dp = [0] * (n+1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(climb_stairs(5))  # 8

DP의 시간 복잡도

• DP는 부분 문제의 수 × 각 부분 문제를 푸는 데 걸리는 시간으로 시간 복잡도가 결정됩니다.
• 예를 들어, 피보나치 수열:
  • 부분 문제 수: O(n)
  • 각 문제 계산 시간: O(1)
  • 총 시간 복잡도: O(n)

DP의 장점

1. 중복 계산을 제거하여 효율성을 극대화.
2. 복잡한 문제를 작은 문제로 나눠 해결 가능.
3. 최적의 해를 보장.

DP 문제를 풀 때 기억해야 할 것

1. 문제를 작은 문제로 나눌 수 있는지 확인.
2. 점화식(재귀적 관계)을 정의.
3. 작은 문제의 해답을 저장해 중복 계산 방지.
4. 탑다운 또는 바텀업 방식 중 하나 선택.