포스트

[CS 기초 #14] 동적 계획법: 복잡한 문제를 단순하게 해결하는 마법

게시
동적 계획법 - 중복 계산을 피하는 최적화 기법
동적 계획법 - 중복 계산을 피하는 최적화 기법
By YonYonWare
33 분읽는 시간
[CS 기초 #14] 동적 계획법: 복잡한 문제를 단순하게 해결하는 마법

어려운 문제를 작은 문제로 쪼개기! DP를 마스터하면 복잡한 문제도 술술 풀립니다.

🎯 이 글을 읽고 나면

  • 동적 계획법의 핵심 개념을 이해합니다
  • 메모이제이션과 타뷸레이션의 차이를 안다
  • 피보나치, 배낭 문제 등을 DP로 풀 수 있습니다
  • DP 적용 가능 여부를 판단할 수 있습니다
  • 재귀에서 DP로 최적화하는 방법을 알게 됩니다

📚 사전 지식

  • 재귀 함수: DP의 기초
  • 시간 복잡도: 복잡도 분석 필수
  • 배열/딕셔너리: 결과 저장에 사용

💡 핵심 개념 미리보기

동적 계획법(DP)은 큰 문제를 작은 부분 문제로 나누고, 결과를 저장(메모이제이션)하여 중복 계산을 피합니다. 피보나치를 재귀로 풀면 O(2ⁿ)이지만 DP로 풀면 O(n)! 최적 부분 구조와 중복 부분 문제가 있을 때 사용하며, 배낭 문제, 최장 공통 부분수열 등에 활용됩니다!

🎯 들어가며: 왜 동적 계획법인가?

피보나치 수열의 40번째 항을 재귀로 계산하면 20억 번 이상의 함수 호출이 필요합니다. 하지만 동적 계획법을 사용하면 단 40번의 계산으로 끝납니다!

오늘은 복잡한 문제를 작은 부분 문제로 나누어 효율적으로 해결하는 동적 계획법(Dynamic Programming)을 완벽하게 마스터해보겠습니다!

📊 동적 계획법이란?

동적 계획법은 최적 부분 구조와 중복되는 부분 문제를 가진 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.

graph TB
    subgraph "동적 계획법 핵심 개념"
        OPT[최적 부분 구조<br/>Optimal Substructure]
        OVE[중복 부분 문제<br/>Overlapping Subproblems]
        MEM[메모이제이션<br/>Memoization]
        TAB[타뷸레이션<br/>Tabulation]
    end
    
    OPT --> DP[동적 계획법]
    OVE --> DP
    DP --> MEM
    DP --> TAB
    
    MEM --> TD[Top-Down<br/>하향식]
    TAB --> BU[Bottom-Up<br/>상향식]

DP의 두 가지 조건

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def dp_conditions_checker():
    """DP 적용 가능 조건 확인"""
    
    conditions = {
        "최적 부분 구조": {
            "정의": "큰 문제의 최적해가 작은 부분 문제의 최적해로 구성",
            "예시": "최단 경로: A→C = min(A→B→C)",
            "반례": "최장 단순 경로 (사이클 때문에 DP 불가)"
        },
        "중복 부분 문제": {
            "정의": "동일한 부분 문제가 여러 번 계산됨",
            "예시": "피보나치: F(5) = F(4) + F(3), F(4) = F(3) + F(2)",
            "반례": "병합 정렬 (부분 문제가 독립적)"
        }
    }
    
    print("DP 적용 가능 조건:")
    print("=" * 60)
    for condition, details in conditions.items():
        print(f"\n{condition}:")
        for key, value in details.items():
            print(f"  {key}: {value}")
    
    # DP vs 분할 정복 비교
    print("\n\nDP vs 분할 정복:")
    print("-" * 60)
    print("동적 계획법: 부분 문제가 중복 → 결과 저장하여 재사용")
    print("분할 정복: 부분 문제가 독립적 → 저장 불필요")

dp_conditions_checker()

🔄 피보나치로 이해하는 DP

1. 단순 재귀 (비효율적)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def fibonacci_recursive(n):
    """단순 재귀 - O(2^n)"""
    if n <= 1:
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

def count_fibonacci_calls(n):
    """함수 호출 횟수 계산"""
    call_count = 0
    
    def fib(n):
        nonlocal call_count
        call_count += 1
        
        if n <= 1:
            return n
        return fib(n-1) + fib(n-2)
    
    result = fib(n)
    return result, call_count

# 호출 횟수 비교
print("피보나치 재귀 호출 횟수:")
for n in [5, 10, 20, 30]:
    result, calls = count_fibonacci_calls(n)
    print(f"F({n:2}) = {result:8}, 호출 횟수: {calls:,}")

2. 메모이제이션 (Top-Down DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

def fibonacci_memoization(n, memo=None):
    """메모이제이션 - O(n)"""
    if memo is None:
        memo = {}
    
    # 이미 계산한 값이면 반환
    if n in memo:
        return memo[n]
    
    # 기저 사례
    if n <= 1:
        return n
    
    # 계산하고 저장
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    return memo[n]

# 데코레이터를 사용한 메모이제이션
def memoize(func):
    """메모이제이션 데코레이터"""
    cache = {}
    
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    
    wrapper.cache = cache  # 캐시 접근 가능
    return wrapper

@memoize
def fibonacci_decorated(n):
    """데코레이터 메모이제이션"""
    if n <= 1:
        return n
    return fibonacci_decorated(n-1) + fibonacci_decorated(n-2)

# 성능 비교
import time

def compare_fibonacci_methods(n):
    """피보나치 구현 방법 비교"""
    
    # 단순 재귀 (n이 크면 너무 오래 걸림)
    if n <= 35:
        start = time.perf_counter()
        result1 = fibonacci_recursive(n)
        time1 = time.perf_counter() - start
    else:
        result1 = "너무 오래 걸림"
        time1 = float('inf')
    
    # 메모이제이션
    start = time.perf_counter()
    result2 = fibonacci_memoization(n)
    time2 = time.perf_counter() - start
    
    print(f"F({n}) 계산 시간:")
    print(f"  단순 재귀: {time1:.6f}초 - {result1}")
    print(f"  메모이제이션: {time2:.6f}초 - {result2}")
    if time1 != float('inf'):
        print(f"  속도 향상: {time1/time2:.0f}배")

compare_fibonacci_methods(35)

3. 타뷸레이션 (Bottom-Up DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

def fibonacci_tabulation(n):
    """타뷸레이션 - O(n) 시간, O(n) 공간"""
    if n <= 1:
        return n
    
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    # 상향식으로 계산
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

def fibonacci_space_optimized(n):
    """공간 최적화 - O(n) 시간, O(1) 공간"""
    if n <= 1:
        return n
    
    prev2 = 0
    prev1 = 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    
    return prev1

def visualize_fibonacci_dp():
    """피보나치 DP 시각화"""
    n = 10
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    print(f"피보나치 수열 계산 (n={n}):")
    print("-" * 50)
    print(f"dp[0] = {dp[0]}")
    print(f"dp[1] = {dp[1]}")
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        print(f"dp[{i}] = dp[{i-1}] + dp[{i-2}] = {dp[i-1]} + {dp[i-2]} = {dp[i]}")
    
    print(f"\n최종 결과: F({n}) = {dp[n]}")

visualize_fibonacci_dp()

💰 0/1 배낭 문제 (Knapsack Problem)

기본 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

def knapsack_recursive(weights, values, capacity, n):
    """재귀적 해법 - O(2^n)"""
    # 기저 사례
    if n == 0 or capacity == 0:
        return 0
    
    # 현재 물건이 용량을 초과하면 포함 불가
    if weights[n-1] > capacity:
        return knapsack_recursive(weights, values, capacity, n-1)
    
    # 포함하는 경우와 포함하지 않는 경우 중 최댓값
    include = values[n-1] + knapsack_recursive(
        weights, values, capacity - weights[n-1], n-1
    )
    exclude = knapsack_recursive(weights, values, capacity, n-1)
    
    return max(include, exclude)

def knapsack_memoization(weights, values, capacity):
    """메모이제이션 - O(n*capacity)"""
    n = len(weights)
    memo = {}
    
    def dp(i, w):
        # 메모이제이션 체크
        if (i, w) in memo:
            return memo[(i, w)]
        
        # 기저 사례
        if i == 0 or w == 0:
            return 0
        
        # 현재 물건이 용량 초과
        if weights[i-1] > w:
            result = dp(i-1, w)
        else:
            include = values[i-1] + dp(i-1, w - weights[i-1])
            exclude = dp(i-1, w)
            result = max(include, exclude)
        
        memo[(i, w)] = result
        return result
    
    return dp(n, capacity)

def knapsack_tabulation(weights, values, capacity):
    """타뷸레이션 - O(n*capacity)"""
    n = len(weights)
    
    # DP 테이블 초기화
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # 상향식으로 계산
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            # 현재 물건을 넣을 수 없는 경우
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                # 포함하는 경우와 안 하는 경우 중 최댓값
                include = values[i-1] + dp[i-1][w - weights[i-1]]
                exclude = dp[i-1][w]
                dp[i][w] = max(include, exclude)
    
    return dp[n][capacity]

def knapsack_with_items(weights, values, capacity):
    """선택된 물건도 반환"""
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # DP 테이블 채우기
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                include = values[i-1] + dp[i-1][w - weights[i-1]]
                exclude = dp[i-1][w]
                dp[i][w] = max(include, exclude)
    
    # 선택된 물건 역추적
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)
            w -= weights[i-1]
    
    return dp[n][capacity], selected[::-1]

# 배낭 문제 테스트
def test_knapsack():
    """배낭 문제 예시"""
    items = [
        {"name": "노트북", "weight": 3, "value": 1500},
        {"name": "카메라", "weight": 2, "value": 1000},
        {"name": "책", "weight": 1, "value": 300},
        {"name": "옷", "weight": 2, "value": 400},
        {"name": "신발", "weight": 1, "value": 500}
    ]
    
    weights = [item["weight"] for item in items]
    values = [item["value"] for item in items]
    capacity = 5
    
    max_value, selected = knapsack_with_items(weights, values, capacity)
    
    print(f"배낭 용량: {capacity}kg")
    print("\n물건 목록:")
    for i, item in enumerate(items):
        print(f"  {i+1}. {item['name']}: {item['weight']}kg, ${item['value']}")
    
    print(f"\n최대 가치: ${max_value}")
    print("선택된 물건:")
    total_weight = 0
    for idx in selected:
        item = items[idx]
        print(f"  - {item['name']}: {item['weight']}kg, ${item['value']}")
        total_weight += item['weight']
    print(f"총 무게: {total_weight}kg")

test_knapsack()

공간 최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def knapsack_space_optimized(weights, values, capacity):
    """공간 최적화 - O(capacity) 공간"""
    n = len(weights)
    
    # 1차원 배열만 사용
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 역순으로 순회 (중복 사용 방지)
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

def unbounded_knapsack(weights, values, capacity):
    """무한 배낭 문제 - 물건을 여러 개 사용 가능"""
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

📝 최장 공통 부분 수열 (LCS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

def lcs_recursive(X, Y, m, n):
    """재귀적 LCS - O(2^(m+n))"""
    if m == 0 or n == 0:
        return 0
    
    if X[m-1] == Y[n-1]:
        return 1 + lcs_recursive(X, Y, m-1, n-1)
    
    return max(lcs_recursive(X, Y, m, n-1), 
               lcs_recursive(X, Y, m-1, n))

def lcs_tabulation(X, Y):
    """타뷸레이션 LCS - O(mn)"""
    m, n = len(X), len(Y)
    
    # DP 테이블 초기화
    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]

def lcs_with_sequence(X, Y):
    """LCS 길이와 실제 수열 반환"""
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # DP 테이블 채우기
    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])
    
    # LCS 역추적
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return dp[m][n], ''.join(reversed(lcs))

def lcs_visualization(X, Y):
    """LCS DP 테이블 시각화"""
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    print(f"X = '{X}', Y = '{Y}'")
    print("\nDP 테이블:")
    
    # 헤더 출력
    print("    ", end="")
    for j in range(n + 1):
        if j == 0:
            print("  ∅", end="")
        else:
            print(f"  {Y[j-1]}", end="")
    print()
    
    # DP 테이블 계산 및 출력
    for i in range(m + 1):
        if i == 0:
            print("  ∅", end="")
        else:
            print(f"  {X[i-1]}", end="")
        
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif 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])
            
            print(f"  {dp[i][j]}", end="")
        print()
    
    length, sequence = lcs_with_sequence(X, Y)
    print(f"\nLCS 길이: {length}")
    print(f"LCS: '{sequence}'")

