LIS

LIS

LIS(Longest Increasing Subsequence), 최장 증가 부분 수열이란 주어진 수열에서 가장 긴 증가하는 부분수열을 말한다. 예를 들어 수열 A = {1, 3, 2, 7, 3, 5}에서 LIS는 {1, 3, 4, 5}이다. LIS의 길이를 구하는 방법과, 실제 예를 역추적하는 방법을 알아보겠다.

 

$A$는 길이의 $n$의 음이 아닌 정수로 이루어진 수열이다(1-based). (좌표압축을 통해 음이 아닌 정수 조건을 강제시킬 수 있다.)

$A[i]$는 주어진 수열의 i번째 수,

$L[i]$는 $A[1], \cdots, A[i]$만 고려했을 때 $A_i$로 끝나는 LIS의 길이

를 의미한다.

모든 $i$에 대해 $L[i]$를 구하고, 이 중 최댓값이 주어진 수열의 LIS이다.

 

$O(n^2)$ dp

$j < i$ 이고 $A[j] < A[i]$ 이면 $A[j]$로 끝나는 부분 수열에 $A[i]$를 덧붙여 더 긴 부분 수열을 만들 수 있다.

따라서 다음과 같은 점화식이 만들어진다: $L[i]=\max_{j < i ,\  A[j] < A[i]}(L[j])+1$

이는 $O(n^2)$에 계산할 수 있다.

 

$O(nlogn)$ dp with segment tree

$j < i ,\  A[j] < A[i]$을 만족하는 $L[j]$중 최댓값을 구하는 과정을 세그먼트 트리로 최적화 할 수 있다.

트리의 [0,A[i]) 구간에 구간 최대 쿼리를 날리고 1을 더해 L[i]를 구할 수 있고, 트리의 A[i]번째 노드에 L[i]를 업데이트하면 된다.

 

$O(nlogn)$ dp with binary search

새로은 배열 $B$를 도입한다. $B[i] = min_{L[j]=i}(A[j])$ 이다. 풀어서 쓰면 $x$로 끝나는 LIS의 길이가 i인 최소 $x$를 의미한다. 그러면 $ L[i] = \max_{ B[j]<A[i] }( j )+1 $ 라는 새로운 점화식을 생각할 수 있다. 이는 $B[j] \geq A[i]$인 최소 인덱스를 의미란다.

이때 배열 $B$는 단조증가한다는 사실을 통해 이분탐색으로 점화식을 $O(logN)$에 계산할 수 있다.

$B$의 초기상태을 $B[0]=-1$, 나머지는 $\inf$으로 초기화해둔다. 이때 $B$는 단조증가 조건을 만족한다.

이분탐색을 이용해 $B[k] \geq A[i]$인 최소 인덱스 k를 찾았다고 하자. 이는 L[i]=k를 의미한다. $B[k]=A[i]$로 갱신한다. 여전히 $B[k-1] \leq B[k] \leq B[k+1]$을 만족한다. 따라서 배열 $B$는 단조증가한다.

 

코드 이후 추가 예정