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

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란?

 

어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 최장 증가 부분 수열(Longest Increasing Subsequence)이란 '증가하는 부분 수열' 중 가장 긴 수열을 의미합니다.

 

2. 최장 증가 부분 수열(Longest Increasing Subsequence)동작 원리

 

O(NlogN)의 시간복잡도가 걸리는 lower_bound를 활용하여 구할 수 있습니다.

 

1

2

3

5

6

위와 같은 수열을 예로 들어서 설명드리겠습니다.

 

수열의 첫 수를 LIS에 넣어줍니다.

LIS의 마지막 수보다 현재 숫자가 더 크다면 LIS에 넣어줍니다.

그렇지 않다면 lower_bound를 활용해 현재 수보다 크거나 같은 수가 있는 곳의 index의 값을 현재 수로 바꿔줍니다.

위와 같은 방식으로 LIS를 채워주면 다음과 같은 결과를 얻을 수 있습니다.

 

유의할 점은 위의 방식으로 LIS를 구하면 길이는 구할 수 있지만 부분수열 자체는 구할 수 없습니다.