알고리즘 문제 풀이 - DP(2)
서론
안녕하세요! 최근 2주동안 DP 문제를 차곡차곡 풀면서 DP에 대한 숙련도를 높이고 있습니다!
이번 주제는 DP 문제 중 대표적인 문제로 Longest Increasing Subsequence(LIS)유형의 문제들을 리뷰하겠습니다.
개인적으로 이 유형은 처음 풀이법을 떠올리지 못해서 큰 벽을 마주한 느낌이었습니다..🥲
하지만 비슷한 유형의 문제를 반복해서 풀다보니 감을 잡을 수 있었고, 몇 가지 저의 문제점을 찾을 수 있었습니다.
그럼 바로 문제 리뷰 시작하겠습니다!
문제 리뷰
가장 큰 증가하는 부분 수열
사실 가장 긴 부분 수열을 찾는 LIS의 정석 문제를 풀기전에 이 문제를 먼저 접했습니다. 그래서인지 풀이가 잘 생각이 나지 않더군요..
문제 접근 🤔
일단 먼저 해결한 부분 문제의 답을 통해서 이 다음의 문제를 해결 하기위해 원소가 추가된다면 직전에 가장 큰 합이었던 수열에 더할지 말지를 생각해보았습니다.
만약 더 큰 값이 온다면 해당 부분수열에 더해주면 그것이 현재 수열의 가장 큰 증가하는 부분 수열이 됩니다.
문제는 더 작은 값이 올 때 입니다.
‘처음에는 더 작은 값이면 무시하면 되겠지?’라 생각했었으나..
더 작은 값이라도 다른 수열에 더해져 기존 답보다 더 큰 증가하는 부분 수열이 될 수도 있는 것입니다.
문제 설명의 예시에서도 이와 같은 상황이 주어지는데
A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
이렇게 수열이 주어졌을 때
5번째 원소가 추가된 경우를 보겠습니다.
5번째 원소가 추가되기 직전에 가장 큰 수열은
{1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
이렇게 {1,100} 이고 합은 101입니다.
하지만 추가된 이후에는
{1, 100, 2, 50, 60, 3, 5, 6, 7, 8}
이렇게 {1,2,50,60} 으로 합이 113으로 합이 더 큰 부분 수열이 됩니다.
저는 여기서 특별한 아이디어를 떠올리지 못했습니다🥹
해결방법 🔍
사실 아이디어랄게 없이 그냥 앞선 모든 수열들에 원소를 추가하여 직전의 답인 수열과 비교해주면 됩니다.
여기서 제가 놓친 것은 각 원소가 추가될 때 마다 최적의 해가 저장되고 이를 유연하게 이용해야 하는데 저는 직전의 답이 되는 수열만 이용하려고 하는 고정적인 사고에서 벗어나지 못했던 것 같습니다.
여기서 또 중요한 부분이 있는데, 그건 문제에서 수열의 크기가 1000이하로 주어진다는 것입니다. 1000이하로 주어졌기 때문에 모든 최대 합과 비교를 하더라도 시간복접도가 O(N²) 알고리즘이라도 연산 횟수가 100,000으로 충분히 작기 때문입니다!
구현 코드 🧑🏻💻
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys
input = sys.stdin.readline
# 이전의 정답에 고정되어 이와 점화식을 연게 시키는거에 시야가 좁아지지 말자
# 원소가 추가 되었을 때 그 원소가 지금 까지 구한 부분 수열(부분 문제)에 추가될 수 있는지가 핵심
N = int(input().rstrip())
A = list(map(int, input().rstrip().split()))
dp = [0] * N
for i in range(N):
dp[i] = A[i]
max_sum = dp[0]
for i in range(1,N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[j] + A[i],dp[i])
max_sum = max(max_sum,dp[i])
print(max_sum)
인사이트 👀
- 문제의 조건 역시 알고리즘을 떠올리는 힌트가 될 수 있다.
- Bottom-Up 방식을 사용하여 DP를 풀 때는 앞서 구한 최적해를 모두 유연하게 이용하자.
가장 긴 증가하는 부분 수열
이 문제가 LIS의 정석 문제입니다! 말 그대로 가장 긴 증가하는 부분 수열의 길이를 구하는 문제죠
앞에서 푼 합이 큰 증가하는 부분 수열을 구하는 것과 크게 다르지 않습니다.
문제 풀이 ⭐️
증가하는 부분 수열이기에 추가된 원소의 크기를 비교해서
이전에 구한 각 부분 문제의 마지막 원소보다 크다면 최대 길이에 +1을 하고
만약 직전의 최대 길이보다 크다면 해당 길이를 선택하는 방법입니다.
합을 비교하는 것이 아니라 길이를 비교하기 때문에 길이를 저장하는 것이 이전 문제와의 차이점입니다. 거의 똑같죠?
가장 긴 감소하는 부분 수열이나 등 여러 변형 문제가 있는데 이런 문제들도 비슷하지만 조건을 조금만 다르게 한다면 모두 풀 수 있습니다.😀
구현 코드 🧑🏻💻
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
input = sys.stdin.readline
N = int(input().rstrip())
A = list(map(int, input().rstrip().split()))
dp = [1] * N
max_length = 1
for i in range(1,N):
for j in range(i):
# 더 큰 숫자가 오면 수열에 추가 및 길이 계산
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j]+1)
max_length = max(max_length, dp[i])
print(max_length)
인사이트 👀
- LIS 변형 문제는 부분 수열의 조건, 구하는 것이 길이 or 합 인지에 따라 조건을 조금씩만 다르게 하면 해결할 수 있다.
더 어려운 난이도로 가장 긴 증가하는 부분 수열 2,3,4,5도 있는데
이 문제들은 원소의 범위가 크게 증가하거나 수열을 직접 구하는 것으로 난이도에 변화를 줬습니다.
이 문제들은 나중에 다뤄보도록 하겠습니다!
읽어주셔서 감사합니다😊