# LCS 테스트
lcs_visualization("ABCDGH", "AEDFHR")

🪙 동전 교환 문제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

def coin_change_min_coins(coins, amount):
    """최소 동전 개수 - O(amount * len(coins))"""
    # DP 테이블 초기화
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    # 각 금액에 대해
    for i in range(1, amount + 1):
        # 각 동전으로
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

def coin_change_with_coins(coins, amount):
    """사용한 동전도 반환"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin
    
    if dp[amount] == float('inf'):
        return -1, []
    
    # 사용한 동전 역추적
    used_coins = []
    current = amount
    while current > 0:
        coin = parent[current]
        used_coins.append(coin)
        current -= coin
    
    return dp[amount], used_coins

def coin_change_ways(coins, amount):
    """동전 교환 방법의 수 - O(amount * len(coins))"""
    dp = [0] * (amount + 1)
    dp[0] = 1  # 0원을 만드는 방법은 1가지 (아무것도 선택 안함)
    
    # 각 동전에 대해
    for coin in coins:
        # 해당 동전을 사용할 수 있는 모든 금액에 대해
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    
    return dp[amount]

def coin_change_visualization(coins, amount):
    """동전 교환 DP 시각화"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    print(f"동전: {coins}")
    print(f"목표 금액: {amount}")
    print("\nDP 테이블 계산:")
    print("-" * 50)
    
    for i in range(1, amount + 1):
        print(f"금액 {i}: ", end="")
        options = []
        
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                option = dp[i - coin] + 1
                options.append(f"{coin}원 사용 → {option}개")
                dp[i] = min(dp[i], option)
        
        if options:
            print(f"{', '.join(options)} → 최소: {dp[i]}개")
        else:
            print("불가능")
    
    print(f"\n최종 결과: {dp[amount]}개의 동전 필요")
    
    # 사용한 동전 출력
    _, used = coin_change_with_coins(coins, amount)
    if used:
        print(f"사용한 동전: {used}")

