[Python] 가장 긴 증가하는 부분 수열(LIS) 구하는 방법

가장 긴 증가하는 부분 수열의 '길이'을 구하는 방법은

1. DP(Dynamic Programming) - 동적 계획법

2. Binary Search - 이분 탐색

으로,, 이전 게시글 참고하기 : https://bskwak.tistory.com/259 

 

이번 게시물은 '길이'가 아닌 가장 긴 증가하는 부분 수열(LIS) 자체를 구하는 방법이다.

풀이 방법을 간단하게 설명하면,

1. dp를 통해 LIS 길이 구하기

2. 역추적하여 배열 구하고 뒤집으면 구할 수 있음

 

관련 문제 : 

https://www.acmicpc.net/problem/14002

 

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[i]>arr[j]:
            dp[i] = max(dp[i],dp[j]+1)
            
max_len = max(dp)
idx = dp.index(max_len)

res = []
while idx>=0:
    if dp[idx] == max_len:
        res.append(arr[idx])
        max_len -=1
    idx -=1

res.reverse()
print(*res)

 

max_len : 가장 긴 증가하는 부분 수열의 길이 

idx : max_len에 해당하는 위치 

res : 가장 긴 증가하는 부분 수열을 담을 배열

 

 arr = [10, 20, 10, 30, 20, 50] 일때, 

dp =[1, 2, 1, 3, 2, 4]

 

max_len = 4 이고, idx = 5 (초기값)

반복문을 하나씩 실행하면, 아래와 같이 추가된다. 즉, idx 4->3->2->1 에 해당하는 값을 추가하면 된다..

[50]
[50, 30]
[50, 30, 20]
[50, 30, 20, 10]

 

 

문제는,, 이렇게 풀면 14003 문제처럼 n의 범위가 커졌을 때, 시간 초과가 난다..

관련 문제 : https://www.acmicpc.net/problem/14003

 

위에서 dp 구하는 부분을 이분탐색을 통해 구하면 된다!

import sys
input = sys.stdin.readline

def bs(arr,target):
    left, right = 0, len(arr)-1
    while left<= right:
        mid = (left+right)//2
        if arr[mid]<target:
            left = mid+1
        else:
            right = mid-1
    return left

n = int(input())
arr = list(map(int, input().split()))
INF = int(1e10)

check = [0]*n
inc_arr = [INF]*n

for i, x in enumerate(arr):
    idx = bs(inc_arr,x)
    inc_arr[idx] = x
    check[i] = idx

max_len = max(check)
idx = check.index(max_len)

res = []
while idx>=0:
    if check[idx] == max_len:
        res.append(arr[idx])
        max_len -=1
        # print(res)
    idx -=1

res.reverse()
print(len(res))
print(*res)