[TIL] LIS 알고리즘 (최장 증가 부분 수열)

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

 - 원소가 n개인 배열의 일부 원소로 만든 수열 중 각 원소가 이전의 원소보다 크며 길이가 최대인 부분 수열

 

 

 

백준 dp 알고리즘을 풀다가 LIS 알고리즘을 접하게 되었다. 

LIS를 푸는 방법으로는 DP를 이용한 방법과 이분탐색 방법 두 가지가 있다.

 

 

 

1.DP를 활용

[1,3,2,7,6,4,9,8] 이라는 배열 lst가 존재할 때

dp 리스트를 사용하여 각 인덱스별로 최장 증가 부분 수열의 길이를 구한 것이다.

lst =[1,3,2,7,6,4,9,8]
dp=[1]*len(lst)

for i in range(len(lst)):
    for j in range(i):
        if lst[i]>lst[j]:
            dp[i] = max(dp[i], dp[j]+1)
            
print(dp)	# [1,2,2,3,3,3,4,4]

 

관련 문제로는 다음과 같다.

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

11054번: 가장 긴 바이토닉 부분 수열

바이토닉 부분 수열의 경우 감소하는 경우도 고려해야 하므로

리스트를 반대로 뒤집은 뒤 최장 증가 부분 수열을 구한 후 다시 뒤집으면 된다.

위의 과정을 고려하여 코드를 짜면 아래와 같다.

 

import sys

input = sys.stdin.readline

n = int(input())
lst=[*map(int, input().split())]
dp1=[1]*n
dp2=[1]*n

for i in range(n):
    for j in range(i):
        if lst[i]>lst[j]:
            dp1[i] = max(dp1[i], dp1[j]+1)

re_lst=lst[::-1]

for i in range(n):
    for j in range(i):
        if re_lst[i]>re_lst[j]:
            dp2[i] = max(dp2[i], dp2[j]+1)
            
dp2.reverse()

rst=[]
for i in range(n):
    rst.append(dp1[i]+dp2[i])
print(max(rst)-1)

마지막 결과에서 -1을 해주는 것은 같은 인덱스 간 중복되는 숫자가 있으므로 그것을 제외하기 위함이다.

 

 

2.이분 탐색을 활용

dp를 활용하는 방법은 모든 원소를 두번씩 돌기 때문에 O(N^2)의 시간 복잡도를 가진다.

그러나 이분탐색을 활용하면 O(nlogn)의 시간 복잡도를 가지므로 훨씬 효율적이다.

 

[1,3,2,7] 이라는 배열 lst가 존재할 때

lis 리스트를 이용하여 최장 증가 부분 수열을 구한다.

lis의 첫 인덱스에는 lit의 첫 번째 원소를 넣어준다.

이후, lst를 순회하며 lst[i]의 값이 lis의 마지막 원소보다 크다면 lis에 append 시키고

작다면 lis에 들어갈 수 있는 인덱스 값을 이분탐색으로 찾은 후 값을 append 시킨다.

 

1-1) 이분 탐색의 구현

lst =[1,3,2,7]
lis =[lst[0]]

def binarySearch(x):
    start = 0
    end = len(lis)-1
    
    while start <= end:
        mid = (start+end) //2
        
        if lis[mid] == x:
            return mid
        elif lst[mid] <x:
            start = mid +1
        else:
            end = mid -1
    return start

for i in range(1,len(lst)):
    if lst[i]> lis[-1]:
        lis.append(lst[i])    
    else:
        idx = binarySearch(lst[i])
        lis[idx] = lst[i]
        
            
print(lis)		# [1,2,7]
print(len(lis))		# 3

 

1-2) bisect 모듈 사용

 

파이썬에서의 이분 탐색은 bisect 모듈을 사용하여 간단하게 구현할 수 있다.

bisect_left(list, value) : 왼쪽 인덱스

bisect_right(list, value) : 오른쪽 인덱스

from bisect import bisect_left

lst =[1,3,2,7]
lis =[lst[0]]

for i in range(1,len(lst)):
    if lst[i]> lis[-1]:
        lis.append(lst[i])    
    else:
        idx = bisect_left(lis, lst[i])
        lis[idx] = lst[i]
        
            
print(lis)		#[1,2,7]
print(len(lis))		# 3