DP (다이나믹 프로그래밍) 기본개념/기본문제
[ 1차원DP 기본문제 ]
- 거스름돈 문제
- 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] #오른쪽 아래 끝까지의 최소경로합