📚 다이나믹 프로그래밍
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법이다.
다이나믹 프로그래밍은 점화식을 그대로 코드로 옮겨서 구현할 수 있다.
점화식 : 인접한 항들 사이의 관계식을 의미한다.
다이나믹 프로그래밍은 그 자체로도 다양한 문제로 출제될 수 있는 유형이지만, 그래프 이론 등 다양한 알고리즘에서도 자주 사용된다.
또한, 플로이드 위셜 알고리즘은 다이나믹 프로그래밍을 활용한 알고리즘이다.
탑 다운 방식 : 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.
보텀업 방식 : 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식이다.
📚 문제
📖 Q 31 금광
2차원 테이블을 이용한 다이나믹 프로그래밍으로 해결할 수 있다.
금광의 모든 위치에 대하여 (1) 왼쪽 위에서 오는 경우, (2) 왼쪽 아래에서 오는 경우, (3) 왼쪽에서 오는 경우 3가지 경우가 존재한다.
이 3가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 저장해주어 문제를 해결할 수 있다.
array 변수는 초기 '금광' 정보를 담고 있으며, dp 변수는 다이나믹 프로그래밍을 위한 2차원 테이블이다.
dp 테이블이 접근해야 할 때마다 리스트의 범위를 벗어나지 않는지 체크할 필요가 있다.
또한, dp 테이블에 초기 데이터를 담아서 점화식에 따라서 dp 테이블을 갱신할 수 있다.
# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 다이나믹 프로그래밍을 위한 2차원 dp 테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[index:index+m])
index += m
print(dp)
# 다이나믹 프로그래밍 진행
for j in range(1, m):
for i in range(n):
# 왼쪽 위에서 오는 경우
if i == 0:
left_up = 0
else:
left_up = dp[i-1][j-1]
# 왼쪽 아래에서 오는 경우
if i == n - 1:
left_down = 0
else:
left_down = dp[i+1][j-1]
# 왼쪽에서 오는 경우
left = dp[i][j-1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m-1])
print(result)
📖 Q 32 정수 삼각형
이 문제에서도 특정한 위치로 도달하기 위해서는 (1) 왼쪽 위, (2) 바로 위 2가지 위치까지의 최적의 합 중에서 더 큰 합을 가지는 경우를 선택하면 된다.
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i-1][j])
n = int(input())
list_array = []
dp = [[0] * n for _ in range(n)]
for idx in range(n):
list_array.append(list(map(int, input().split())))
col_idx = 0
dp[0][0] = list_array[0][0]
for row in range(1, n):
for col in range(0, len(list_array[row])):
if col == 0:
dp[row][col] = dp[row-1][col] + list_array[row][col]
elif col == len(list_array[row]) - 1:
dp[row][col] = dp[row -1][col - 1] + list_array[row][col]
else:
dp[row][col] = max(dp[row - 1][col - 1], dp[row - 1][col]) + list_array[row][col]
print(max(dp[n-1][0:n]))
📖 Q 33 퇴사
문제를 풀 때 뒤쪽 날짜부터 거꾸로 확인하는 방식으로 접근하여 해결하는 다이나믹 프로그래밍의 아이디어를 떠올릴 수 있다.
뒤쪽부터 매 상담에 대하여 '현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터 최대 이윤 (dp[t[i] + [i]])' 을 계산하면 된다.
dp[i] = i 번째 날부터 마지막 날까지 낼 수 있는 최대 이익
점화식
dp[i] = max(p[i] + dp[t[i] + i]], max_value)
n = int(input()) # 전체 상담 개수
t = [] # 각 상담을 완료하는데 걸리는 시간
p = [] # 각 상담을 완료했을 때 받을 수 있는 금액
dp = [0] * (n + 1) # 다이나믹 프로그래밍을 위한 1차원 dp 테이블 초기화
max_value = 0
for _ in range(n):
x, y = map(int, input().split())
t.append(x)
p.append(y)
# 리스트를 뒤에서부터 거꾸로 확인
for i in range(n -1, -1, -1):
time = t[i] + i
print("t[i] : ", t[i], " i : ",i, " n : ", n)
# 상담이 기간 안에 끝나는 경우
if time <= n:
# 점화식에 맞게, 현재까지의 최고 이익 계산
dp[i] = max(p[i] + dp[time], max_value)
max_value = dp[i]
# 상담이 기간을 벗어나는 경우
else:
dp[i] = max_value
print("dp : ", dp)
print(dp)
print(max_value)
📖 Q 34 병사 배치하기
이 문제의 기본 아이디어는 '가장 긴 증가하는 부분 수열(LIS)'로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다.
가장 긴 증가하는 부분 수열 : 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다.
(LIS : Longest Increasing Subsequence)
ex) array = [10, 20, 10, 30, 20, 50], 이때 가장 긴 증가하는 부분 수열 : [10, 20, 30, 50]
D[i] = array[i] : 마지막 원소로 가지는 부분 수열의 최대 길이
가장 긴 증가하는 부분 수열을 계산하는 점화식
- DP 테이블의 값은 모두 1로 초기화한다.
모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]
실행 예시
6
10 20 10 30 20 50
i, j 1 0 , array[j] : 10 array[i] 20 , dp[i] : 1 , dp[j] + 1 : 2
i, j 3 0 , array[j] : 10 array[i] 30 , dp[i] : 1 , dp[j] + 1 : 2
i, j 3 1 , array[j] : 20 array[i] 30 , dp[i] : 2 , dp[j] + 1 : 3
i, j 3 2 , array[j] : 10 array[i] 30 , dp[i] : 3 , dp[j] + 1 : 2
i, j 4 0 , array[j] : 10 array[i] 20 , dp[i] : 1 , dp[j] + 1 : 2
i, j 4 2 , array[j] : 10 array[i] 20 , dp[i] : 2 , dp[j] + 1 : 2
i, j 5 0 , array[j] : 10 array[i] 50 , dp[i] : 1 , dp[j] + 1 : 2
i, j 5 1 , array[j] : 20 array[i] 50 , dp[i] : 2 , dp[j] + 1 : 3
i, j 5 2 , array[j] : 10 array[i] 50 , dp[i] : 3 , dp[j] + 1 : 2
i, j 5 3 , array[j] : 30 array[i] 50 , dp[i] : 3 , dp[j] + 1 : 4
i, j 5 4 , array[j] : 20 array[i] 50 , dp[i] : 4 , dp[j] + 1 : 3
[1, 2, 1, 3, 2, 4]
2
최종적으로 테이블의 값은 [1, 2, 1, 3, 2, 4]이고, 이렇게 테이블에 남아 있는 값 중에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이이다.
현재 예시에서는 4가 최장 길이가 된다.
문제에서는 '가장 긴 감소하는 부분 수열'의 길이를 계산하는 문제로 간주하고, 입력으로 주어진 원소의 순서를 뒤집은 뒤에 '가장 긴 증가하는 부분 수열' 문제를 풀 때의 점화식을 그대로 적용하면 해결할 수 있다.
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '가장 긴 증가하는 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
# 만약, 현재 기준 값보다 작다면 횟수를 증가시킨다.
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외시켜야 하는 병사의 최소 수를 출력
print(n - max(dp))
📖 Q 35 못생긴 수
못생긴 수 : 2, 3, 5 만을 소인수로 가지는 수 (오직 2, 3, 5를 약수로 가지는 합성수)
못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해서 2의 배수, 3의 배수, 5의 배수를 고려한다는 점을 기억하여 효율적으로 소스코드를 작성하면 다음과 같이 작성할 수 있다.
n = int(input())
ugly = [0] * n # 못생긴 수를 담기 위한 테이블(1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1
# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈값을 초기화
next2, next3, next5 = 2, 3, 5
# 1부터 n까지 못생긴 수를 찾기
for l in range(1, n):
# 가능한 곱셈 결과 중에서 가장 작은 수를 선택
ugly[l] = min(next2, next3, next5)
# 인덱스에 따라서 곱셈 결과를 증가
if ugly[l] == next2:
i2 += 1
next2 = ugly[i2] * 2
if ugly[l] == next3:
i3 += 1
next3 = ugly[i3] * 3
if ugly[l] == next5:
i5 += 1
next5 = ugly[i5] * 5
# print("idx : ", l , ", i2 : ", i2, ", i3 : ", i3, ", i5 : ", i5, ", ugly[l] : ", ugly[l])
# print("next2 : ",next2, " next3 : ", next3, " next5 : ",next5)
# print(ugly)
# print()
# n번째 못생긴 수를 출력
print(ugly[n-1])
📖 Q 36 편집 거리
이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤에, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다.
점화식
(1) 두 문자가 같은 경우 : dp[i][j] = dp[i - 1][j - 1]
➡️ 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
(2) 두 문자가 다른 경우 : dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
➡️ 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수중에서 가장 작은 수에 1을 더해 대입
sunday ➡️ saturday
ex) sun 이라는 문자열을 sat 이라는 문자열로 바꾸기 위한 최소 편집 거리 : dp[3][3] : 2
테이블의 가장 오른쪽 아래에 있는 값이 구하고자 하는 최소 편집 거리가 된다. : 3
# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
n = len(str1)
m = len(str2)
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * (m + 1) for _ in range(n + 1)]
# DP 테이블 초기 설정
for i in range(1, n + 1):
dp[i][0] = i
for j in range(1, m + 1):
dp[0][j] = j
# 최소 편집 거리 계산
for i in range(1, n + 1):
for j in range(1, m + 1):
# 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
# 문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
return dp[n][m]
# 두 문자열을 입력받기
str1 = input()
str2 = input()
# 최소 편집 거리 출력
print(edit_dist(str1, str2))
