[ 백준 / 파이썬 ] 플레티넘 5 - 14003. 가장 긴 증가하는 부분 수열 5

난이도

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

입력

입력	출력
6 10 20 10 30 20 50	4 10 20 30 50

풀이

기존의 LIS를 풀었던 방식은 dp 방식으로 시간복잡도 O(N2) 의 방법이었다.

DP 방식

# N = 6, arr = [10, 20, 10, 30, 20, 50]
    DP = [1] * N
    ans = []
    for i in range(1, N):
        for j in range(i):
            if arr[j] < arr[i]:
                DP[i] = max(DP[i], DP[j] + 1)
    lis = max(DP)

    for i in range(N-1, -1, -1):
        if lis == DP[i]:
            ans.append(arr[i])
            lis -= 1

    print(*ans[::-1])

DP 로 구현하면 아주 쉽게 구현할 수 있지만, 이중 for문으로 시간초과가 발생하게 된다.

그래서 이분탐색 방식으로 LIS 문제를 풀어야 한다.
이분탐색 방식은 DP를 구현할 때, 기존의 DP 와 비교하는 것이 아니라 DP 자체를 LIS 로 보는 것이다.

DP 에 들어있는 수와 현재 배열에서 꺼내온 값과 비교해서 추가하거나 교체하거나 하는 방식이라고 할 수 있다.

DP = [arr[0]] # DP 를 arr[0] 번째로 초기화

for i in range(1, N):
	if DP[-1] < arr[i]:	# DP 의 마지막 값보다 arr[i] 값이 더 크면 추가
    	DP.append(arr[i])
    else:	# DP 의 마지막 값보다 작은 값이 들어오면, 현재 DP에서 적절한 위치를 찾아 교체
    	DP[bisect_left(DP, arr[i])] = arr[i]

이 때, DP 와 현재 들어온 값을 교체할 때 이진탐색을 통해 교체하므로 시간 복잡도가 O(N logN) 이다.

다만, 이 때 DP 에 들어있는 값이 LIS 는 맞지만 문제에서 요구하는 정답은 아니다.

더 작은 값이 들어오면 교체되기 때문에, 사전 순으로 나열한다면 정답일 수 도 있을 것 같다.

그래서 역추적 과정이 필요하다.

DP 에 값을 추가하거나 교체할 때 해당 인덱스를 저장할 배열을 새로 선언하여, 그걸 통해 역추적 하여 가장 긴 증가하는 부분 수열을 찾을 수 있다.

DP = [arr[0]] # DP 를 arr[0] 번째로 초기화
record = [-1] * N # i 번째에 DP 에 저장되는 인덱스

for i in range(1, N):
	if DP[-1] < arr[i]:	# DP 의 마지막 값보다 arr[i] 값이 더 크면 추가
    	record[i] = len(dp) 
    	DP.append(arr[i])
    else:	# DP 의 마지막 값보다 작은 값이 들어오면, 현재 DP에서 적절한 위치를 찾아 교체
    	record[i] = bisect_left(DP, arr[i])
    	DP[bisect_left(DP, arr[i])] = arr[i]

이분탐색으로 LIS 를 찾는 방법은 정말 간단해서 쉽게 이해했는데, 역추적 과정이 정말 아리까리 알듯말듯 어려웠다..

해당 블로그 글을 보고 이해했으니, 이 글을 보는 사람도 참고하면 좋을 듯 하다.

코드

from sys import stdin
from bisect import bisect_left

input = stdin.readline

def solution(N):
    arr = list(map(int, input().split()))
    dp = [arr[0]]
    record = [-1] * N
    record[0] = 0
    for i in range(1, N):
        if dp[-1] < arr[i]:
            record[i] = len(dp)
            dp.append(arr[i])

        else:
            record[i] = bisect_left(dp, arr[i])
            dp[bisect_left(dp, arr[i])] = arr[i]

    stack = []
    idx = len(dp) - 1
    for i in range(N-1, -1, -1):
        if record[i] == idx:
            idx-=1
            stack.append(arr[i])
	print(len(dp))
    print(*reversed(stack))


solution(int(input()))