LIS(Longest Increasing Subsequence) 알고리즘

LIS 알고리즘이란?

주어진 수열에서 최장 증가 부분 수열을 구하는 알고리즘이다. 단, LIS 알고리즘은 최장 증가 부분 수열의 길이만 알 수 있다. 최장 증가 부분 수열을 구하는 알고리즘에는 2가지 방법이 있다.

1. DP를 활용한 방법: O(N^2)의 시간 복잡도를 갖는다.
2. LIS를 활용한 방법: O(NlogN)의 시간 복잡도를 갖는다.

LIS 알고리즘

LIS를 만들기 위해서는 만드는 과정에서 LIS의 마지막 원소가 가능한 작을 수록 더 긴 LIS를 생성할 수 있다는 것이 중요하다. 중간에 있는 값이 변화한다고 LIS의 마지막 값이 변화하지 않기 때문에, LIS의 길이만 알 수 있다는 것이다. 즉, 더 작은 값을 기억하고 진행했을 때, 더 긴 LIS를 만들 수 있는 경우를 위해서 LIS 원소에 더 작은 값이 들어갈 수 있다면 업데이트를 해주는 것이다.

1. 현재 숫자가 LIS 테이블의 최댓값보다 크다면 LIS 테이블 뒤에 추가한다.
2. 1이 아니라면, 이분 탐색을 통해 현재 숫자가 LIS 테이블에서 어느 위치에 들어갈 수 있는지 확인 후 교환한다. (현재 숫자보다 큰 수중에 최솟값을 찾아야 함)
3. 반복 후 LIS 테이블의 크기를 반환한다. (단, 길이만 알 수 있음)

[10, 20, 10, 30, 25, 50]
1. lis = [10]
2. lis = [10, 20]
3. lis = [10, 20] (10이 첫번째 자리로 들어감)
4. lis = [10, 20, 30]
5. lis = [10, 20, 25] (25가 세번째 자리로 들어감)
6. lis = [10, 20, 25, 50] 으로 나오게 된다.

관련 문제

백준 12738 가장 긴 증가하는 부분 수열