Dynamic Programing은 큰 문제를 작은 문제로 나눠서 푸는 유형이다.
사실 이게 백트래킹보다 훨씬 어렵다.
dp를 풀 떄, Top-down tabulation으로 풀거나, memoization으로 풀거나 두가지 방식이 있는데 tabulation만 알아도 된다.
Subproblem을 합치면 되는 DP
가장 기본적인 dp문제이다. 피보나치를 풀듯, 가장 작은 단계부터 합해가면서 위로 올라오면 된다.
BST 구하기
BST의 가능한 모든 가지수를 구하는 문제이다.
개념만 이해하면 참 쉬운데 일단 노드가 1개 2개일때는 각각 1과 2로 지정한다.
그리고 만약 노드가 { 1 2 3 } 이라고한다면 1이 root일때, 왼쪽에 들어갈 수 있는 갯수는 0, 오른쪽은2, 2가 루트일때는 1과 1, 3일때는 1과 2 이런식이다.
dp[i] += (dp[j] * dp[i - j - 1]) 이라고 할 수 있다.
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
for j in range(0, n):
dp[i] += (dp[j] * dp[i - j - 1])
print(dp[-1])격자에서 한칸씩 전진하는 DP
격자에서 주어진 조건에 따라 이동하면서 마지막 구간의 최대값을 구하는 dp이다.
경로의 관점에서 생각해본다면, a 지점까지 오는데 3가지정도의 경로가 있다고 하더라도 a입장에서는 어차피 가장 큰 값을 고르면 끝나는 문제이다. 따라서 우리는 각 칸에 최대값을 집어넣는 dp를 구성하면 된다.
다만 조건에 따라 특정 라인들은 최대값이 항상 고정이다. 이 초기조건을 잘 조정해야한다.
n = int(input())
grid = []
dp = [[0 for _ in range(n)] for _ in range(n)]
ans = 0
for _ in range(n):
grid.append(list(map(int, input().split())))
for i in range(n):
for j in range(n):
if j == 0:
dp[i][j] = grid[i][j] + dp[i-1][j]
elif i == 0:
dp[i][j] = dp[i][j - 1] + grid[i][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
for j in range(n):
ans = max(ans, dp[n-1][j])
print(ans)최소값의 최대
- nn의 격자가 있을때 nn까지 가는 루트가 존재한다.
- 해당 루트에 최소값들이 있다.
- 최소값들중 가장 큰 값을 구한다.
어떤 지점으로 올 수 있는 루트중에서 가장 최소값을 항상 기록해주면 되는 문제이다.
만약 오른쪽과 아래로만 갈 수 있는 문제라면
for i in range(n):
for j in range(n):
if i == 0 and j == 0:
dp[0][0] = grid[0][0]
elif j == 0:
dp[i][j] = min(dp[i-1][j], grid[i][j])
elif i == 0:
dp[i][j] = min(dp[i][j - 1], grid[i][j])
else:
dp[i][j] = min(max(dp[i-1][j], dp[i][j-1]), grid[i][j])다음과 같이 구성된다.
j == 0일때는 무조건 오른쪽에서 오니깐 오른쪽값과 자신을 비교해 더 작은값을
i==0 일때는 항상 위에서 오니깐 위의 값과 자신을 비교하면 된다.
그 밖에 경우에는 위 혹은 오른쪽 두군데에서 오게된다. 따라서 이 두 곳의 최소값들중 더 큰값을 고르고, 그 값과 자신의 값 중 더 작은 값을 고른다.
진행하다 끊어지는 DP
수열이 주어지고 그 수열에서 연결된 부분수열들 중에서 최대값을 찾는 문제이다. 만약 우리가 i번째 원소를 살펴보는데 그전까지의 최대 연속수열이 2가지 경우가 있고 그 값들의 합이 모두 2라고 한다면, i번째 입장에서는 뭐를 골라도 그만인 문제이다. 따라서 우리는 각 칸에 해당 값을 포함하는 최대수열크기를 적어주면 되는것이다.
n = int(input())
arr = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
if i == 0:
dp[i] = arr[i]
else:
dp[i] = max(arr[i], dp[i-1] + arr[i])
print(max(dp))M개의 구간 선택하기
M개의 구간 선택하기 문제는 특정 수열을 주고 그 안에서 M개의 구간을 선택해서 최대값을 뽑아내는 문제이다.
이떄 우리는 i번째수가 포함되는 경우 안되는 경우 두 경우로 나눠서 접근해야한다.
우선 이 문제의 dp는 dp[n][m] = n개의 수 m개의 구간에서 최대값 이다.
-
만약 포함되지 않는다면
i가 m안에 포함되지 않는다면, dp[i][j] = dp[i-1][j]이다. 다시말해, 포함되지 않는다면 i를 제외한 m구간과 동일한 최대값을 가진다는 뜻이다. -
만약 포함된다면
i가 m안에 들어간다면
2-1) i-1 까지의 m 구간에 추가되는 경우
2-2) i-1 m-1의 구간까지 시행되고, 그 다음 구간의 시작점 이렇게 두가지 경우가 있을수 있다.
따라서 이 두가지 경우중 max값을 고르고 arr[i]를 하면 된다.
이를 dp 식으로 나타낼때, 3차원 배열을 사용하거나, 2차원 배열을 2개 사용하여 풀 수 있다.
for i in range(1, n+1):
for j in range(1, m + 1):
nonbelong_dp[i][j] = max(belong_dp[i-1][j], nonbelong_dp[i-1][j])
belong_dp[i][j] = max(belong_dp[i-1][j], nonbelong_dp[i-1][j-1])+arr[i-1]조건에 맞게 전진하는 dp
각 위치에 적힌 숫자가 최대 점프 거리이고, 조건에 맞게 거리를 구하는 문제이다.
이 문제도 i지점까지 오는 방법은 여러가지 있을 수 있겠지만, i지점 입장에서는 어차피 가장 작은 값을 고르기에 각 dp에는 최소값을 적어주면 되는 문제이다. 다만 i지점에서 최소값을 고르기 위해서는 j라는 이중루프틀 이용해 0부터 i-1까지 탐색을 하면서 j + a[j] 최소 i까지 올 수 있는 값들중 최대값을 찾아나가야한다.
for i in range(1, n + 1):
for j in range(0, i):
if dp[j] + a[j] >= i:
dp[i] = max(dp[i], dp[j] + 1)
부분증가수열
이 문제도 이전문제와 비슷하게 접근해야하는데 수열에서 최장증가부분수열을 구하는것이다. 즉, i값에서 j (0~i)까지 루프를 돌면서 arr[j] < arr[i]인 그 최대값을 찾는 문제이다. dp[i]와 j값에서 1증가한 값을 비교한다.
import sys
n = int(input())
arr = [0 for _ in range(n + 1)]
temp_arr = list(map(int, input().split()))
arr[1:] = temp_arr[:]
dp = [-sys.maxsize] * (n + 1)
dp[0] = 0
arr[0] = 0
for i in range(1, n + 1):
for j in range(0, i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))스케줄링? 문제
어떠한 일의 시작정보 끝정보 value가 주어질때, 최대로 얻일 수 있는 value를 구하는 문제이다.
이 경우 값을 계산해서 dp에 저장하지만, 동시에 일의 시작정보나 끝 정보도 저장해야하고 시장정보와 끝 정보를 비교해서 항상 풀이에 접근해야한다
자세한 설명은 주석에 적도록 하겠다
import sys
n = int(input())
info = []
for _ in range(n):
s, e, p = map(int, input().split())
info.append((s,e,p))
dp = [(0,0)] * n
dp[0] = (info[0][2], info[0][1])
flag = True
for i in range(1, n):
for j in range(0, i):
if dp[j][1] < info[i][0]: # 만약 이전 작업 종료보다 현 작업이 더 늦게 시작된다면(안겹친다면)
money = max(dp[i][0], dp[j][0] + info[i][2]) # dp값과 과거 최대값 + 지금부터 할 일의 값중 더 큰 값을 선택한다.
dp[i] = (money, info[i][1]) # 일의 value와 동시에 현재 일이 끝나는 시간도 기록
flag = False # 한번이라도 실행되었다면 그게 무조건 큰 값이 될 수밖에 없다 (10 100 보다는 110이 크다)
if flag: # 만약 위의 조건이 한번도 실행되지 않았다면(일이 무조건 겹친다면)
dp[i] = (info[i][2], info[i][1]) # new moeny, new end time # dp는 처음실행되니깐 새로운값과 새로운 종료시간을 가짐
max = -sys.maxsize
for i in dp:
if i[0] > max:
max = i[0] # dp중에서 가장 큰 값이 정답
print(max)
