[알고리즘/코드트리] 동적계획법 DP

Subproblem 을 그대로 합치면 되는 DP

DP 는 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법이다.

작은 문제들을 연쇄적으로 풀면 큰 문제의 답을 얻을 수 얻겠다! 라는 해석을 할 수 있다면 이 문제는 쉬운 DP 문제라고 할 수 있다. 만약 바로 생각이 안나고 꼬여져 있다면 어려운 DP 문제이다.

쉬운 문제의 예시는 피보나치 수열이 있다. 피보나치 수열은 수열의 자기 전과 자기 전전을 더해서 만드는 건데 a[n] = a[n-1] + a[n-2] 의 점화식이 나온다.
이런 문제를 동적계획법으로 푼다면, 아 n 번쨰 문제는 n-1 번쨰와 n-2 번쨰의 답을 알고 있으면 구할 수 있겠다! 라고 해석할 수 있기 때문에 DP 로 풀 수 있다. 만약 문제를 읽었는데 작은 문제도 잘 정의하고 작은 문제의 답을 구하는 것도 성공했다면 구현을 하면 된다.
구현 방식은 크게 2가지가 있다. 첫 번째는 for 문을 돌리는 것이고, 두 번째는 재귀를 이용하는 방법이다.

재귀함수를 이용해서 피보나치를 돌린다면 다음처럼 코드를 짤 수 있다. 50번째 피보나치 수를 구하려면 fibo 함수가 엄청나게 많이 호출된다. 종료조건까지 호출되기 때문에 n 이 조금만 늘어도 호출되는 횟수가 기하급수적으로 늘 것이다. 그래서 호출 횟수를 줄이려면 이미 답을 구한 문제를 저장해야한다. 피보나치 예시에서는 최초로 답이 구해지는 순간은 메모리에 값을 저장한다. fibo(5) 를 호출했다면 fibo(5) fibo(4) fibo(3) fibo(2) fibo(1) 을 거치게 되는데 이렇게 처음으로 거친 애들은 저장을 한다. 작은 문제가 풀리는 최초의 순간들을 저장해둔다면, 다음에 또 호출될 때는 저장된 애를 그냥 꺼내면 된다.

이런 걸 메모이제이션이라고 한다.

def fibo(n):
	if n <= 2:
    	return 1
     else:
     	return fibo(n-1) + fibo(n-2)

1. 피보나치 수

https://www.codetree.ai/missions/2/problems/fibonacci-number?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에는 N이 주어집니다.
1≤N≤45

출력 형식
N번째 피보나치 수를 출력합니다.

입출력 예제
예제1
입력:
2

출력:
1

내가 짠 코드

n = int(input())

MAX_NUM = 45

dp = [0 for _ in range(MAX_NUM+1)]

dp[1] = dp[2] = 1

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2] 

print(dp[n])

2. 계단 오르기

https://www.codetree.ai/missions/2/problems/climbing-stairs?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에 n이 주어집니다.
2 ≤ n ≤ 1,000

출력 형식
n층 높이의 계단에 올라가기 위한 서로 다른 방법의 수를 10,007로 나눈 나머지를 출력합니다. 만약 불가능하다면 0을 출력합니다.

입출력 예제
예제1
입력:
2

출력:
1

내가 짠 코드

n = int(input())

# 2, 3 , 2+3, 3+3, 2+3+3, 2+2+2, 3+2
# f(2) = 1 
# f(3) = 1
# f(4) = f(2) + 2 = 1
# f(5) = f(2) + 3 / f(3) + 2 = 2
# f(6) = f(3) + 3 / f(4) + 2 = 2
# f(7) = f(4) + 3 / f(5) + 2 = 1 + 2 = 3
# f(8) = f(5) + 3 / f(6) + 2 = 2 + 2 = 4




MAX_N = 1000

memo = [0] * (MAX_N + 1)
memo[2], memo[3], memo[4] = 1, 1, 1

for i in range(5, n+1):
    memo[i] = memo[i-2] + memo[i-3]


print(memo[n]%10007)

격자 안에서 한 칸씩 전진하는 DP

어떤 문제를 DP 로 풀려면 결과가 확정되어야할 뿐만 아니라 결과로 가기위해 거치게 되는 과정들도 다 확정이 되어 있어야한다.

DP 를 풀기 위해 다음 세가지 질문을 해봐야한다.
1. 작은 문제의 값을 구할 수 있는가?
2. 이미 해결된 문제의 답이 바뀌지 않는가?
3. 문제의 답을 가지고 다음 문제를 풀 수 있는가?

1. 정수 사각형 최대 합

