[Algorithm] Dynamic Programming (동적 계획법)

Dynamic Programming (동적 계획법)

Dynamic Programming(DP, 동적 계획법)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 후, 결과를 저장하여 중복 계산을 피하는 최적화 기법
→   한 번 계산한 값을 저장해두고, 필요할 때 다시 사용함으로써 연산량을 줄이는 기법

 

 

---

조건

DP를 사용하기 위한 조건

 

1. 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나누었을 때, 작은 문제의 최적해를 이용해 큰 문제의 최적해를 구할 수 있어야 한다.

 

• 예시)
  • 피보나치 수열
    • f(N) = f(N−1) + f(N−2)    →    f(N-1)과 f(N-2)을 구하면 f(N)도 구할 수 있다.

2. 중복되는 부분 문제 (Overlapping Subproblems)

• 동일한 작은 문제가 여러 번 반복해서 계산되는 경우, 이를 저장하여 중복 계산을 피한다.

 

• 예시)
  • 피보나치 수열에서 fibo(3)을 실행하는 경우 다음과 같이 중복 호출이 발생한다.

fibo(3)
├── fibo(2)
│   ├── fibo(1) → 1
│   ├── fibo(0) → 0
│
└── fibo(1) → 1

 

• fibo(3)  →  fibo(2), fibo(1)을 호출
• fibo(2)  →  fibo(1), fibo(0)을 호출
• fibo(1)이 두 번 호출

 

 

 

---

DP 구현 방식

 

1. Top-Down (메모이제이션, Memoization)

• 재귀 + 메모이제이션 활용
• 큰 문제를 작은 문제로 나누고, 이미 계산한 값은 배열에 저장하여 중복 계산을 방지

 

예제: 피보나치 수열 (Top-Down)

# 메모이제이션을 위한 DP 테이블 초기화
dp = [-1] * 100

def fibo(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if dp[n] != -1:  # 이미 계산한 값이면 반환
        return dp[n]
    
    dp[n] = fibo(n-1) + fibo(n-2)  # 계산 후 저장
    return dp[n]

print(fibo(10))  # 55

• 재귀를 사용하지만 한 번 계산한 값은 저장하여 중복 호출을 피함
• 시간 복잡도  :  O(N)
• But, 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있음

 

 

---

2. Bottom-Up (Tabulation)

• 작은 문제부터 차례대로 해결하면서 배열에 저장하고, 이를 이용해 점진적으로 큰 문제를 해결하는 방식
• 반복문을 사용하고, 재귀를 사용하지 않기 때문에 스택 오버플로우 문제가 발생하지 않음

 

예제: 피보나치 수열 (Bottom-Up)

def fibo(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(fibo(10))  # 55

• 재귀 없이 반복문으로 해결하여 스택 오버플로우 걱정 없음
• 시간 복잡도  :  O(N)
• But, 메모이제이션보다 코드가 길어질 수 있음

 

 

---

DP 적용 방법

DP를 적용할 수 있는지 판단은?

1. "작은 문제의 결과를 이용해 큰 문제를 풀 수 있는가?" → 최적 부분 구조 확인
2. "동일한 작은 문제가 반복해서 계산되는가?" → 중복되는 부분 문제 확인
3. 위 두 가지가 만족되면 DP를 적용

 

 

---

DP 활용 예시

 

1. 피보나치 수열

점화식  :  F(N) = F(N-1) + F(N-2)
→   Top-Down & Bottom-Up 방법 적용 가능

 

2. 동전 거스름돈 문제

문제  :  최소한의 동전 개수로 거스름돈을 줄 때, 필요한 동전 개수를 구하는 문제

점화식  :  dp[i] = min(dp[i - coin] + 1 for coin in coins if i >= coin)
→   Bottom-Up 방식이 일반적

 

3. 최장 공통 부분 수열 (LCS, Longest Common Subsequence)

문제  :  두 문자열에서 가장 긴 공통 부분 수열의 길이를 구하는 문제

점화식  :

• dp[i][j] = dp[i-1][j-1] + 1 (두 문자가 같으면)
• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (다르면)
  → 2차원 DP 배열 사용