최적 부분 구조(Optimal Substructure)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def fibonacci_dp(n):
    if n <= 1:
        return n
    
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    
    # 상향식(bottom-up) 접근
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 선형 최적 부분 구조
    
    return dp[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def matrix_chain_multiplication(dimensions):
    n = len(dimensions) - 1  # 행렬 개수
    
    # m[i][j] = i부터 j까지의 행렬을 곱하는 최소 연산 횟수
    m = [[0 for _ in range(n)] for _ in range(n)]
    
    # 연쇄 길이 l을 2부터 n까지 증가시키며 계산
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            m[i][j] = float('inf')
            
            # 최적의 분할 지점 k 찾기 (분기 최적 부분 구조)
            for k in range(i, j):
                cost = m[i][k] + m[k+1][j] + dimensions[i] * dimensions[k+1] * dimensions[j+1]
                if cost < m[i][j]:
                    m[i][j] = cost
    
    return m[0][n-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # dp[i][j] = text1[:i]와 text2[:j]의 LCS 길이
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                # 문자가 같으면 대각선 값에 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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def floyd_warshall(graph):
    n = len(graph)
    dist = [row[:] for row in graph]  # 그래프 복사
    
    # k = 중간 정점, i = 시작 정점, j = 종료 정점
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # i에서 j로 가는 최단 경로 업데이트 (중첩 최적 부분 구조)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def longest_increasing_subsequence(nums):
    if not nums:
        return 0
    
    n = len(nums)
    
    # dp[i] = nums[i]를 마지막 요소로 하는 LIS의 길이
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(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

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    
    # (거리, 노드) 쌍의 우선순위 큐
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        
        # 이미 처리된 노드는 건너뛰기
        if current_dist > dist[current_node]:
            continue
        
        # 인접 노드 탐색
        for neighbor, weight in enumerate(graph[current_node]):
            if weight > 0:  # 연결된 노드만 처리
                distance = current_dist + weight
                
                # 더 짧은 경로 발견 시 업데이트 (최적 부분 구조 활용)
                if distance < dist[neighbor]:
                    dist[neighbor] = distance
                    heapq.heappush(priority_queue, (distance, neighbor))
    
    return dist

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def knapsack_01(weights, values, capacity):
    n = len(weights)
    
    # dp[i][w] = 처음 i개 물건으로 무게 w를 채울 때의 최대 가치
    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:
                # i번째 물건을 포함하거나 포함하지 않는 두 경우 중 최대값 선택 (최적 부분 구조)
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                # i번째 물건이 너무 무거워 포함할 수 없는 경우
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

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

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    
    # dp[i][j] = word1[:i]를 word2[:j]로 변환하는 최소 연산 횟수
    dp = [[0 for _ in range(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  # 삽입 연산
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                # 문자가 같으면 연산 필요 없음
                dp[i][j] = dp[i-1][j-1]
            else:
                # 삽입, 삭제, 대체 중 최소 비용 선택 (최적 부분 구조)
                dp[i][j] = 1 + min(dp[i][j-1],      # 삽입
                                   dp[i-1][j],      # 삭제
                                   dp[i-1][j-1])    # 대체
    
    return dp[m][n]

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

def non_serial_dp_example(graph, weights):
    n = len(graph)
    # dp[mask] = mask에 포함된 노드들의 최적 부분 구조 값
    dp = [float('inf')] * (1 << n)
    dp[0] = 0  # 빈 집합의 값은 0
    
    # 모든 가능한 부분집합에 대해
    for mask in range(1, 1 << n):
        # 집합 내 각 노드에 대해
        for i in range(n):
            if mask & (1 << i):  # i가 mask에 포함되어 있다면
                # i를 제외한 부분집합
                prev_mask = mask & ~(1 << i)
                
                # 인접한 노드들의 가중치 합산
                additional_cost = 0
                for j in range(n):
                    if mask & (1 << j) and graph[i][j]:
                        additional_cost += weights[i][j]
                
                # 최적 부분 구조 활용
                dp[mask] = min(dp[mask], dp[prev_mask] + additional_cost)
    
    return dp[(1 << n) - 1]  # 모든 노드를 포함한 집합의 값

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def coin_change_optimized(coins, amount):
    # 무한대로 초기화
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 기본 사례: 금액이 0이면 동전 0개 필요
    
    # 모든 동전에 대해
    for coin in coins:
        # coin 이상의 모든 금액에 대해
        for i in range(coin, amount + 1):
            # 최적 부분 구조: 현재 동전을 사용하거나 사용하지 않는 경우 중 최소값
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class DPSolver:
    def __init__(self, problem_input):
        self.input = problem_input
        self.memo = {}  # 메모이제이션을 위한 딕셔너리
        
    def solve(self):
        # 문제 해결을 위한 진입점
        return self._solve_recursive(self._get_initial_state())
    
    def _get_initial_state(self):
        # 초기 상태 반환 (문제에 따라 구현)
        pass
    
    def _is_base_case(self, state):
        # 기저 사례 확인 (문제에 따라 구현)
        pass
    
    def _get_base_case_value(self, state):
        # 기저 사례 값 반환 (문제에 따라 구현)
        pass
    
    def _get_subproblems(self, state):
        # 현재 상태에서의 하위 문제들 반환 (문제에 따라 구현)
        pass
    
    def _combine_solutions(self, state, subproblem_solutions):
        # 하위 문제 해결책 결합 (문제에 따라 구현)
        # 최적 부분 구조 활용 지점
        pass
    
    def _solve_recursive(self, state):
        # 이미 계산된 상태인지 확인
        if state in self.memo:
            return self.memo[state]
        
        # 기저 사례 확인
        if self._is_base_case(state):
            return self._get_base_case_value(state)
        
        # 하위 문제 해결
        subproblems = self._get_subproblems(state)
        subproblem_solutions = [self._solve_recursive(subproblem) for subproblem in subproblems]
        
        # 하위 문제 해결책 결합 (최적 부분 구조 활용)
        result = self._combine_solutions(state, subproblem_solutions)
        
        # 메모이제이션
        self.memo[state] = result
        return result

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def debug_dynamic_programming(dp_function, test_cases):
    for i, (input_data, expected_output) in enumerate(test_cases):
        result = dp_function(input_data)
        
        print(f"Test Case {i+1}:")
        print(f"Input: {input_data}")
        print(f"Expected: {expected_output}")
        print(f"Result: {result}")
        print(f"Status: {'PASS' if result == expected_output else 'FAIL'}")
        print("-" * 40)

 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

# 기본 O(n²) 알고리즘
def longest_increasing_subsequence_basic(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 최적화된 O(n log n) 알고리즘
def longest_increasing_subsequence_optimized(nums):
    if not nums:
        return 0
    
    # tails[i] = 길이가 i+1인 LIS의 마지막 요소 중 가능한 가장 작은 값
    tails = []
    
    for num in nums:
        # 이진 검색으로 num이 들어갈 위치 찾기
        idx = bisect.bisect_left(tails, num)
        
        if idx == len(tails):
            # num이 모든 값보다 크면 추가
            tails.append(num)
        else:
            # 그렇지 않으면 해당 위치의 값 업데이트
            tails[idx] = num
    
    return len(tails)