https://www.codetree.ai/missions/2/problems/maximum-sum-path-in-square?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에는 N이 주어집니다.
두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.
1≤N≤100
1≤ 행렬에 주어지는 숫자 ≤1,000,000

출력 형식
가능한 최대 합을 출력합니다.

입출력 예제
예제1
입력:
3
1 2 3
3 2 1
4 2 1

출력:
11

접근 방식
i 행 j 열까지 도착했을 때 최대 합은
dp[i][j] = dp[i-1][j-1], dp[i-1][j] 중 둘 중의 큰값 + 자기 자신의 값 arr[i][j] 이다. 이런식으로 테이블을 채우면 된다.

단, 처음 세팅을 해줘야 한다.
dp[1][1] = arr[1][1] 초기값은 자기 자신이고,
dp[2][1], dp[2][2] 은 자기 자신 + arr[1][1] 이다.

내가 짠 코드

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]


arr_sum = [[0] * n  for _ in range(n)]

# 초기값 세팅
arr_sum[0][0] = arr[0][0]

# 가장자리 채우기 
for i in range(1, n):
    arr_sum[i][0] = arr_sum[i-1][0] + arr[i][0]
    arr_sum[0][i] = arr_sum[0][i-1] + arr[0][i]

# 내부 채우기
for i in range(1, n):
    for j in range(1, n):
        arr_sum[i][j] = max(arr_sum[i-1][j], arr_sum[i][j-1]) + arr[i][j]

print(arr_sum[n-1][n-1])

2. 정수 사각형 최소 합

https://www.codetree.ai/missions/2/problems/minimum-sum-path-in-square?&utm_source=clipboard&utm_medium=text

N×N 행렬이 주어졌을 때, (1,N)에서 시작하여 왼쪽 혹은 밑으로만 이동하여 (N,1)로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자의 합을 최소로 하는 프로그램을 작성해보세요.

입력 형식
첫째 줄에는 N이 주어집니다.
두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.

1≤N≤100
1≤ 행렬에 주어지는 숫자 ≤1,000,000

출력 형식
가능한 최소 합을 출력합니다.

입출력 예제
예제1
입력:
3
5 2 1
1 9 1
1 8 9

출력:
10

내가 짠 코드

# 출발 (1, N) 도착 (N, 1)
# 왼쪽 혹은 아래로 이동

n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

sum_arr = [[0] * n for _ in range(n)]

sum_arr[0][n-1] = arr[0][n-1]

# 테두리 채우기 ((1, n) 부터 왼쪽으로)
for i in range(n-2, -1, -1):
    sum_arr[0][i] = sum_arr[0][i+1] + arr[0][i]

# 테두리 채우기 ((1,n) 에서 아래쪽으로)
for i in range(1, n):
    sum_arr[i][n-1] = sum_arr[i-1][n-1] + arr[i][n-1]

# 가운데 채우기 (위랑 오른쪽에서 최솟값 가져와서 더하기)
for i in range(1, n):
    for j in range(n-2, -1, -1):
        sum_arr[i][j] = min(sum_arr[i-1][j], sum_arr[i][j+1]) + arr[i][j]


print(sum_arr[n-1][0])

3. 정수 사각형 최솟값의 최대

https://www.codetree.ai/missions/2/problems/maximin-path-in-square?&utm_source=clipboard&utm_medium=text

N×N 행렬이 주어졌을 때, (1,1)에서 시작하여 오른쪽 혹은 밑으로만 이동하여 (N,N)으로 간다고 했을 때 거쳐간 위치에 적혀있는 숫자들 중 최솟값을 최대로 하는 프로그램을 작성해보세요.

입력 형식
첫째 줄에는 N이 주어집니다.
두 번째 줄 부터 N개의 줄에 각각 각 행에 해당하는 N개의 정수 값이 공백을 사이에 두고 주어집니다.

1≤N≤100
1≤ 행렬에 주어지는 숫자 ≤1,000,000

출력 형식
가능한 경로의 숫자들 중 최솟값의 최댓값을 출력합니다.

입출력 예제
예제1
입력:
3
5 2 3
3 2 1
1 2 4

출력:
2

내가 짠 코드
생각 못 한 부분 : min[i][j] 의 값은 <min[i-1][j] 와 min[i][j-1] 의 값 중 max 값>과 <현재 배열의 값(arr[i][j])> 중 min 값을 넣어야한다는 게 헷갈렸다.
-> 왜 이렇게 하는지 ? 오는 여러 동선 중에서 min 값의 max 를 취해야 한다. path1 과 path2 가 있을 때 path1의 min 값이 1이고 path2 의 min 값이 2 라면 2를 취해야한다는 점이다. 그런데 경로의 최소값이라는 점에서는 변함이 없으므로 현재값과 해당 값의 Min을 취해야한다.