# 동전 교환 테스트
coin_change_visualization([1, 5, 10, 25], 41)

🎯 편집 거리 (Edit Distance)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

def edit_distance(str1, str2):
    """편집 거리 (Levenshtein Distance) - O(mn)"""
    m, n = len(str1), len(str2)
    
    # DP 테이블 초기화
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 기저 사례
    for i in range(m + 1):
        dp[i][0] = i  # 삭제
    for j in range(n + 1):
        dp[0][j] = j  # 삽입
    
    # DP 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 변경 불필요
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # 삭제
                    dp[i][j-1],    # 삽입
                    dp[i-1][j-1]   # 교체
                )
    
    return dp[m][n]

def edit_distance_with_operations(str1, str2):
    """편집 거리와 연산 순서"""
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 초기화
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # DP 계산
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    
    # 연산 역추적
    operations = []
    i, j = m, n
    
    while i > 0 or j > 0:
        if i == 0:
            operations.append(f"삽입 '{str2[j-1]}' at position {i}")
            j -= 1
        elif j == 0:
            operations.append(f"삭제 '{str1[i-1]}' at position {i-1}")
            i -= 1
        elif str1[i-1] == str2[j-1]:
            i -= 1
            j -= 1
        else:
            if dp[i][j] == dp[i-1][j-1] + 1:
                operations.append(f"교체 '{str1[i-1]}' → '{str2[j-1]}' at position {i-1}")
                i -= 1
                j -= 1
            elif dp[i][j] == dp[i-1][j] + 1:
                operations.append(f"삭제 '{str1[i-1]}' at position {i-1}")
                i -= 1
            else:
                operations.append(f"삽입 '{str2[j-1]}' at position {i}")
                j -= 1
    
    return dp[m][n], operations[::-1]

