최장 증가 부분 수열(LIS, Longest Increasing Subsequence)이란 말 그대로 원소가 n개인 배열의 일부 원소를 골라내서 만든 수열 중 증가 수열이면서 가장 긴 것을 의미한다. (각 원소가 연속일 필요는 없다)
LIS와 관련된 백준 문제는 매우 많고, 다양한데 14003번 문제를 보면서 nlogn의 시간 복잡도를 가지는 LIS의 길이와 LIS 원본을 추출해내는 작업을 하는 코드를 만들어 볼 것이다.
https://www.acmicpc.net/problem/14003
가장 간단하게 LIS의 길이가 얼마인지 풀기 위해선 DP를 이용해 n ** 2의 완전탐색을 하면 된다.
dp = [1 for _ in range(N)] #이 dp는 수열의 길이를 담음, 수열의 길이는 최소가 1이므로 초기값을 1로 설정
for i in range(1, N):
for j in range(i):#수열의 i 인덱스 수는 i 인덱수 수보다 더 먼저 나온 수들과 수열을 만들어야 되기 때문에 range(i)를 사용
if A[i] > A[j]: #수열의 i 인덱스 수와 그보다 먼저 나온 수들을 비교
dp[i] = max(dp[i], dp[j]+1) #만약 A[i]가 A[j]보다 크다면 dp[j] 수열에 A[i]를 붙여서 수열의 길이를 하나 늘릴 수 있으므로 dp[j] + 1
하지만 n ** 2의 시간 복잡도를 가지는 코드는 매우 비효율적이므로 완전탐색을 이분 탐색으로 바꿔 시간복잡도를 n * logn으로 줄여볼 수 있다.
- LIS, LIS_idx, real_LIS 세 가지 변수가 존재한다.
- LIS에는 수를(진짜 LIS가 아님에 주의), LIS_idx에는 입력 받은 수가 어떠한 인덱스를 가지고 있는지, real_LIS에는 LIS_idx를 토대로 진짜 LIS를 만들어서 저장할 것이다.
- LIS가 진짜 LIS가 아닌 이유는 각 수가 어떠한 인덱스에 들어가는지만 신경 쓰고 수의 순서는 신경 쓰지 않기 때문이다. (ex. [3, 5, 2]의 경우, [3, 5]가 답이지만 LIS는 [2, 5]를 저장하고 있다.)
- LIS_idx를 이용해 real_LIS를 추출하는 원리는 예를 들어 [3, 6, 7, 4, 1]의 경우 LIS_idx는 [1, 2, 3, 2, 1]를 저장하고 있을 것이다. len(LIS)를 통해 LIS의 길이를 알 수 있으므로 이를 이용해 가장 먼저 나온 3을 저장하고, 그 뒤에 가장 먼저 나온 2를 저장하고, 그 뒤에 가장 먼저 나온 1을 저장하는 방식으로 append해서 역순으로 만들면 그것이 real_LIS이다.
- LIS와 LIS_idx는 첫 번째 수를 넣은 상태로 초기화하여 시작하고, target이 LIS의 마지막 값보다 크다면 LIS에 추가하고, 크지 않다면 이분 탐색을 이용해 어느 인덱스에 들어가야 하는지 파악하여 LIS를 업데이트한다.
#가장 긴 증가하는 부분 수열4
n = int(input())
li = list(map(int, input().split()))
LIS = [li[0]]
LIS_idx = [1]
real_LIS = []
def bs(target, lst):
st = 0
end = len(lst) - 1
while st <= end:
mid = (st + end) // 2
if target <= lst[mid]:
end = mid - 1
else:
st = mid + 1
return st
for i in range(1, n):
if LIS[-1] < li[i]:
LIS.append(li[i])
LIS_idx.append(len(LIS))
else:
idx = bs(li[i], LIS)
LIS[idx] = li[i]
LIS_idx.append(idx + 1)
LIS_idx = LIS_idx[::-1]
s = 0
maxi = max(LIS_idx)
for i in range(len(LIS_idx)):
if LIS_idx[i] + s == maxi:
s += 1
real_LIS.append(li[len(li) - 1 - i])
print(len(LIS))
print(*real_LIS[::-1])