2.16.2 LIS

개념

부분 수열은 원래 순서를 유지하면서 일부 원소를 골라 만든 수열입니다. LIS는 뒤의 원소가 바로 앞 원소보다 큰 부분 수열 중 가장 긴 것입니다. 원소들이 연속해서 놓여 있을 필요는 없습니다.

$[3,1,2,5,4]$에는 $[1,2,4]$와 $[1,2,5]$가 있고 LIS의 길이는 $3$입니다. 같은 값을 이어 붙이면 엄격하게 증가하지 않으므로 $[2,2]$의 LIS 길이는 $1$입니다.

방법 1: 위치별 DP — O(N²)

$D_i$를 인덱스 $i$의 원소 $a_i$로 끝나는 최장 증가 부분 수열의 길이로 정의합니다. 원소 하나만 선택할 수 있으므로 모든 $D_i$의 초기값은 $1$입니다.

$a_i$ 앞에 붙일 원소 $a_j$는 원래 순서와 증가 조건을 모두 만족해야 합니다. 따라서 $j<i$이고 $a_j<a_i$인 위치를 확인하여 다음과 같이 갱신합니다.

$D_i\leftarrow\max(D_i,D_j+1).$

$a_j$로 끝나는 수열 뒤에 $a_i$를 붙이면 길이가 $1$ 늘어납니다. 가능한 이전 위치를 모두 확인하므로 그중 가장 긴 수열을 찾습니다. 전체 LIS의 길이는 모든 $D_i$ 중 최댓값입니다. 마지막 원소에서 끝나는 수열만 확인하면 앞에서 끝난 더 긴 수열을 놓칠 수 있습니다.

각 위치에서 앞의 원소를 모두 비교합니다. 비교 횟수는 $0+1+\cdots+(N-1)=N(N-1)/2$이므로 시간복잡도는 $O(N^2)$입니다.

위치별 DP의 역추적

길이와 함께 그 길이를 만든 이전 위치를 저장하면 실제 수열도 구할 수 있습니다. $P_i$를 $a_i$ 바로 앞에 선택한 원소의 인덱스로 정하고, 이전 원소가 없으면 $-1$로 둡니다.

$D_j+1>D_i$일 때 $D_i$를 갱신하면서 $P_i=j$도 함께 저장합니다. 같은 길이를 만드는 후보가 여러 개라면 그중 하나를 저장하면 됩니다.

앞의 수열에서 이전 위치를 왼쪽부터 확인하고 더 길어질 때만 갱신하면 다음 결과를 얻습니다.

최대 길이 $3$을 가진 위치 중 $3$에서 시작하면 $3\to2\to1\to-1$로 이전 위치를 따라갑니다. 이때 모은 값은 $[5,2,1]$입니다. 끝에서 시작으로 이동했으므로 순서를 뒤집으면 LIS $[1,2,5]$를 얻습니다. 위치 $4$에서 시작하면 $[1,2,4]$를 얻습니다.

방법 2: 이분 탐색 — O(N log N)

같은 길이의 증가 부분 수열이라면 마지막 값이 작을수록 다음 원소를 붙이기 쉽습니다. 마지막 값이 $5$이면 다음 값이 $5$보다 커야 하지만, 마지막 값이 $4$이면 이후에 나오는 $5$도 붙일 수 있습니다.

$T_k$를 지금까지 확인한 원소들로 만든 길이 $k+1$인 증가 부분 수열의 마지막 값 중 최솟값으로 정의합니다. 새 값 $x$를 왼쪽부터 하나씩 처리하며 $T$에서 $x$ 이상인 첫 위치 $k$를 찾습니다.

• 그런 위치가 있으면 $T_k$를 $x$로 바꿉니다. 길이 $k+1$인 수열의 마지막 값을 더 작게 또는 같게 만듭니다.
• 그런 위치가 없으면 $T$의 끝에 $x$를 추가합니다. 가장 긴 수열의 마지막 값보다 $x$가 크므로 길이를 $1$ 늘릴 수 있습니다.

$T$는 증가하는 순서를 유지합니다. 길이 $k+1$인 증가 부분 수열의 끝값보다 그 앞 $k$개 원소의 끝값이 작고, $T_{k-1}$은 그보다 작거나 같은 최솟값이기 때문입니다. 따라서 $x$ 이상인 첫 위치를 이분 탐색으로 찾을 수 있습니다. C++의 lower_bound, Python의 bisect_left가 이 위치를 찾습니다.

같은 값을 만나면 기존 위치를 교체하므로 길이가 늘어나지 않습니다. 모든 원소를 처리한 뒤 $T$의 길이가 LIS의 길이입니다. 원소마다 이분 탐색을 한 번 수행하므로 시간복잡도는 $O(N\log N)$입니다.

이분 탐색 풀이의 역추적

$T$에는 길이별 후보의 끝값이 들어 있으므로, 그 배열 자체가 항상 원래 수열의 부분 수열인 것은 아닙니다. $[2,3,4,1]$을 처리한 최종 $T$는 $[1,3,4]$이지만, 원래 수열에서 $1$은 $3,4$보다 뒤에 있습니다. 실제 LIS는 $[2,3,4]$입니다.

실제 순서를 복원하려면 두 종류의 위치를 저장합니다.

$a_i$를 넣을 위치가 $k$라면, $k>0$일 때 $P_i=I_{k-1}$로 정합니다. $k=0$이면 앞에 붙일 원소가 없으므로 $P_i=-1$입니다. 그 뒤 $T_k=a_i$, $I_k=i$로 갱신합니다.

$I_{k-1}$은 이미 처리한 원소의 위치이고, 그 끝값은 $a_i$보다 작습니다. 따라서 $P_i$를 따라가면 인덱스와 값이 모두 작아져 원래 순서에 맞는 증가 부분 수열을 얻습니다. 이후 $I$의 후보가 바뀌어도 각 원소에 저장한 $P_i$는 유지합니다.

$[2,3,4,1]$을 처리한 결과는 다음과 같습니다.

마지막에는 가장 긴 길이의 끝 위치인 $I_2=2$에서 시작합니다. $P$를 따라 $2\to1\to0\to-1$로 이동하여 값 $[4,3,2]$를 모으고, 뒤집어 $[2,3,4]$를 복원합니다. 마지막에 $I_0$이 $3$으로 바뀌어도 $P_1=0$은 그대로이므로 올바른 이전 원소를 찾습니다.

복잡도와 선택 기준

원소 수를 $N$, 복원할 LIS 길이를 $L$이라고 합니다. 원소가 $1\,000$개이면 이차 시간 DP는 약 $50$만 번 비교하지만, $100\,000$개이면 약 $50$억 번 비교합니다. 입력이 커질수록 이분 탐색을 활용한 방법이 적합합니다.

예제

문제

수열의 최장 증가 부분 수열의 길이와 그에 해당하는 수열 하나를 구하여라. 증가 부분 수열에서 뒤의 원소는 바로 앞의 원소보다 커야 한다.

입력

첫째 줄에 원소 수 $N$이 주어진다. $1\le N\le1\,000$이다.

둘째 줄에 수열의 원소 $a_1,a_2,\ldots,a_N$이 공백을 사이에 두고 주어진다. $1\le a_i<10\,000$이다.

출력

첫째 줄에 LIS의 길이를 출력한다. 둘째 줄에 LIS의 원소를 순서대로 공백으로 구분하여 출력한다. 가능한 LIS가 여러 개이면 그중 하나를 출력한다.