알고리즘 문제 풀이 - DP(1)
지난주에 그래프 탐색 문제에 대해서 리뷰를 해봤는데 이번에는 DP, 동적 프로그래밍 문제에 대한 리뷰를 진행해보겠습니다.
Dynamic Programming(DP)
먼저 동적 프로그래밍 문제를 푸는 기본 전략은
문제를 부분 문제로 나누고 부분 문제의 해를 이용해서 원래의 해를 찾는 것입니다. 말로만 하면 어려운 것 같아서 예시를 들어보겠습니다.
피보나치 수열
1,1,2,3,5,8,13,21,34…
규칙이 좀 보이시나요?
첫번째 항과 두번째항은 1로 시작하고 3번째 항부터는 n-1, n-2번째 항을 더한 것이 n번째 항이 되는 규칙의 수열입니다.
만약 7번째 항을 구하려면 어떻게 해야할까요?
5,6 번째 항을 알아야겠죠?
그렇다면 5,6번항은 또 어떻게 알 수 있을까요?
5번째 항은 3,4번째 6번째 항은 4,5번째 항을 알아야 할 것입니다.
이런식으로 n번째의 해를 구하기 위해서 n-1, n-2 번째 해를 이용할 수 있습니다. 이 때 순차적으로 n(n>2)번째 항을 구하는 것을 Bottom-Up 방식이라고 하고 이렇게 순차적으로 n번째 해를 저장해나가는 것을 Tabulation이라고 합니다.
반대로 바로 n번째 항을 구하려고 시도를 하고 이 시도 안에서 n-1번째 항과 n-2번째 항을 구하려는 접근을 Top-Down 방식이라고 하고 이 때 구해진 해를 기록하는 것을 memoization이라고 합니다.
저는 주로 Bottom-Up 방식으로 접근하여 DP 문제를 풀고 뒤의 풀이에서도 Bottom-Up방식을 이용한 풀이를 보여드리겠습니다!
개미전사
나동빈님의 이코테 강의에서 풀어주는 기본 문제입니다.
문제 풀이
식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 경우를 생각해봅시다. 그냥 직관적으로 생각했을 때 어떤 식량 창고에 식량의 최대 개수인 1000이 있다면 해당 식량을 선택해야할 것 입니다. 하지만 만약 해당 식량 창고의 이전창고를 선택했다면 현재 식량창고를 털 수가 없겠죠?
따라서 바로 앞 식량창고의 선택 여부가 중요한 부분입니다. 만약 앞의 식량 창고가 현재 선택한 식량 창고보다 많은 가치를 가지고 있다면 앞의 식량 창고를 선택하고 현재 식량 창고를 선택하지 않는 것이 옳은 선택일 것입니다.
예시 접근
[3,5,3,100,1000]
위 처럼 식량 창고 정보가 주어졌을 때 Bottom-Up 방식으로 접근하여 풀어보겠습니다.
N=1 경우는 한개의 식량창고만 있으니 무조건 선택하는 것이 이득입니다.
[3] -> [3]
dp[1] = 3
N=2 경우는 둘 중 더 큰 것을 선택하면 됩니다.
[3,5] -> [1,5]
dp[2] = 5
N=3 경우는 한번 생각을 해볼 필요가 있습니다.
이전 N=2인 경우의 해를 선택한다면 새로 추가된 식량 창고를 선택할 수 없고
전전 N=1인 경우의 해를 선택한다면 새로 추가된 식량 창고를 선택할 수 있습니다.
이를 한번 비교해봐야 할 것 같습니다.
N=1 선택 -> dp[1] + value[3] = 6
N=2 선택 -> dp[2] = 5
두번째를 선택하지 않는 경우가 더 많은 식량을 털 수 있네요
[3,5,3] -> [3,5,3]
dp[3] = 6
마지막으로 한번만 더 해보겠습니다.
N=3 경우의 해를 선택한다면
dp[3] = 6
N=2 경우의 해를 선택한다면
dp[2] + value[4] = 105
이 경우에도 n-2번째의 해를 선택하는 것이 더 많은 식량을 얻을 수 있네요 [3,5,3,100] -> [3,5,3,100]
이러면 어느정도 규칙성이 보인 것 같습니다. n-1의 해와 n-2의 해 + 현재 식량 창고의 가치를 비교해서 더 큰 것이 n번째의 해가 될 수 있겠네요.
1
dp[n] = max(dp[n-1], dp[n-2] + value[n]) # n번째의 부분 해
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
input = sys.stdin.readline
N = int(input().rstrip())
k_list = list(map(int, input().rstrip().split()))
dp = [0] * N
# 1,2번째 항은 직접 구하기
dp[0] = k_list[0]
dp[1] = k_list[0] if k_list[0] > k_list[1] else k_list[1]
# n > 2 부터는 점화식
for i in range(2,N):
if dp[i-2] + k_list[i] > dp[i-1]:
dp[i] = dp[i-2] + k_list[i]
else:
dp[i] = dp[i-1]
print(dp[N-1])
현재 추가된 식량 창고를 선택할지 말지에 따라서 가져오는 해가 달라지는 문제였습니다.
인사이트
- 문제를 잘 읽고 현재 선택이 어떤 영향을 미치는지를 잘 생각해보자
스티커
이 문제도 개미전사 문제와 유사한 문제입니다.
현재의 선택에 따라서 가져올 수 있는 해가 달라지는 문제입니다.
문제풀이
개미전사는 1차원 공간으로 현재의 선택에 따라서 x-1의 해나 x-2를 가져오는 것이었습니다.
하지만 이 스티커 문제는 세로의 길이가 2로 고정된 2차원 공간이고 선택한 스티커와 인접한(상,하,좌,우) 스티커는 선택할 수 없습니다.
따라서 N이 증가함에 따라서 선택지가 좀 더 많아지게 됩니다. 만약 추가된 1행의 스티커를 선택한다면 n-1번째의 1행이 포함된 해는 가져올 수 없습니다. 반대로 2행의 스티커를 선택한다면 n-1번째의 2행이 포함된 해는 가져올 수 없겠죠
그렇다면 n-1번째의 인접하지 않는 스티커를 선택한 해를 가져와서 현재 선택한 스티커의 값만 더하면 되는 것일까요?🤔
여기서 다시 잘 생각해볼 필요가 있습니다.
예를 들어
| 1 | 2 | 3 |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 2 | 1 |
이렇게 스티커가 있을 때
3열의 스티커 중 1행의 스티커를 선택 했다면
| 1 | 2 | 3 |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 2 | 1 |
이렇게 2열 2행의 스티커를 선택한 최댓값과 현재 선택한 스티커 값을 더해 4를 얻을 수 있습니다.
하지만 이 방법 말고도 2열의 스티커를 아예 선택하지 않는 방법이 있습니다.
2열의 스티커 역시 1열의 스티커의 선택에 영향을 주기 때문에 아예 선택하지 않음으로서 n-2번째의 해를 이용할 수 있습니다.
| 1 | 2 | 3 |
|---|---|---|
| 1 | 1 | 1 |
| 4 | 2 | 1 |
1 + 4 = 5로 이 경우가 더 큰 값이 되는군요!
만약 n-2의 해가 n-1에서 선택한 해와 겹치지 않는 스티커라면 n-1의 해에 포함되어 있기 때문에,
n-2열에서 n-1에서 선택한 스티커와 인접한 스티커를 사용하는 경우만 고려하면 됩니다. (위와 같은 경우)
n번째에서 어떤 스티커를 고르느냐에 따라 n-1,n-2 행에서 선택했던 스티커가 달라지기 때문에 tabulation 역시 2차원으로 저장해야합니다.(스티커를 골랐을 때의 최댓값을 모두 저장)
그러면 점화식은 이렇게 세울 수 있겠죠?
1
2
dp[n][0] = value[n][0] + max(dp[n-1][1], dp[n-2][1])
dp[n][1] = value[n][1] + max(dp[n-1][0], dp[n-2][0])
이렇게 n열에서 스티커를 선택했을 때의 두 가지 경우를 구한 뒤
두 값 중 더 큰 값이 해가 되는 것입니다!
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
input = sys.stdin.readline
t = int(input().rstrip())
for _ in range(t):
n = int(input().rstrip())
sticker = [ [ 0 for _ in range(n) ] for _ in range(2)]
dp = [ [ 0 for _ in range(n)] for _ in range(2) ]
sticker[0] = list(map(int, input().rstrip().split()))
sticker[1] = list(map(int, input().rstrip().split()))
# 스티커
if n == 1:
print(max(sticker[0][0], sticker[1][0]))
continue
# 초기값 설정 (n > 2)
dp[0][0] = sticker[0][0]
dp[1][0] = sticker[1][0]
dp[0][1] = dp[1][0] + sticker[0][1]
dp[1][1] = dp[0][0] + sticker[1][1]
# 점화식
# n-1전 다른 세로 칸 혹은 n-2의 같은 세로 칸(현재 스티커를 붙일 수 있는 경우) dp값 중 더 큰 것을 선택하여 현재 스티커 값과 더한다.
for i in range(2,n):
dp[0][i] = sticker[0][i] + max(dp[1][i-1], dp[1][i-2])
dp[1][i] = sticker[1][i] + max(dp[0][i-1], dp[0][i-2])
print(max(dp[0][n-1], dp[1][n-1]))
인사이트
- dp 테이블에 N에 따른 해만 1차원적으로 저장하는 것이 아니다.
- 현재 선택에 따라서 해가 아닌 다른 최적값이 필요할 수 있다. -> 해만 저장하는 것이 아니다.
다음 글에서는 DP 문제 중에서도 longest increasing subsequence(LIS)유형의 문제에 대해서 리뷰를 진행해보겠습니다!