동적 프로그래밍(Dynamic Programming)의 개념과 예제

동적 프로그래밍(Dynamic Programming)의 개념과 예제

1. 동적 프로그래밍(Dynamic Programming)이란?

 동적 프로그래밍(DP, Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 결과를 저장하여 동일한 계산을 반복하지 않도록 최적화하는 알고리즘 기법이다. 특히, 부분 문제의 결과를 재사용할 수 있는 경우(Overlapping Subproblems)와 최적 부분 구조(Optimal Substructure)를 만족하는 경우에 효과적이다.

 

📌 핵심 개념:

• 동일한 연산을 반복하지 않도록 결과를 저장(Memoization)
• 작은 문제를 해결한 후 이를 조합하여 큰 문제를 해결하는 방식
• 재귀(Top-Down) 방식과 반복(Bottom-Up) 방식이 존재

---

2. 동적 프로그래밍이 필요한 이유

 일반적인 완전 탐색(Brute Force) 방법으로 문제를 해결하면 시간 복잡도가 급격히 증가할 수 있다. 하지만 동적 프로그래밍을 활용하면 불필요한 계산을 줄여 알고리즘을 효율적으로 최적화할 수 있다.

 

📌 예제 비교: 피보나치 수열 계산

• 재귀 방식 (일반적인 방식, O(2ⁿ))

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

 

 

→ 중복 계산이 많아 시간 복잡도 O(2ⁿ) 로 비효율적이다.

 

• 동적 프로그래밍 방식 (O(n))

def fibonacci_dp(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]

 

→ 이전 결과를 저장하여 불필요한 계산을 줄이고 시간 복잡도를 O(n)으로 최적화할 수 있다.

---

3. 동적 프로그래밍의 핵심 개념

1. 중복되는 부분 문제(Overlapping Subproblems)
   • 문제를 작은 부분 문제로 나누었을 때, 동일한 문제가 반복적으로 발생하는 경우
   • 예: 피보나치 수열, 최단 경로 문제, 배낭 문제 등
2. 최적 부분 구조(Optimal Substructure)
   • 문제의 최적 해법이 하위 문제의 최적 해법을 조합하여 구성될 수 있는 경우
   • 예: 최단 경로 문제, LCS(최장 공통 부분 수열), 배낭 문제 등

📌 즉, 동일한 연산을 반복하지 않고 이전 계산 값을 저장하면 불필요한 연산을 줄일 수 있다! 

---

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

 동적 프로그래밍을 구현하는 방식은 2가지가 있다.

4-1. 메모이제이션(Memoization) – Top-Down 방식 (재귀)

• 문제를 해결하면서 결과를 저장하고 재사용하는 방식
• 일반적으로 재귀(Recursion) + 해시 테이블(Dictionary) 또는 리스트(List)를 활용하여 구현
• 필요한 계산만 수행하므로 효율적이지만, 재귀 호출이 많으면 스택 오버플로우 위험이 있음

📌 예제: 피보나치 수열 (재귀 + 메모이제이션)

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

 

✔ 장점: 필요할 때만 계산 → 불필요한 중복 연산을 최소화
✔ 단점: 재귀 호출이 많으면 스택 오버플로우(Stack Overflow) 발생 가능

---

4-2. 반복문(Bottom-Up) – Tabulation 방식

• 작은 문제부터 차근차근 해결하여 결과를 테이블(배열)에 저장하는 방식
• 반복문을 사용하므로 스택 오버플로우 문제가 없음
• 미리 모든 값을 계산하므로 필요 없는 연산도 포함될 수 있음

📌 예제: 피보나치 수열 (반복문 + DP 테이블)

def fibonacci_tabulation(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_tabulation(10))  # 결과: 55

 

✔ 장점: 재귀 호출이 없어 스택 오버플로우 문제 없음
✔ 단점: 모든 값을 미리 계산 → 필요 없는 연산이 포함될 가능성 있음

---

5. 동적 프로그래밍 활용 사례

 동적 프로그래밍(Dynamic Programming)은 다양한 문제에서 최적의 해결 방법을 찾기 위한 핵심적인 기법이다. 특히, 부분 문제의 결과를 저장하여 불필요한 연산을 줄이는 방식이므로, **최적화 문제(Optimization Problem)**에 자주 활용된다.

 

📌 대표적인 DP 문제 유형

1. 피보나치 수열(Fibonacci Sequence)
   • 기본적인 DP 개념을 학습하기 좋은 예제
   • 재귀로 구현하면 O(2ⁿ) 의 시간이 걸리지만, DP를 활용하면 O(n) 으로 최적화 가능
   • 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식 모두 적용 가능
2. 최장 공통 부분 수열(LCS, Longest Common Subsequence)
   • 두 개의 문자열에서 공통된 부분 문자열 중 가장 긴 부분을 찾는 문제
   • 동적 프로그래밍을 활용하면 O(n × m) 의 시간 복잡도로 최적화 가능
   • LCS는 문서 비교, DNA 서열 분석, 버전 관리 시스템(Git Diff) 등에서 활용됨
   • 예제: "ABCDEF"와 "ACDF"에서 최장 공통 부분 수열은 "ACDF"
3. 배낭 문제(Knapsack Problem)
   • 여러 개의 아이템이 있을 때, 배낭이 담을 수 있는 최대 무게를 초과하지 않으면서 가장 높은 가치를 얻는 조합을 찾는 문제
   • 탐욕 알고리즘으로 풀면 항상 최적해를 보장할 수 없지만, DP를 사용하면 최적해를 찾을 수 있음
   • 0/1 배낭 문제, 분할 가능 배낭 문제(Fractional Knapsack), 다차원 배낭 문제 등 다양한 변형이 존재
4. 최단 경로 문제 (Floyd-Warshall 알고리즘)
   • 그래프에서 모든 노드 간의 최단 경로를 구하는 알고리즘
   • 동적 프로그래밍을 활용하여 O(n³)의 시간 복잡도로 해결 가능
   • 다익스트라 알고리즘이 한 노드에서 모든 노드로 가는 최단 경로를 찾는 것과 달리,
     Floyd-Warshall 알고리즘은 모든 노드 간의 최단 경로를 찾는 문제에 적합
5. 동전 거스름돈 문제 (Coin Change Problem)
   • 주어진 동전으로 특정 금액을 만들 때, 필요한 최소 동전 개수를 찾는 문제
   • 그리디 알고리즘(탐욕법)으로 풀 수 없는 경우가 많으며, DP를 활용하면 O(n × m)의 시간 복잡도로 최적화 가능
   • 실제 금융 시스템, ATM 기기에서 동전을 최소한으로 사용하여 거스름돈을 제공하는 데 활용
6. 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)
   • 주어진 숫자 배열에서 증가하는 부분 수열 중 가장 긴 길이를 찾는 문제
   • O(n²) 의 시간 복잡도로 해결할 수 있으며, 이진 탐색을 적용하면 O(n log n) 으로 최적화 가능
   • 예제: [3, 10, 2, 1, 20] → 가장 긴 증가 부분 수열: [3, 10, 20]
