동적 계획법(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), 피보나치 수열 등 다양한 문제에서 활용됩니다.
✅ 중복 계산이 많은 문제에서 가장 강력한 최적화 방법 중 하나입니다.