MAX_N = 1000000
n = int(input())

arr = [list(map(int, input().split())) for _ in range(n)]

min_arr = [[MAX_N+1]*n for _ in range(n)]
min_arr[0][0] = arr[0][0]

# 테두리값 세팅
for i in range(1, n):
    min_arr[0][i] = min(min_arr[0][i-1], arr[0][i])
    min_arr[i][0] = min(min_arr[i-1][0], arr[i][0])


# 내부값 세팅
for i in range(1, n):
    for j in range(1, n):
        min_arr[i][j] = min(max(min_arr[i-1][j], min_arr[i][j-1]), arr[i][j])


print(min_arr[n-1][n-1])

조건에 맞게 선택적으로 전진하는 DP

https://www.codetree.ai/missions/2/problems/longest-increasing-subsequence/introduction

점프해서 가야한다(앞으로만 점프가 가능)는 조건이 있을 때 처음 위치에서 시작해서 종료 지점까지 최대 점프 횟수를 구해야한다. 앞으로만 점프가 가능하므로 문제를 "앞으로"만 확장할 수 있다.
이 때 가장 작은 문제는 처음 위치가 될 것이다.

문제를 확장해나가야 하는데 최종적으로 구하는 것을 처음 가정으로 삼으면 좋다. 그런식으로 계산을 해보면
i 번째 위치까지 최대 점프 횟수로 i+1 번째 위치까지의 최대 점프 횟수를 어떻게 도출해낼 수 있을지 먼저 생각해보면 좋다. (i 번째 위치까지 최대 점프 횟수 -> i+1 번째 위치까지의 최대 점프 횟수)

점화식을 세울 떄 예전에는 dp[i] = min(dp[i-1], dp[i-2]) 처럼 정형화된 점화식을 세웠었지만, 조건이 있을 땐 조건에 따라 유동적으로 세워야 한다.

그냥 i번째 위치까지의 최대 점프 횟수 / i번째 위치로 마지막으로 점프한 경우 중 최대 점프 횟수 <- 이렇게 나눌 수 있는데 이 두 개는 비슷하면서 다르다.
첫번째는 마지막 위치가 상관없는데 두번째는 정확히 i 번째로 끝나는 애들 중에서 최대 점프 횟수를 가지고 있다. 만약 첫번째로 문제를 정의한다면, 아래 같은 코드로 가져올텐데 문제가 생긴다. 만약 k 가 10이라면 i = 1~9 의 값을 가져오게 된다. 그런데 그냥 가져오면 dp[9] 에서 dp[10]으로 가져온다면(dp[9]+1 = dp[10]), dp[9]가 3이라면 3이라는 숫자가 만약 dp[10] 으로 갈 수 있는지 확인해야한다.

for i in range(1, k+1): #k+1 문제를 풀 때, 
	dp[i+1] = max(dp[k+1], dp[i])  + 1

아래처럼 배열이 주어졌을 때 10에서 12번째 1로는 넘어갈 수 있으나. 최대 점프 수를 담은 배열에선 이를 표현하기 어렵다.

10 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 4 4 4 4 4 4 5

따라서, 두번째 방법을 사용해서 정확히 i번째로 끝나는 애들 중에서 최대 점프 횟수를 저장해야한다.
그럼 i번째 위치로 마지막으로 점프한 경우 중 최대 점프 횟수를 기준으로 삼으면,

아래 코드와 같다. k로 올 수 있는 애를 다 확인하는 조건을 추가한 것이다.

 for i in range(1, k+1):
 	if(i + arr[i] >= k+1):
    	dp[k+1] = max(dp[k+1], dp[i]) + 1
 

1. 최대 증가 부분 수열

입력 형식
첫째 줄에는 N이 주어집니다.
두 번째 줄에는 N개의 숫자가 공백을 사이에 두고 주어집니다.
1≤N≤1,000
1≤ 수열의 원소 (M)≤10,000

출력 형식
최장 증가 부분 수열의 길이를 출력합니다.

진행하다 끊기고 또 진행하다 끊기는 DP

수열에서 점수가 최대가 되는 연속 부분 수열을 구하려면 어떻게 할까?
부분 문제를 정의해보자.
각 부분 문제를 "해당 위치까지의 배열에서 최대 연속 부분 수열의 합" 으로 정해보자.
예를 들어, 주어진 수열이 [-2, 1, -3, 4, -1, 2, 1, -5, 4]일 때, 각 위치에서의 부분 문제는 다음과 같다.

