가장 긴 증가하는 부분 수열

작성일 | In

수열 $\{a_n\}$이 주어졌을 때, 부분 수열 중 증가하는 것의 개수를 빠르게 세는 방법을 알아봅시다.

LIS(Longest Increasing Subsquence)라고도 불리는 이 알고리즘은 DP와 이분탐색 두 가지 방법이 있습니다.

DP: $O(N^2)$

길이 찾기

$dp[i]$를 $a_i$로 끝나는 LIS의 길이라고 합시다.
예를 들어 $\{a_n\} = \{1, 2, 1, 3, 2, 5\}$이라고 하면 $dp[3]$은 $3$입니다. $(\because \{1, 2, 3\})$

이때 $j < i, a_j < a_i$라면 $dp[i] = max(dp[j] + 1, dp[i])$임을 알 수 있습니다.
$\underset{i = 1}{\overset{n - 1}{FOR}}\ \underset{j = 0}{\overset{i-1}{FOR}}$ 로 반복문을 돌려 $dp$배열을 완성할 수 있습니다.

아래는 11053번: 가장 긴 증가하는 부분 수열의 정답 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
a = list(map(int, input().split()))

dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if a[j] < ar[i]:
            dp[i] = max(dp[j] + 1, dp[i])

print(max(dp))

부분 수열 찾기

완성된 $dp$배열을 통해 LIS를 찾아봅시다.
먼저 부분 수열의 끝에 오는 원소부터 역추적합니다.
가장 긴 증가하는 부분 수열의 길이가 $n$이라고 하면 $dp[i] = n, n-1, n-2, n-3$인 $i$를 뒤에서부터 순서대로 찾으면 됩니다.
찾은 순서의 역순이 LIS가 됩니다.

1
2
3
4
5
6
7
lis = []

for i in range(n-1, -1, -1):
    if dp[i] == findingIndex:
        lis.append(arr[i])

print(*list[::-1]) # 뒤집어서 출력

이분 탐색: $O(NlogN)$

길이 찾기

이분 탐색을 이용해 LIS를 찾아가면 길이를 빠르게 구할 수 있습니다.

이 알고리즘은 풀이를 먼저 보고 이해하는 것이 편합니다.

아래는 12015번: 가장 긴 증가하는 부분 수열 2의 정답 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
lis = []

for a_i in a:
    index = bisect_left(lis, a_i)
    if index == len(lis):
        lis.append(a_i)
    else:
        lis[index] = a_i

print(len(lis))

$LIS$ 배열은 항상 오름차순 정렬을 유지합니다.
이분탐색을 통해 구한 $index$로 $LIS_{index}$를 $a_i$로 대체합니다.
이렇게 하면 $LIS$는 항상 LIS의 형태를 띄므로 답을 구할 수 있습니다.
하지만 $LIS$는 실제로 LIS가 아닙니다. 그럼에도 불구하고 $LIS$의 길이가 LIS의 길이가 되는 이유를 살펴보겠습니다.

수열 $\{a_n\} = \{1, 3, 7, 4, 5, 2, 8\}$를 예로 들어 설명해 보겠습니다.
$a_0 = 1$, $LIS = [1]$
$a_1 = 3$, $LIS = [1, 3]$
$a_2 = 7$, $LIS = [1, 3, 7]$
$a_3 = 4$, $LIS = [1, 3, 4]$

$LIS_2$를 $a_3$으로 대체했습니다. $\{1, 3, 4\}$로 시작하는 증가 부분 수열이 $\{1, 3, 7\}$로 시작하는 것보다 길거나 같기 때문입니다.
7보다 큰 수가 온다면 4 뒤에 올 수 있을 테고, 7보다 작은 수가 오더라고 4 뒤에 올 수 있기 때문입니다.

$a_4 = 5$, $LIS = [1, 3, 4, 5]$
$a_5 = 2$, $LIS = [1, 2, 4, 5]$

여기서는 $\{1, 3, 4, 5\}$와 $\{1, 2\}$를 동시에 보고 있는 것으로 이해할 수 있습니다.
아까와 같은 이유로 $\{1, 3, \dots\}$ 대신 $\{1, 2, \dots\}$를 구하는 것입니다.
앞의 3은 이때까지 이러한 수가 등장했다는 것을 의미하지, 그 이상의 의미를 가지지 않습니다.
5보다 큰 수가 등장해서 $LIS$가 길어질 때 3은 아무런 영향도 미치지 않습니다. 대신 $\{1, 3\}$으로 시작하는 수열을 빠르게 찾을 수 있도록 해 주는 것이죠.
그러니까 위에서 봤던 $dp[i]$를 빠르게 구하도록 도와주는 역할을 하는 것입니다.

부분 수열 찾기

각 반복문에서 찾은 index가 $dp[i]$와 같다는 것을 알 수 있습니다. 그래서 이를 따로 저장하는 배열을 만들어서 DP와 같은 방법으로 구하면 됩니다.

가장 긴 증가하는 부분 수열