파이썬 동적 계획법 알고리즘 구현 예시

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 단순한 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 각 하위 문제의 해답을 저장하여 중복 계산을 피하고 전체 문제의 최적해를 효율적으로 찾을 수 있도록 합니다. 이 문서에서는 여러 가지 고전적인 동적 계획법 문제들을 파이썬으로 구현한 예시들을 살펴봅니다.

0/1 배낭 문제

0/1 배낭 문제는 각각의 무게와 가치를 가진 n개의 물건들과 최대 수용 용량을 가진 배낭이 주어졌을 때, 배낭에 담을 수 있는 물건들의 최대 총 가치를 찾는 문제입니다. 각 물건은 한 번만 선택하거나 선택하지 않을 수 있습니다.

def solve_knapsack_max_value(item_weights, item_values, max_capacity):
    """
    0/1 배낭 문제의 최대 가치를 계산하는 동적 계획법 함수.

    Args:
        item_weights (list): 각 물건의 무게를 담은 리스트.
        item_values (list): 각 물건의 가치를 담은 리스트.
        max_capacity (int): 배낭이 수용할 수 있는 최대 무게.

    Returns:
        int: 배낭에 담을 수 있는 물건들의 최대 총 가치.
    """
    num_items = len(item_weights)
    
    # dp_table[i][j]는 i번째 물건까지 고려했을 때, 무게 j에서 얻을 수 있는 최대 가치를 저장
    dp_table = [[0 for _ in range(max_capacity + 1)] for _ in range(num_items + 1)]

    for item_idx in range(1, num_items + 1):
        for current_capacity in range(1, max_capacity + 1):
            weight_of_current_item = item_weights[item_idx - 1]
            value_of_current_item = item_values[item_idx - 1]

            if weight_of_current_item <= current_capacity:
                # 현재 물건을 포함하는 경우와 포함하지 않는 경우 중 최대 가치를 선택
                # 포함하는 경우: (이전 물건까지의 (현재 용량 - 현재 물건 무게)에서의 최대 가치) + 현재 물건 가치
                # 포함하지 않는 경우: 이전 물건까지의 현재 용량에서의 최대 가치
                dp_table[item_idx][current_capacity] = max(
                    dp_table[item_idx - 1][current_capacity],
                    dp_table[item_idx - 1][current_capacity - weight_of_current_item] + value_of_current_item
                )
            else:
                # 현재 물건의 무게가 현재 용량보다 크면, 현재 물건을 포함할 수 없음
                dp_table[item_idx][current_capacity] = dp_table[item_idx - 1][current_capacity]

    return dp_table[num_items][max_capacity]

고유 경로의 수 계산

로봇이 M x N 크기의 격자 좌측 상단(0,0)에서 시작하여 우측 하단(M-1, N-1)으로 이동하려고 합니다. 로봇은 한 번에 아래쪽(down) 또는 오른쪽(right)으로만 움직일 수 있습니다. 이 로봇이 우측 하단에 도달할 수 있는 고유한 경로의 총 개수를 찾아야 합니다.

def count_unique_grid_paths(rows, cols):
    """
    M x N 격자에서 로봇이 우측 하단으로 이동하는 고유 경로의 수를 계산하는 함수.
    로봇은 아래 또는 오른쪽으로만 이동할 수 있습니다.

    Args:
        rows (int): 격자의 행 수 (M).
        cols (int): 격자의 열 수 (N).

    Returns:
        int: 우측 하단까지의 고유 경로의 총 개수.
    """
    # path_counts[r][c]는 (r, c)까지 도달하는 고유 경로의 수를 저장
    path_counts = [[1] * cols for _ in range(rows)]

    # 첫 번째 행과 열은 모두 1로 초기화됩니다.
    # (0,0)에서 (0,c) 또는 (r,0)으로 가는 경로는 각각 1가지 뿐입니다.

    for r_idx in range(1, rows):
        for c_idx in range(1, cols):
            # (r_idx, c_idx)에 도달하는 경로는
            # (r_idx-1, c_idx)에서 아래로 오거나
            # (r_idx, c_idx-1)에서 오른쪽으로 오는 두 가지 방법의 합입니다.
            path_counts[r_idx][c_idx] = path_counts[r_idx - 1][c_idx] + path_counts[r_idx][c_idx - 1]

    return path_counts[rows - 1][cols - 1]

최소 경로 합

음이 아닌 정수로 채워진 M x N 격자 `input_grid`가 주어졌을 때, 좌측 상단에서 우측 하단까지의 경로 중 숫자의 합이 가장 작은 경로를 찾아 그 합을 반환하는 문제입니다. 로봇은 한 번에 아래쪽(down) 또는 오른쪽(right)으로만 이동할 수 있습니다.

def find_min_grid_path_sum(input_grid):
    """
    격자에서 좌측 상단에서 우측 하단까지의 최소 경로 합을 찾는 함수.
    로봇은 아래 또는 오른쪽으로만 이동할 수 있습니다.

    Args:
        input_grid (list of list): 음이 아닌 정수로 채워진 M x N 격자.

    Returns:
        int: 최소 경로 합.
    """
    num_rows = len(input_grid)
    num_cols = len(input_grid[0])

    # min_path_sums[r][c]는 (r, c)까지의 최소 경로 합을 저장
    min_path_sums = [[0] * num_cols for _ in range(num_rows)]

    # 시작점 초기화
    min_path_sums[0][0] = input_grid[0][0]

    # 첫 번째 열 초기화: 위에서 아래로만 이동 가능
    for r_idx in range(1, num_rows):
        min_path_sums[r_idx][0] = min_path_sums[r_idx - 1][0] + input_grid[r_idx][0]

    # 첫 번째 행 초기화: 왼쪽에서 오른쪽으로만 이동 가능
    for c_idx in range(1, num_cols):
        min_path_sums[0][c_idx] = min_path_sums[0][c_idx - 1] + input_grid[0][c_idx]

    # 나머지 셀 채우기
    for r_idx in range(1, num_rows):
        for c_idx in range(1, num_cols):
            # 현재 셀까지의 최소 경로는 위에서 오거나 왼쪽에서 오는 경로 중 더 작은 값에 현재 셀의 값을 더한 것
            min_path_sums[r_idx][c_idx] = min(
                min_path_sums[r_idx - 1][c_idx],
                min_path_sums[r_idx][c_idx - 1]
            ) + input_grid[r_idx][c_idx]

    return min_path_sums[num_rows - 1][num_cols - 1]

