DP (다이나믹 프로그래밍) 기본개념/기본문제

 

[ 1차원DP 기본문제 ]

 

1. 거스름돈 문제

• 11원을 만들 때 최소한의 동전 개수를 찾고 싶습니다.
• 사용할 수 있는 동전은 [1, 2, 5]입니다.

 

     dp[x] : x원을 만들기 위한 최소 동전 개수

     1을 사용하면 dp[10] + 1 (10원을 만드는 방법에 동전1 추가)

     2를 사용하면 dp[9] + 2  (9원을 만드는 방법에 동전2 추가)

     5를 사용하면 dp[6] + 5

      - dp[6] = dp[5] + 1 (5원을 만드는 방법 동전1 추가)

     

     >> 각 경우 중 가장 작은 경우

     dp[x] = min(dp[x-1] + 1, dp[x-2] + 1, dp[x-5] + 1)

     

     "x원을 만들기 위해 필요한 최소 동전 개수는, 그보다 작은 금액들을 만들 수 있는 최소 동전 개수 + 마지막 동전 1개"라는 의미

 

 

2. 1로만들기

 

1)  X가 3으로 나누어떨어지면, 3으로 나눕니다

2) X가 2로 나누어떨어지면, 2로 나눕니다.

3) 1을 뺍니다.

정수 X를 1로 만들기 위해 최소 몇 번의 연산을 해야 하는지 구하는 문제입니다.

 

[해결아이디어]

점화식:

dp[x]는 다음 세 가지 선택지에서 최소값을 선택한 결과로 구할 수 있습니다:

• dp[x-1] + 1: 1을 빼는 연산
• dp[x // 2] + 1: 2로 나눌 수 있으면 나누는 연산
• dp[x // 3] + 1: 3으로 나눌 수 있으면 나누는 연산

최종적으로는 이 세 가지 연산 중 가장 작은 값을 선택하게 됩니다.

 

def make_one(n):
    dp = [0] * (n+1) # dp[1] ~ dp[n]을 사용하기 위함
    for i in range(2, n+1):  # dp[2] ... dp[7] 작은수부터 차례대로 채워나간다
        # 기본적으로 1을 빼는 경우로 초기화
        dp[i] = dp[i - 1] + 1

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3] + 1)
        

    return dp[i]

 

 

3. 최대부분수열합

 

array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

 

dp[1] : 1번째요소 포함한 최대 부분수열 합 > -2+1 or -3 > -2+1이 더 큼

따라서 dp[1] = [-2,1]의 합인 -1     

dp[2] : 2번째요소를 포함한 최대 부분수열 합 >  -2+1+-3 or 4 < 4가 더 큼

dp[2] = 4

def max_subarray_sum(arr):
    n = len(arr)
    dp = [0] * n
    dp[0] = arr[0]
    max_sum = dp[0]

    for i in range(1, n):
        # i번째 원소를 포함하는 최대 부분 합
        dp[i] = max(dp[i-1] + arr[i], arr[i])
        # 전체 최대값 갱신
        max_sum = max(max_sum, dp[i])

    return max_sum

 

 

 

[ 2차원DP 기본문제 ]

 

최소 경로 합 (Minimum Path Sum)

문제 설명:

• m x n 크기의 격자가 주어집니다. 각 칸에는 숫자가 쓰여 있습니다.
• 왼쪽 위에서 시작해서 오른쪽 아래로 이동하려고 합니다.
• 오직 오른쪽 또는 아래로만 이동할 수 있습니다.
• 이때, 각 칸의 숫자는 그 칸을 지날 때의 비용을 의미하며, 경로 상의 숫자 합이 최소가 되도록 이동하는 경로를 찾으세요.

grid = [ [1, 3, 1], 

             [1, 5, 1],

            [4, 2, 1] ]

(경로: 1 → 3 → 1 → 1 → 1) 총 합 7이 최소경로합

 

def min_path_sum(grid):
    m, n = len(grid), len(grid[0]) # 행, 열 개수
    dp = [ [0] * n for _ in range(m) ]
    # 시작점 초기화
    dp[0][0] = grid[0][0]
    # dp[i][j] : i행j열까지 가는 최소 비용 합
    # 첫번째 행,열은 각각 오른쪽이나 아래로만 이동 할 수 있으므로 따로 계산
    
    # 첫번째 행
    for j in range(1,n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    # 첫번째 열
    for i in range(1,m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    # 나머지dp - 위에서 오거나, 왼쪽에서 오거나 둘 중 하나 (최소값)
    for i in range(1,m):
        for j in range(1,n):
            dp[i][j] =  min( dp[i-1][j], dp[i][j-1] ) + grid[i][j]

    return dp[m-1][n-1] #오른쪽 아래 끝까지의 최소경로합