동적 계획법(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]