숫자 제거 및 점수 획득

정수 배열 `input_numbers`가 주어졌을 때, 다음 규칙에 따라 최대한 많은 점수를 얻는 것이 목표입니다. 배열에서 숫자 `x`를 선택하여 제거하면 `x`점수를 얻습니다. 이 작업을 수행한 후, 배열에서 `x-1`과 `x+1`에 해당하는 모든 요소도 제거해야 합니다. 초기 점수는 0이며, 최종적으로 얻을 수 있는 최대 점수를 반환해야 합니다.

def calculate_max_points_from_array(input_numbers):
    """
    정수 배열에서 특정 규칙에 따라 숫자를 제거하여 얻을 수 있는 최대 점수를 계산하는 함수.

    Args:
        input_numbers (list): 주어지는 정수 배열.

    Returns:
        int: 얻을 수 있는 최대 점수.
    """
    if not input_numbers:
        return 0

    # 배열 내의 최대값을 찾아 배열 크기를 결정
    max_val = max(input_numbers)
    
    # 각 숫자의 총 점수를 저장할 배열 (예: points_map[k]는 숫자 k의 총 합)
    # 인덱스 k를 선택하면 k * (k의 출현 횟수)를 얻음
    value_sums_for_num = [0] * (max_val + 1)
    for num_val in input_numbers:
        value_sums_for_num[num_val] += num_val

    # 동적 계획법 배열 초기화
    # dp_points[i]는 숫자 i까지 고려했을 때 얻을 수 있는 최대 점수
    dp_points = [0] * (max_val + 1)
    
    # 기본 케이스
    if max_val >= 1: # max_val이 0일 경우 points[1]이 유효하지 않을 수 있음
        dp_points[1] = value_sums_for_num[1]

    # 점화식: dp_points[i] = max(dp_points[i-1], dp_points[i-2] + value_sums_for_num[i])
    # dp_points[i-1]: i를 선택하지 않는 경우 (i-1을 선택했거나 안 했거나)
    # dp_points[i-2] + value_sums_for_num[i]: i를 선택하는 경우 (i-1과 i+1은 제거되므로 i-2까지의 최대 점수에 i의 점수를 더함)
    for current_num_val in range(2, max_val + 1):
        dp_points[current_num_val] = max(
            dp_points[current_num_val - 1],
            dp_points[current_num_val - 2] + value_sums_for_num[current_num_val]
        )

    return dp_points[max_val]

삼각형 최소 경로 합

정수로 이루어진 삼각형 배열 `triangle_grid`가 주어졌을 때, 맨 위에서 맨 아래까지의 최소 경로 합을 찾아야 합니다. 각 단계에서 현재 행의 숫자가 주어졌을 때, 다음 행의 인접한 숫자로만 이동할 수 있습니다. 즉, `i`번째 행의 `j`번째 숫자에 있다면, 다음 단계에서는 `i+1`번째 행의 `j`번째 숫자 또는 `j+1`번째 숫자로 이동할 수 있습니다.

def find_min_triangle_path_sum(triangle_grid):
    """
    삼각형 구조에서 맨 위에서 맨 아래까지의 최소 경로 합을 찾는 함수.

    Args:
        triangle_grid (list of list): 정수로 이루어진 삼각형 배열.

    Returns:
        int: 최소 경로 합.
    """
    if not triangle_grid:
        return 0

    num_rows = len(triangle_grid)
    
    # dp 배열을 가장 아랫줄로 초기화합니다.
    # 이는 역순으로 계산할 때 각 위치에서의 최소 경로 합을 저장하는 역할을 합니다.
    min_sums_current_row = list(triangle_grid[num_rows - 1])

    # 아래에서 위로 올라가면서 최소 경로 합을 계산합니다.
    # (num_rows - 2)부터 0번째 행까지 역순으로 순회
    for row_idx in range(num_rows - 2, -1, -1):
        # 현재 행의 각 요소에 대해 반복
        for col_idx in range(len(triangle_grid[row_idx])):
            # 현재 위치에서의 최소 경로는
            # (현재 값) + min(바로 아래 값, 아래-오른쪽 값)
            # min_sums_current_row[col_idx]는 (row_idx+1, col_idx) 위치의 최소 합
            # min_sums_current_row[col_idx+1]은 (row_idx+1, col_idx+1) 위치의 최소 합
            min_sums_current_row[col_idx] = triangle_grid[row_idx][col_idx] + \
                                            min(min_sums_current_row[col_idx], min_sums_current_row[col_idx + 1])

    # 최종 결과는 맨 위(0,0)의 최소 경로 합입니다.
    return min_sums_current_row[0]

태그: dynamic programming python knapsack problem Grid Traversal Algorithms Minimum Path Sum

11월 8일 21:37에 게시됨