동적 계획법(Dynamic Programming, DP): 최적화된 문제 해결 기법
🔹 동적 계획법이란?
1. 동적 계획법(Dynamic Programming, DP)의 정의
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누고, 각 부분 문제의 해를 저장하여 반복 연산을 줄여 최적의 해결책을 구하는 기법입니다. 주로 중복 계산을 피하고 성능을 향상시키기 위해 사용됩니다.
✅ 동적 계획법의 주요 특징:
- 부분 문제(Optimal Substructure): 문제를 작은 문제로 분할하여 해결 가능
- 중복되는 부분 문제(Overlapping Subproblems): 같은 하위 문제를 여러 번 해결해야 함
- 메모이제이션(Memoization) 또는 테이블 저장 방식(Tabulation)으로 최적화 가능
- 탑다운(Top-Down)과 바텀업(Bottom-Up) 접근 방식이 있음
📌 동적 계획법은 재귀적 문제 해결을 최적화하는 강력한 기법입니다.
🔹 동적 계획법의 접근 방식
1. 메모이제이션(Memoization, Top-Down)
✅ 재귀를 이용해 하위 문제를 해결하고, 그 결과를 저장하여 중복 계산 방지
✔️ 피보나치 수열 예제 (Python, 메모이제이션):
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
print(fibonacci_memo(10)) # 출력: 55📌 이전 계산값을 저장하여 중복 계산을 줄일 수 있습니다.
2. 테이블 저장 방식(Tabulation, Bottom-Up)
✅ 작은 문제부터 차례로 해결하며 결과를 저장
✔️ 피보나치 수열 예제 (Python, 테이블 저장 방식):
def fibonacci_tab(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_tab(10)) # 출력: 55📌 바텀업 방식은 스택 오버플로우 위험이 없고, 성능이 향상됩니다.
🔹 동적 계획법이 사용되는 문제 유형
1. 0-1 배낭 문제(Knapsack Problem)
✅ 무게 제한이 있는 배낭에 최대한의 가치를 담는 문제
✔️ 0-1 배낭 문제 예제 (Python):
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity)) # 출력: 7📌 DP를 활용하면 최적의 선택을 빠르게 찾을 수 있습니다.
2. 최장 공통 부분 수열(Longest Common Subsequence, LCS)
✅ 두 문자열 간 가장 긴 공통 부분 수열 찾기
✔️ LCS 예제 (Python):
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
X = "ACDBE"
Y = "ABCDE"
print(lcs(X, Y)) # 출력: 4📌 문자열 비교 및 데이터 분석 문제에 활용됩니다.
🔹 동적 계획법 vs 분할 정복
| 비교 항목 | 동적 계획법(DP) | 분할 정복(Divide & Conquer) |
|---|---|---|
| 중복 문제 해결 | 결과 저장 후 재사용 | 매번 새로 계산 |
| 접근 방식 | 바텀업/탑다운 | 문제를 작은 부분으로 나눔 |
| 대표 알고리즘 | 피보나치, 배낭 문제, LCS | 퀵 정렬, 병합 정렬 |
📌 동적 계획법은 중복 계산을 줄이고, 분할 정복은 문제를 분할하여 해결합니다.
📌 결론
✅ 동적 계획법(Dynamic Programming)은 중복 계산을 줄이고 최적의 해결책을 제공하는 알고리즘 기법입니다.
✅ 탑다운(메모이제이션)과 바텀업(테이블 저장) 방식이 있으며, 문제 유형에 따라 적절한 방식을 선택해야 합니다.
✅ 0-1 배낭 문제, 최장 공통 부분 수열(LCS), 피보나치 수열 등 다양한 문제에서 활용됩니다.
✅ 중복 계산이 많은 문제에서 가장 강력한 최적화 방법 중 하나입니다.