[python] 가장 긴 증가하는 부분 수열 시리즈
가장 긴 증가하는 부분 수열 (백준 11053번)
https://www.acmicpc.net/problem/11053
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
maxa = 0
for i in range(n):
maxt = 0
for j in range(i):
if a[i] > a[j]:
maxt = max(maxt, dp[j])
dp[i] = maxt + 1
maxa = max(maxa, dp[i])
print(maxa)dp[i] : 0부터 i까지 i를 포함하는 가장 길게 증가하는 수열의 길이
앞의 계산을 뒤의 계산에서 활용하기 위해서 마지막 요소를 포함시켜 점화식을 정의하는 방식이다. dp에서 자주 보이는 방식이다.
점화식 : dp[i] = max(dp[k]) + 1 (dp[i]보다 dp[k]가 작은 0과 i-1 사이의 k에 대해...)
(정답)
가장 긴 증가하는 부분 수열 2 (백준 12015번)
https://www.acmicpc.net/problem/12015
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1
def binarysearch(l, r, now):
while l < r:
mid = (l + r) // 2
if b[mid] < now:
l = mid + 1
else:
r = mid
return l
for i in range(2, n + 1):
if b[maxl] < a[i]:
maxl += 1
b[maxl] = a[i]
dp[i] = maxl
else:
idx = binarysearch(1, maxl, a[i])
b[idx] = a[i]
dp[i] = idx
print(maxl)dp 배열과 점화식은 위와 동일하다. 그런데 위의 풀이대로 풀면 시간 초과가 나온다. (오답)
시간을 줄이기 위해 dp 배열을 채울 때 순차 탐색이 아닌 이분 탐색을 활용하여야 한다.
이분 탐색은 정렬된 데이터에만 적용할 수 있으므로 필요한 데이터들을 추가 공간 b에 오름차순 정렬이 되도록 채워가며 b에서 이분 탐색을 해주는 것이다. (정답)
가장 긴 증가하는 부분 수열 3 (백준 12738번)
https://www.acmicpc.net/problem/12738
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1
def binarysearch(l, r, now):
while l < r:
mid = (l + r) // 2
if b[mid] < now:
l = mid + 1
else:
r = mid
return l
for i in range(2, n + 1):
if b[maxl] < a[i]:
maxl += 1
b[maxl] = a[i]
dp[i] = maxl
else:
idx = binarysearch(1, maxl, a[i])
b[idx] = a[i]
dp[i] = idx
print(maxl)두번째 문제와 동일하게 풀면 되었다. (정답)
가장 긴 증가하는 부분 수열 4 (백준 14002번)
https://www.acmicpc.net/problem/14002
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
maxa = 0
for i in range(1, n + 1):
maxt = 0
for j in range(i):
if a[i] > a[j]:
maxt = max(maxt, dp[j])
dp[i] = maxt + 1
maxa = max(maxa, dp[i])
idx = maxa
ans = [0 for _ in range(idx + 1)]
for i in range(n, 0, -1):
if dp[i] == idx:
ans[idx] = a[i]
idx -= 1
print(maxa)
for i in range(1, maxa + 1):
print(ans[i], end = ' ')dp 배열과 점화식은 위와 동일하다. 그런데 이번에는 가장 긴 증가하는 부분 수열의 길이뿐만 아니라 해당 수열까지 출력을 해야 한다.
나머지 풀이(dp 정의, dp 채우기 등)는 동일한데 마지막에 dp 배열을 역순으로 하나씩 탐색하며 저장한 뒤 출력하면 된다. (정답)
가장 긴 증가하는 부분 수열 5 (백준 14003번)
https://www.acmicpc.net/problem/14003
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1
def binarysearch(l, r, now):
while l < r:
mid = (l + r) // 2
if b[mid] < now:
l = mid + 1
else:
r = mid
return l
for i in range(2, n + 1):
if b[maxl] < a[i]:
maxl += 1
b[maxl] = a[i]
dp[i] = maxl
else:
idx = binarysearch(1, maxl, a[i])
b[idx] = a[i]
dp[i] = idx
idx = maxl
ans = [0 for _ in range(idx + 1)]
for i in range(n, 0, -1):
if dp[i] == idx:
ans[idx] = a[i]
idx -= 1
print(maxl)
for i in range(1, maxl + 1):
print(ans[i], end = ' ')세번째 문제와 네번째 문제를 합치기만 하면 된다.
즉, dp 배열을 채울 때는 이분 탐색을 이용해서 채우고, 마지막에 출력할 때는 dp 배열을 거꾸로 탐색하며 정답 수열을 구하는 것이다. (정답)