알고리즘 문제 풀이 - DP(3)
서론
안녕하세요! 최근에도 코딩테스트 대비를 위해서 지속적으로 문제들을 풀고 있는데요, 요즘은 기출문제를 풀기 위해서 프로그래머스에서 카카오 기출문제들을 풀고 있습니다.
그런데 아직 제대로 복기하지 못한 백준 문제들이 많아서 이번 글에서 리뷰해보며 복기해보려고 합니다.
이번에 리뷰할 문제들은 2차원으로 부분 문제의 해를 저장해야하는 형식입니다.
따라서 어떤 것을 기준으로 부분 문제로 나눌지를 생각하는 것이 중요하니, 이에 집중하면서 리뷰를 봐주시면 좋을 것 같습니다.
문제 리뷰
평범한 배낭
평범한 배낭 아주 대표적인 2차원 DP 문제입니다.
문제 접근
Bottom-Up 방식으로 접근하여 물건이 1개 있을 때를 생각해보겠습니다. 만약 물건이 배낭의 무게를 넘지 않는다면 물건의 가치가 해가 되고, 만약 넘는다면 0이 해일 것입니다.
다음은 물건이 2개 있을 때를 생각해보겠습니다.
만약 이전에 물건을 1개 넣은것에 추가적으로 넣을 수 있다면 넣는 것이 당연히 더 높은 가치를 가질 것 입니다(음수의 가치는 없으므로)
그런데, 만약 무게가 부족해 둘 다 넣을 수가 없다면?
둘 중에 1개를 선택해야하는 상황이 올 것 입니다.
물건을 비교해서 가치가 높은 물건을 넣어야 합니다.
만약 물건이 3개가 있다면?
모든 물건을 비교해서 가치가 높은 순부터 넣으면 될까요?
아니면 물건을 많이 담기 위해서 무게가 낮은 순부터 넣으면 될까요?
만약 무게나 가치가 일정하다면 정렬한 뒤 위처럼 그리디한 방법으로 선택하면 되겠지만
물건의 무게와 가치는 랜덤하기 때문에 다른 방법을 생각해 봐야겠습니다.
DP 문제를 풀 때는 항상 ‘이전에 구해놓은 부분 문제의 해’를 이용하는 것이 중요합니다.
만약 새로운 물건이 추가됐을 때 이 물건을 선택할지 말지를 판단할 때 이를 잘 이용해봅시다.🤔
가정을 한번 해보겠습니다.
만약 새로운 물건의 가치가 100조 정도 되는 매우 큰 숫자라고 생각해보겠습니다. 배낭에 넣을 수 있는 물건이라면 다른 물건보다도 이 물건을 우선하여 반드시 넣어야 할 것입니다.
그렇다면 이 새로운 물건을 넣고 나서 나머지 무게는 어떤 물건으로 채우는게 좋을까요? 방법은 잘 모르겠습니다만, 가장 가치가 높도록 채워야겠죠?
여기가 바로 이 문제를 부분 문제로 나눌 수 있는 포인트 입니다!
위의 예시에선 물건의 가치가 매우 높아 새로운 물건을 선택했지만 항상 선택하는 것이 옳은 선택은 아니겠죠?
만약 같은 무게더라도 전에 구했던 무게 당 가장 높은 가치가 더 높다면 새로운 물건을 선택할 이유가 없습니다.
그러면 무게와 물건을 기준으로 부분 문제를 해결하며 2차원 배열에 각 해를 저장해가면 될 것 같습니다. 어느정도 윤곽이 잡힌 것 같으니 점화식을 생각해 보겠습니다.🤗
현재 물건을 넣고 남은 무게에 대한 최대 가치를 구해야 하니
현재 물건의 무게만큼 뺀 것이 부분 문제가 될 것입니다.
dp[n][m] = max(dp[n-1][m], 새로운 물건의 가치 + dp[n-1][m-새로운 물건의 무게]) // n:물건 , m:무게
이 점화식은 새로운 물건의 무게가 m보다 작을때만 적용하고 (물건을 넣을 수 있을 때) 만약 무게가 m 보다 클 때는 추가되도 넣을 수가 없으니 물건을 추가하기 이전과 같은 해를 가진다고 봐도 됩니다.
주의할 점
물건의 개수는 1개이기 때문에 물건을 중복해서 넣을 수 없음에 주의해야 합니다. 따라서 남은 물건의 최대 가치를 반드시 ‘현재 물건이 추가되기 직전’에서 가져와야 합니다.
따라서 dp[n]이 아닌 dp[n-1]에서 남은 무게의 최대 가치를 가져오는 것입니다. 만약 dp[n]에서 가져온다면 새로운 물건의 무게의 배수마다 이미 물건이 추가된 해에 중복해서 물건을 추가하여 계산하게 되어 잘못된 계산을 하게 됩니다.
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
input = sys.stdin.readline
N,K = map(int, input().rstrip().split())
T = [ list(map(int, input().rstrip().split())) for _ in range(N) ]
dp = [ [0 for _ in range(K+1)] for _ in range(N)]
for i in range(1,K+1):
if i >= T[0][0]:
dp[0][i] = T[0][1]
for i in range(1,N):
w,v = T[i]
# 이전 부분해 가져오기
for j in range(1,K+1):
# 새로 추가된 물건을 선택할 수 없을 때는 이전과 같음
if j < w:
dp[i][j] = dp[i-1][j]
# 새로 추가한 물건을 선택하고 나머지 무게를 이전 최댓값으로 채운 것이 더 크다면 최대값 갱신
else:
dp[i][j] = max(dp[i-1][j], v+dp[i-1][j-w])
print(dp[N-1][K])
인사이트
- DP문제는 시뮬레이션을 돌려보며 부분 문제 구조를 찾자
- 부분 문제의 해를 가져올 때, 명확하게 어떤 경우의 해를 가져올 지 잘 생각하자
동전 2
동전 2
동전 문제도 유명한 DP 문제 중 하나입니다.
이 동전 문제는 문제의 조건에 따라서 그리디 문제가 되기도 하는데요😳
이 문제의 경우에는 동전의 가치가 배수 관계라는 조건이 없기 때문에 DP유형에 해당합니다.
문제 풀이
언뜻보면 가장 가치가 높은 동전을 우선적으로 선택하면 될 것처럼 보이기도 하지만 그렇지 않습니다.
예를들어,
10원을 만들어야 하는데 동전이 8원, 5원 1원이 있을 때 높은 가치를 우선적으로 선택한다면
1(8원의 개수) + 2(1원의 개수) = 3 이지만 사실 5원 동전 2개 사용하는 것이 더 적은 개수로 10을 만들 수 있습니다.
그렇다면 이 문제도 DP 풀이 방법으로 풀어야 하는데(조건에 따라 완전탐색, BFS 등으로 풀 수도 있습니다.)
혹시 어떻게 부분 문제로 나눠야 할 지 감이 오셨나요?
먼저 동전 종류에 따라서 부분 문제를 나눌 수 있을 것 같고
만약 현재 동전을 선택하고 채워야 하는 남은 가치를 또 부분 문제로 나눌 수 있을 것 같습니다.
생각해보면 배낭 문제와 유사한 기준으로 나눴다고 볼 수 있을 것 같습니다. (동전 == 물건, 가치 == 무게)
이번에도 점화식을 생각해보겠습니다.
새로운 동전을 사용하고 나머지 부분을 최소 동전 개수로 만든 것과 동전이 추가되기 전에 현재 가치의 최소 동전 개수를 비교해서 더 작은 것을 선택하면 될 것 같습니다
dp[n][m] = max(dp[n-1][m], 1 + dp[n][m-현재 동전의 가치] ) // n:동전 m:가치
이 점화식 역시 현재 만드려는 가치인 m이 동전의 가치 보다 크거나 같을 때 사용을 할 수 있겠죠?
그리고 이번에 남은 가치를 구하는 부분을 보면 dp[n]인데 배낭문제와는 다르게
추가된 동전은 여러개를 사용할 수도 있기 때문에 현재 동전이 추가된 상황의 해를 가져올 수 있어서
n-1이 아닌 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
n,k = map(int,input().rstrip().split())
coins = []
for i in range(n):
coin = int(input().rstrip())
if coin <= 10000:
coins.append(coin)
else:
n = n-1
if not coins:
print(-1)
exit()
dp = [ [ float('inf') for _ in range(k+1)] for _ in range(n)]
for i in range(n):
for j in range(1,k+1):
if coins[i] > j:
dp[i][j] = dp[i-1][j]
elif coins[i] == j:
dp[i][j] = 1
elif coins[i] < j:
dp[i][j] = min(dp[i-1][j], dp[i][coins[i]] + dp[i][j-coins[i]])
if dp[n-1][k] == float('inf'):
print(-1)
exit()
print(dp[n-1][k])
촤적화
그런데 이 문제를 풀고나서 다른 사람들의 사용 메모리와 시간을 보니 저보다 더 빠른 것들이 있어 코드를 살펴보고 더 최적화할 수 있음을 알았습니다.
저는 2차원 배열을 사용했지만 잘 생각해보면 1차원 배열로도 가능합니다.
m이 추가된 동전의 가치보다 작을 때는 이전과 같기 때문에 그대로 두고
m이 동전의 가치와 같을 때는 1
m이 더 클 때는 점화식을 적용하면 됩니다.
이렇게 최적화가 가능한 이유는 동전이 추가되기 직전과 추가된 경우의 해만 이용하기 떄문입니다
모든 것을 저장하기 보다는 필요한 것만 최소한으로 저장하는 방법으로 공간복잡도를 줄일 수 있다는 사실을 알았습니다!
아래는 최적화 이후의 코드입니다.
구현 코드(최적화 이후)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n,k = map(int,input().rstrip().split())
coins = []
for i in range(n):
coin = int(input().rstrip())
if coin <= 10000:
coins.append(coin)
else:
n = n-1
if not coins:
print(-1)
exit()
dp = [ float('inf') for _ in range(k+1)]
for i in range(n):
for j in range(coins[i],k+1):
if coins[i] == j:
dp[j] = 1
elif coins[i] < j:
dp[j] = min(dp[j], 1 + dp[j-coins[i]])
if dp[k] == float('inf'):
print(-1)
exit()
print(dp[k])
인사이트
- 재사용하는 부분 문제의 해가 고정되어 있다면(ex. n-1번째 부분문제의 해) 배열을 재활용하여 공간복잡도를 줄일 수 있다.
LCS
LCS 공통 최장 부분 수열 문제입니다.
개인적으로 배낭 문제보다 점화식을 찾는 것이 더 까다로운 문제라고 생각합니다.
사실 이 문제를 저번 포스팅인 LIS 유형에 넣을까 고민하다
2차원 DP 유형에 넣는 것이 더 일관성이 있을 것 같아서 여기서 리뷰를 하기로 했습니다.
문제 풀이
이 문제에서는 어떻게 부분 문제 구조로 나눌 수 있을 지를 생각해봅시다.
1개의 수열에서 특정 조건을 만족하는 지를 구하기 위해서는
추가되는 항이 원래 수열에 붙을 수 있는지를 판단하고 이전의 부분 문제의 해를 이용하여 구할 수 있습니다.
그런데 지금 상황은 1개의 수열에서 특정 조건을 갖는 수열을 찾는 것이 아닌
2개의 수열에서 특정 조건을 만족하는 공통수열을 찾는 것이죠?
그렇다면 각 수열마다 부분 문제로 나누어 구해야 합니다.
즉, 2개의 각 수열이 부분 문제로 나뉜 경우를 모두 고려해야 하니 2차원 DP입니다.
그리고 수열 문제를 풀 때 중요한 포인트는
뒤에 추가된 항이 앞의 모든 수열에 추가될 수 있다는 것입니다.
이 말은 만약 수열 1에 항이 새로 추가되면
직전의 LCS에 붙을 수 있는지만 판단하는 것이 아니기 때문에
수열 2에 각 항마다 비교를 하며
만약 같다면 수열1에 항이 추가되기 이전의 해에 +1을 해주면 됩니다.(이전 LCS에 추가됐다는 의미)
그런데 사실, 이는 틀렸습니다.😝
비교하는 항이 같다고 해서 무조건 +1을 한다면
이미 구한 공통 수열에 중복해서 항이 추가가 될 수 있습니다.
예를들어, ‘AAA와 ‘A’ 두 수열이 있을 때
최장 길이 수열의 길이를 3으로 잘못 계산할 수 있습니다.
따라서 구하는 것이 공통 수열의 길이 라는 것을 잘 생각해서
두 수열에서 현재 비교하는 항이 추가 되기 이전의 해에 +1을 해야 합니다.
비교하는 항이 같지 않은 경우에는
수열1에 항이 추가되기 이전 값을 그대로 가져오거나,
이전의 수열에 추가된 항이 붙어 새로운 LCS를 만들 수도 있으므로 수열2에 항이 추가되기 이전 해를 가져옵니다. (둘 중 더 큰 것)
이를 점화식으로 표현해보겠습니다.
1
2
3
4
if 수열1의 n항 == 수열 2의 m항:
dp[n][m] = dp[n-1][m-1] + 1
else:
dp[n][m] = max(dp[n-1][m], [n][m-1])
이정도로 표현할 수 있을 것 같습니다!
구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
input = sys.stdin.readline
seq1 = list(input().rstrip())
seq2 = list(input().rstrip())
seq1.insert(0,0)
seq2.insert(0,0)
dp = [ [0 for _ in range(len(seq2)+1)] for _ in range(len(seq1)+1)]
max_len = 0
for i in range(1,len(seq1)):
for j in range(1,len(seq2)):
if seq1[i] == seq2[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
max_len = max(max_len, dp[i][j])
print(max_len)
인사이트
- 수열문제는 항이 추가될 때 조건에 맞는 모든 부분 수열을 고려해야 한다. -> 부분 문제 구조
- 두 수열이 있다면 경우의 수가 부분 수열 * 부분 수열 이기 때문에 2차원 DP로 접근하는 것이 좋다.