동적 계획법 - 3. 실전 문제 응용

3. 실전 문제 응용

동적 계획법(DP)을 실전 문제에 적용하면 최적의 해를 빠르게 구할 수 있습니다.
이번 장에서는 경로 찾기, 문자열 및 수열 문제, 최적화 문제에서 DP를 활용하는 방법을 배웁니다.

---

3-1. 경로 찾기 관련 문제

📌 최단 경로 문제 (Minimum Path Sum) - 입력 검증 추가

문제 설명

• m×n 크기의 2D 격자(grid)가 주어졌을 때,
  왼쪽 위에서 오른쪽 아래로 이동하는 최소 비용 경로를 찾는 문제입니다.
• 이동 가능 방향: 오른쪽(→), 아래(↓)
• 각 칸에는 이동 비용(양의 정수)이 주어짐.

점화식

dp[i][j]=min⁡(dp[i−1][j],dp[i][j−1])+grid[i][j]

초기 조건:

• 첫 번째 행과 첫 번째 열은 이동 경로가 1가지뿐이므로 누적합을 계산.

시간 복잡도:

• O(m×n) (2D DP 테이블을 채우는 과정)
  공간 복잡도:
• O(n) (1D DP 최적화 가능)

---

바텀업 DP 코드 (입력 검증 추가 포함)

def min_path_sum(grid):
    # 입력 검증: grid가 비어있거나, 행의 길이가 다르면 예외 발생
    if not grid or not grid[0]:
        raise ValueError("Grid cannot be empty")
    if any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("Grid must be rectangular")

    m, n = len(grid), len(grid[0])
    dp = [0] * n

    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]

    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]

    return dp[-1]

# 테스트 케이스
grid1 = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid1))  # 출력: 7 (1→3→1→1→1)

grid2 = [[5]]  # 단일 원소 테스트
print(min_path_sum(grid2))  # 출력: 5

grid3 = [[1, 2, 3], [4, 5, 6]]  # 2x3 격자
print(min_path_sum(grid3))  # 출력: 12

# 예외 처리 테스트
try:
    print(min_path_sum([]))  # 빈 격자
except ValueError as e:
    print(f"Error: {e}")  # 출력: Grid cannot be empty

try:
    print(min_path_sum([[1, 2], [3]]))  # 비정형 격자
except ValueError as e:
    print(f"Error: {e}")  # 출력: Grid must be rectangular

 

 

---

3-2. 문자열 및 수열 문제

📌 팰린드롬 분할 (Palindrome Partitioning) - 초기값 수정 및 테스트 케이스 추가

문제 설명

• 문자열을 최소 개수의 팰린드롬 문자열로 분할하는 문제.

점화식

dp[i]=min⁡(dp[j]+1)  (if substring s[j:i] is palindrome)

바텀업 DP 코드 (초기값 수정 포함)

def min_palindrome_partition(s):
    n = len(s)
    dp = [float('inf')] * n
    dp[0] = 0  # 길이가 1인 문자열은 자체적으로 팰린드롬

    palindrome = [[False] * n for _ in range(n)]

    # 팰린드롬 여부 사전 계산
    for i in range(n):
        for j in range(i+1):
            if s[i] == s[j] and (i - j <= 1 or palindrome[j+1][i-1]):
                palindrome[j][i] = True

    # 최소 분할 수 계산
    for i in range(n):
        if palindrome[0][i]:
            dp[i] = 0
        else:
            for j in range(i):
                if palindrome[j+1][i]:
                    dp[i] = min(dp[i], dp[j] + 1)

    return dp[n-1]

# 테스트 케이스
print(min_palindrome_partition("aab"))  # 출력: 1 ("aa", "b")
print(min_palindrome_partition("abc"))  # 출력: 2 ("a", "b", "c")
print(min_palindrome_partition("racecar"))  # 출력: 0 (이미 팰린드롬)

---

3-3. 최적화 문제

📌 행렬 곱셈 순서 (Matrix Chain Multiplication) - 예외 처리 및 입력 검증 추가

문제 설명

• 여러 개의 행렬을 곱할 때, 괄호를 적절히 배치하여 최소 연산 횟수를 구하는 문제
• 예시:
  • 행렬 A_1, A_2, A_3, A_4의 차원이 p = [10, 20, 30, 40, 30]일 때
  • 최적의 괄호 배치: ( ( A_1 A_2 ) ( A_3 A_4 ) )
  • 최소 연산 횟수: 30000

점화식

dp[i][j]=min⁡(dp[i][k]+dp[k+1][j]+pi−1 pk pj)

시간 복잡도:

• O(n^3) (모든 부분 문제 계산)
  공간 복잡도:
• O(n^2) (DP 테이블 및 괄호 배치 저장)

---

바텀업 DP 코드 (예외 처리 및 입력 검증 포함)

import sys

def matrix_chain_order(p):
    # 입력 검증: p는 리스트여야 하며, 모든 요소는 양의 숫자여야 함
    if not isinstance(p, list):
        raise TypeError("Input must be a list")
    if any(not isinstance(x, (int, float)) for x in p):
        raise ValueError("All dimensions must be numbers")
    if any(x <= 0 for x in p):
        raise ValueError("All dimensions must be positive")

    n = len(p) - 1
    
    # 입력 검증: 행렬이 하나 이하일 경우 연산 불필요
    if n < 1:
        return 0, "A1"

    # 공간 복잡도: O(n²) 메모리 사용
    dp = [[0] * n for _ in range(n)]
    bracket = [[-1] * n for _ in range(n)]  # 최적의 괄호 배치를 저장

    # DP 테이블 채우기
    for length in range(2, n+1):  # 부분 행렬 크기
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = sys.maxsize
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    bracket[i][j] = k  # 최적의 분할 위치 저장

    # 최적의 괄호 배치를 재귀적으로 생성
    def construct_optimal_solution(i, j):
        if i == j:
            return f"A{i+1}"
        k = bracket[i][j]
        left_part = construct_optimal_solution(i, k)
        right_part = construct_optimal_solution(k+1, j)
        return f"({left_part} {right_part})"

    optimal_parenthesization = construct_optimal_solution(0, n-1)
    
    return dp[0][n-1], optimal_parenthesization

# 테스트 케이스
p1 = [10, 20, 30, 40, 30]
min_cost1, optimal_order1 = matrix_chain_order(p1)
print(f"최소 연산 횟수: {min_cost1}")  # 출력: 30000
print(f"최적의 괄호 배치: {optimal_order1}")  # 출력: ((A1 A2) (A3 A4))

# 예외 처리 테스트
try:
    matrix_chain_order("invalid input")
except Exception as e:
    print(f"Error: {e}")  # 출력: TypeError

try:
    matrix_chain_order([10, -20, 30])
except Exception as e:
    print(f"Error: {e}")  # 출력: ValueError (양수만 허용)

try:
    matrix_chain_order([10, "a", 30])
except Exception as e:
    print(f"Error: {e}")  # 출력: ValueError (숫자만 허용)

---