# 편집 거리 테스트
str1, str2 = "SATURDAY", "SUNDAY"
distance, ops = edit_distance_with_operations(str1, str2)
print(f"'{str1}' → '{str2}'")
print(f"편집 거리: {distance}")
print("연산 순서:")
for op in ops:
    print(f"  - {op}")

📈 최대 부분 배열 합

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

def max_subarray_sum_dp(arr):
    """카데인 알고리즘 - O(n)"""
    n = len(arr)
    if n == 0:
        return 0
    
    # dp[i] = i번째 원소를 끝으로 하는 최대 부분 배열 합
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = arr[0]
    
    for i in range(1, n):
        dp[i] = max(arr[i], dp[i-1] + arr[i])
        max_sum = max(max_sum, dp[i])
    
    return max_sum

def max_subarray_with_indices(arr):
    """최대 부분 배열과 인덱스"""
    n = len(arr)
    if n == 0:
        return 0, 0, -1
    
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = arr[0]
    max_end = 0
    
    # 시작 인덱스 추적
    start = [0] * n
    
    for i in range(1, n):
        if arr[i] > dp[i-1] + arr[i]:
            dp[i] = arr[i]
            start[i] = i
        else:
            dp[i] = dp[i-1] + arr[i]
            start[i] = start[i-1]
        
        if dp[i] > max_sum:
            max_sum = dp[i]
            max_end = i
    
    return max_sum, start[max_end], max_end

