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

LIS 알고리즘

• 최장 증가 부분 수열
• 일반적으로 DP(동적 계획법)으로 푸는 알고리즘
• 임의의 수열이 주어질 때, 이 숭려에서 몇 개의 수들을 제거해서 부분 수열을 만든다.
• 이 때 부분수열들을 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다.

 

예시 코드

• 아래의 배열이 주어졌을 때

arr = [3,5,7,9,2,1,4,8]

 

• 아래처럼 부분 수열을 만들 수 있다.
• 이 중에 3,5,7,8이 LIS

arr = [3,7,9,1,4,8]
arr = [7,9,1,8]
arr = [3,5,7,8]
arr = [1,4,8]

 

일반적인 DP 풀이 방법 - O(n^2)

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

 

이분 탐색 이용 - O(nlogn)

# 수열 A가 주어질 때, 가장 긴 증가하는 부분 수열 구하기
n = 6
arr = [10,20,10,30,20,50]
lis = [0]

for case in arr:
    if lis[-1] < case:
        lis.append(case)
    else:
        left = 0
        right = len(lis)

        while left < right:
            mid = (left+right)//2
            if lis[mid] < case:
                left = mid + 1
            else:
                right = mid
        lis[right] = case
print(lis[1:])

 

 

백준 풀이 코드

https://hhiyeon.tistory.com/168

[백준] 11053번 가장 긴 증가하는 부분수열 - dp, LIS

 

https://hhiyeon.tistory.com/166

[백준] 12015번 가장 긴 증가하는 부분수열2 - 이분탐색, LIS