LIS 최장 증가 부분 수열

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열은 주어진 수열 중에서 각 요소가 증가하는 형태의 부분수열 중 가장 긴 수열을 의미한다. 말로 설명하니 복잡한데 아래 예를 보면 간단하다. 예시는 백준 알고리즘의 11053번 문제이다.

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

 이런 최장 증가 부분 수열을 찾는 방식은 가장 간단하게는 DP테이블을 이용하는 문제해결이다. 

주어진 수열이 arr[n] 라 할대 dp[n]의 배열을 만들고, 각 요소마다 가질수 있는 최대 길이값을 저장하는 방식이다.

이 방식으로 문제를 푼것이 아래 포스팅.

 

coder9084.tistory.com/109

백준 11053 가장 긴 증가하는 부분수열 java 풀이

 

헌데 이와같이 구현하면 이중 for문을 돌면서 시간복잡도는 O(n^2)이 된다. 더 시간복잡도를 줄일 수 있는 다른 방법으로는 이분탐색을 이용한 방법이다.

List를 하나 만들고 주어진 수열에서 매 요소를 꺼내면서 List에 같거나 더 큰 요소 중 최소인 요소 자리에 삽입하는 방식이다. 과정을 보면

 

 1. 주어진 수열에서 요소를 차례로 꺼낸다.

 2. List에서 꺼낸 요소와 같거나 더 큰 값을 갖는 요소 중 최소 요소를 이분탐색 방식으로 찾아서 교체한다.

 3. 1-2. 작업을 반복한다.

 

이를 예시로 들어서 보면  주어진 수열이 A = {10, 20, 10, 30, 25, 50} 일때, LIS는 {10, 20, 25(30), 50} 이 된다.

 

 10을 꺼내서 list에 크거나 같은 값 중 최소를 찾아서 넣으면 처음에는 비어있기 때문에 {10}

 20을 꺼내서 위 작업을 반복하면 {10, 20}

 10을 꺼내서 위 작업을 반복하면 {10, 20}

 30을 꺼내서 위 작업을 반복하면 {10, 20, 30}

 25를 꺼내서 위 작업을 반복하면 {10, 20, 25}

 50을 꺼내서 위 작업을 반복하면 {10, 20, 25, 50}

 

 결과적으로 list에 남아있는 요소들이 LIS가 되는것을 확인 할 수 있다. 매번 크거나 같은 값 중 최소를 찾는 작업이 이분탐색으로 실행되기 때문에 log n의 시간복잡도를 갖고, 모든 요소로 작업을 수행하기 때문에 결과적으로 O(nlogn)의 시간복잡도를 갖게된다.

 하지만 주의해야 할 점은 LIS의 길이는 보장이 되지만 같은 길이의 부분함수가 여럿이라면 요소들의 조합을 보장하진 않는다는 점이다. 위의 문제에서도 볼 수 있지만 결과는 {10, 20, 25, 50} 으로 30이 포함되지 않는다.