• 첫 번째 요소(-2)까지의 최대 합: 부분 수열은 [-2]이며, 최대 합은 -2
• 두 번째 요소(1)까지의 최대 합: 두 가지 선택지가 있다 : 새로운 부분 수열을 시작해서 [1]로 하거나 기존의 부분 수열에 이어서 [-2, 1]로 하는 것. 여기서는 [1]이 더 큰 합을 가지므로, 최대 합은 1이다.
• 세 번째 요소(-3)까지의 최대 합: [1, -3] 또는 [-3]을 선택할 수 있다. 최대 합은 -2이다.
• 네 번째 요소(4)까지의 최대 합: [1, -3, 4], [4] 를 선택할 수 있는데 [4]가 가장 큰 합을 가진다. 최대합은 4이다.

이런 식으로 계속해서 구할 수 있다. 이런 알고리즘을 카데인 알고리즘(Kadane's Algorithm)라고 한다.

1. 연속 부분 합의 최댓값 구하기

https://www.codetree.ai/missions/2/problems/max-of-partial-sum?&utm_source=clipboard&utm_medium=text

입력 형식
첫 번째 줄에는 원소의 개수 n이 주어지고, 두 번째 줄에는 n개의 정수가 공백을 사이에 두고 주어집니다.
−1,000≤정수≤1,000
1≤n≤100,000

출력 형식
연속한 부분 수열의 원소들의 합이 최대가 될 때의 값을 출력합니다.

입출력 예제
예제1
입력:
7
4 -1 2 -19 3 6 9

출력:
18

내가 짠 코드

n = int(input())

arr = list(map(int, input().split()))

dp =  [0] * n
dp[0] = arr[0]

for i in range(1, n):
    dp[i] = max(dp[i-1]+arr[i], arr[i])

dp.sort()
print(dp[n-1])

연속적이지만 직전 상황에 영향을 받는 DP

연속적이지만 직전 상황에 영향을 받는 DP 는 예를 들어 이런 문제가 있을 수 있다. 여러 개의 집이 일렬로 배치되어 있으며, 각 집은 특정 색으로만 칠할 수 있다. 인접한 두 집은 같은 색으로 칠할 수 없을 때, 최소 비용으로 모든 집을 칠하는 방법을 찾는 문제가 있다고 하자.

집의 수를 n 이라고 하고, 각 집을 칠하는 비용이 색깔마다 다르다고 가정한다.이 정보를 나타내기 위해
𝑛×𝑘 행렬이 주어지며, 여기서 𝑘는 사용할 수 있는 색상의 수이다.행렬의 cost[i][j]는 집 i를 색 J 로 색칠하는 데 드는 비용이다.
우선 dp 테이블(작은 문제)을 정의한다. 여기서는 집 i 를 색상 j 로 칠할 떄 0에서 i 까지의 최소 비용으로 잡을 수 있을 것이다.
그리고 초기값을 세팅한다. 첫 번째 집을 칠하는 비용은 초기값은 dp[0][j] = cost[0][j] 이다.
이제 점화식을 계산한다. 두 번째 집부터 n번째 집까지, 모든 색상 j에 대해 최소 비용을 계산한다고 하면, dp[i][j]=cost[i][j]+min(dp[i−1][k]) 이다. 여기서 k != j

이것은 이는 집 i 를 색상 J 로 칠하는데 드는 비용 cost[i][j] 에 이전 집 i-1 을 색상 j 이외의 색으로 칠한 최소 비용을 더하는 방식이다.
마지막 집까지 칠했을 때의 최소 비용은
min(dp[n−1][j]) 이 된다.

1. 적절한 옷 고르기

40XP
https://www.codetree.ai/missions/2/problems/select-proper-clothes?&utm_source=clipboard&utm_medium=text

입력 형식
첫째 줄에는 N과 M이 공백을 사이에 두고 주어집니다.
두 번째 줄 부터는 N개의 줄에 걸쳐 각각의 옷의 정보 (s,e,v)가 공백을 사이에 두고 주어집니다. s는 해당 옷을 입기 시작할 수 있는 날짜, e는 해당 옷을 입을 수 있는 마지막 날짜, v는 그 옷의 화려함 입니다. (1≤s≤e≤M,1≤v≤1,000)
각 날짜마다 최소 한 개의 옷은 입을 수 있도록 입력이 주어진다고 가정해도 좋습니다.
1≤N≤200
2≤M≤200

출력 형식
최대 만족도를 출력합니다.

입출력 예제
예제1
입력:
2 3
2 3 10
1 2 5

출력:
5

내가 짠 코드