def max_subarray_2d(matrix):
    """2D 최대 부분 배열 합"""
    if not matrix:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    max_sum = float('-inf')
    
    # 모든 행 조합에 대해
    for top in range(rows):
        temp = [0] * cols
        
        for bottom in range(top, rows):
            # 현재 행 범위의 합을 temp에 누적
            for col in range(cols):
                temp[col] += matrix[bottom][col]
            
            # 1D 카데인 알고리즘 적용
            current_sum = max_subarray_sum_dp(temp)
            max_sum = max(max_sum, current_sum)
    
    return max_sum

# 테스트
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum, start, end = max_subarray_with_indices(arr)
print(f"배열: {arr}")
print(f"최대 부분 배열 합: {max_sum}")
print(f"부분 배열: {arr[start:end+1]}")

🏠 최장 증가 부분 수열 (LIS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

def lis_dp(arr):
    """LIS with DP - O(n^2)"""
    n = len(arr)
    if n == 0:
        return 0
    
    # dp[i] = i번째 원소를 마지막으로 하는 LIS 길이
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

def lis_with_sequence(arr):
    """LIS 길이와 실제 수열"""
    n = len(arr)
    if n == 0:
        return 0, []
    
    dp = [1] * n
    parent = [-1] * n
    
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j
    
    # 최대 길이와 끝 인덱스 찾기
    max_length = max(dp)
    max_idx = dp.index(max_length)
    
    # LIS 역추적
    lis = []
    idx = max_idx
    while idx != -1:
        lis.append(arr[idx])
        idx = parent[idx]
    
    return max_length, lis[::-1]

def lis_binary_search(arr):
    """이진 탐색을 이용한 LIS - O(n log n)"""
    from bisect import bisect_left
    
    if not arr:
        return 0
    
    # tails[i] = 길이가 i+1인 증가 부분 수열의 최소 마지막 값
    tails = []
    
    for num in arr:
        pos = bisect_left(tails, num)
        
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

def lis_visualization(arr):
    """LIS DP 시각화"""
    n = len(arr)
    dp = [1] * n
    parent = [-1] * n
    
    print(f"배열: {arr}")
    print("\nDP 계산 과정:")
    print("-" * 50)
    
    for i in range(1, n):
        print(f"\narr[{i}] = {arr[i]}:")
        
        for j in range(i):
            if arr[j] < arr[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
                    print(f"  arr[{j}]={arr[j]} < arr[{i}]={arr[i]} → dp[{i}] = {dp[i]}")
        
        print(f"  최종 dp[{i}] = {dp[i]}")
    
    print(f"\nDP 배열: {dp}")
    print(f"LIS 길이: {max(dp)}")
    
    _, lis = lis_with_sequence(arr)
    print(f"LIS: {lis}")

# LIS 테스트
lis_visualization([10, 9, 2, 5, 3, 7, 101, 18])

🎮 행렬 곱셈 최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def matrix_chain_multiplication(dimensions):
    """행렬 곱셈 최적화 - O(n^3)"""
    n = len(dimensions) - 1  # 행렬 개수
    
    # dp[i][j] = i번째부터 j번째 행렬까지 곱하는 최소 연산 횟수
    dp = [[0] * n for _ in range(n)]
    
    # 체인 길이별로 계산
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # 분할 지점 k
            for k in range(i, j):
                cost = (dp[i][k] + dp[k+1][j] + 
                       dimensions[i] * dimensions[k+1] * dimensions[j+1])
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

def matrix_chain_with_parenthesis(dimensions):
    """최적 괄호 위치도 반환"""
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    bracket = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            for k in range(i, j):
                cost = (dp[i][k] + dp[k+1][j] + 
                       dimensions[i] * dimensions[k+1] * dimensions[j+1])
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    bracket[i][j] = k
    
    def print_parenthesis(i, j, bracket):
        if i == j:
            return f"M{i+1}"
        
        k = bracket[i][j]
        left = print_parenthesis(i, k, bracket)
        right = print_parenthesis(k+1, j, bracket)
        return f"({left} × {right})"
    
    parenthesis = print_parenthesis(0, n-1, bracket)
    return dp[0][n-1], parenthesis

# 행렬 곱셈 테스트
dimensions = [10, 20, 30, 40, 30]  # M1: 10×20, M2: 20×30, M3: 30×40, M4: 40×30
cost, parenthesis = matrix_chain_with_parenthesis(dimensions)
print(f"행렬 차원: {dimensions}")
print(f"최소 연산 횟수: {cost}")
print(f"최적 괄호: {parenthesis}")

💡 DP 최적화 기법

상태 압축 DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def traveling_salesman_dp(dist):
    """외판원 문제 - 비트마스크 DP - O(n^2 * 2^n)"""
    n = len(dist)
    all_visited = (1 << n) - 1
    
    # dp[mask][i] = mask 상태에서 i번 도시에 있을 때 최소 비용
    dp = {}
    
    def tsp(mask, pos):
        if mask == all_visited:
            return dist[pos][0]  # 시작점으로 돌아가기
        
        if (mask, pos) in dp:
            return dp[(mask, pos)]
        
        result = float('inf')
        
        for city in range(n):
            if mask & (1 << city) == 0:  # 방문하지 않은 도시
                new_mask = mask | (1 << city)
                distance = dist[pos][city] + tsp(new_mask, city)
                result = min(result, distance)
        
        dp[(mask, pos)] = result
        return result
    
    return tsp(1, 0)  # 0번 도시에서 시작

# TSP 테스트
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(f"최소 경로 비용: {traveling_salesman_dp(dist)}")

분할 정복 최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def optimal_binary_search_tree(keys, freq):
    """최적 이진 탐색 트리 - O(n^3)"""
    n = len(keys)
    
    # 누적 빈도
    cum_freq = [0] * (n + 1)
    for i in range(n):
        cum_freq[i + 1] = cum_freq[i] + freq[i]
    
    # dp[i][j] = keys[i..j]로 만든 최적 BST 비용
    dp = [[0] * n for _ in range(n)]
    
    # 길이 1인 경우
    for i in range(n):
        dp[i][i] = freq[i]
    
    # 길이별로 계산
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            
            # 루트 선택
            for r in range(i, j + 1):
                left = dp[i][r-1] if r > i else 0
                right = dp[r+1][j] if r < j else 0
                cost = left + right + cum_freq[j+1] - cum_freq[i]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

🎯 핵심 정리

꼭 기억해야 할 5가지

  1. 최적 부분 구조와 중복 부분 문제가 DP의 핵심
  2. 메모이제이션: Top-Down, 재귀 + 캐시
  3. 타뷸레이션: Bottom-Up, 반복문 사용
  4. 상태 정의가 가장 중요 (무엇을 저장할지)
  5. 공간 최적화: 필요한 이전 상태만 저장

DP 문제 접근법

  1. 재귀 관계식 찾기
  2. 기저 사례 정의
  3. 메모이제이션으로 시작
  4. 타뷸레이션으로 변환
  5. 공간 최적화 고려

📚 추가 학습 자료

추천 문제

  • LeetCode: Climbing Stairs, House Robber, Longest Palindromic Substring
  • 프로그래머스: N으로 표현, 정수 삼각형, 등굣길
  • 백준: 1463(1로 만들기), 11726(2×n 타일링), 9251(LCS)

🚀 다음 시간 예고

다음 포스트에서는 그리디 알고리즘과 분할 정복을 다룹니다. 최적해를 보장하는 그리디 선택과 효율적인 분할 정복 기법을 알아보겠습니다!

📌 시리즈 네비게이션

순서 제목 링크
13 탐색 알고리즘: 선형 탐색부터 이진 탐색까지 ← 이전 글
14 동적 계획법: 복잡한 문제를 단순하게 ✅ 현재 글
15 그리디와 분할정복: 효율적인 문제 해결 다음 글 →
📋 전체 시리즈 목차 보기

기초 이론편

  1. CS 입문 ✅
  2. 컴퓨터 구조 ✅
  3. 이진수와 논리 게이트 ✅
  4. 운영체제 기초 ✅
  5. 네트워크 기초 ✅

자료구조편

  1. 배열과 연결 리스트 ✅
  2. 스택과 큐 ✅
  3. 트리 구조 ✅
  4. 그래프 ✅
  5. 해시 테이블 ✅

알고리즘편

  1. 복잡도 분석 ✅
  2. 정렬 알고리즘 ✅
  3. 탐색 알고리즘 ✅
  4. 동적 계획법 ✅
  5. 그리디와 분할정복

실무 응용편

  1. 데이터베이스 이론
  2. 소프트웨어 공학
  3. 보안 기초
  4. 분산 시스템
  5. CS 종합과 면접 준비
Computer Science, Algorithms
cs algorithm dynamic-programming dp memoization tabulation optimization fibonacci knapsack lcs
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.