7. 행렬 체인 곱셈(Matrix Chain Multiplication)
   • 행렬 곱셈 순서를 최적화하여 연산 횟수를 최소화하는 문제
   • 괄호를 적절히 배치하여 행렬 곱셈 연산량을 줄이는 방식
   • 시간 복잡도 O(n³), 공간 복잡도 O(n²)로 최적화 가능

---

6. 예제 문제 – 배낭 문제 (Knapsack Problem)

1) 문제

• 최대 무게가 W인 배낭이 있다.
• N개의 아이템이 있으며, 각 아이템은 **가치(value)와 무게(weight)**를 가짐.
• 배낭이 수용할 수 있는 최대 무게 W를 초과하지 않으면서 가치의 합이 최대가 되도록 선택하는 문제

2) 코드 구현 (0/1 Knapsack)

def knapsack(W, weights, values, n):
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    
    for i in range(1, n+1):
        for w in range(W+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
n = len(weights)
print(knapsack(W, weights, values, n))  # 결과: 7

 

✔ 점화식: dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
✔ 시간 복잡도: O(N * W), 공간 복잡도 O(N * W)

---

7. 동적 프로그래밍과 탐욕 알고리즘 비교

📌 탐욕 알고리즘(Greedy Algorithm) vs 동적 프로그래밍(DP)

비교 항목	탐욕 알고리즘	동적 프로그래밍
문제 해결 방식	매 단계에서 최적 선택	하위 문제를 저장 후 최적 선택
적용 조건	항상 최적 부분 구조를 가짐	중복 부분 문제와 최적 부분 구조
예제 문제	거스름돈 문제, 다익스트라 알고리즘	배낭 문제, LCS, Floyd-Warshall

🚀 핵심 포인트:
✔ 탐욕법은 매 단계에서 최적의 선택을 하지만, 항상 최적해를 보장하지 않음.
✔ DP는 이전 계산 결과를 저장하여 최적의 해를 보장함.