최장 증가 부분 수열
(LIS: Longest Increasing Subsequence)
1. 개요
최장 증가 부분 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다.2. 정의
어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.예를 들어 다음 수열이 주어졌다고 하자.
3 5 7 9 2 1 4 8
위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다.
3 7 9 1 4 8 (5, 2 제거)
7 9 1 8 (3, 5, 2, 4 제거)
3 5 7 8 (9, 2, 1, 4 제거)
1 4 8 (3, 5, 7, 9, 2 제거)
이들 중 첫번째, 두번째 수열은 일부가 오름차순으로 정렬되어 있다.
반면에 세번째, 네번째 수열은 전체가 오름차순으로 정렬되어 있다.
위와 같이 일부, 혹은 전체가 오름차순인 수열을 '증가 부분 수열'이라고 한다.
그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다.
즉, 위의 수열의 집합에선 부분수열 3 5 7 8이 LIS이다.
한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열
5 1 6 2 7 3 8
에서 부분수열
1 2 3 8
5 6 7 8
은 모두 길이가 4인 LIS이다.
3. LIS의 길이 구하기 문제
길이 N인 임의의 수열이 주어졌을 때 그 수열의 LIS의 길이를 구하는 문제를 생각해 보자.이 문제를 푸는 알고리즘은 두 가지가 있다.
3.1. 첫 번째 알고리즘: O(N2)
새로운 배열 D를 정의하자. D[i]의 정의는 다음과 같다.D[i]: A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이
A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다.
따라서 A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.
수열 A = 3 5 7 9 2 1 4 8을 예로 들어 알고리즘을 살펴보자.
(알고리즘의 규칙성을 위해 i = 0일 때를 추가하자. i = 0일 때 A[i] = 0, D[i] = 0이다.)
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 |
i = 1일 때를 살펴보자.
A[1] = 3이다. 3은 A[0] = 0 뒤에 붙을 수 있다. 따라서 D[1] = D[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 |
i = 2일 때를 살펴보자.
A[2] = 5이다. 5는 A[0] = 0, A[1] = 3 뒤에 붙을 수 있다. 이 때 D[0] = 0, D[1] = 1에서 D[1]이 가장 크다. 이 말은 A[1] = 3을 가장 마지막 값으로 가지는 증가부분수열의 길이가 가장 길다는 뜻이다. A[2]가 가장 긴 증가부분수열 뒤에 붙는 게 더 긴 증가부분수열을 만들 수 있다. 따라서 D[2] = D[1] + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 |
i = 3일 때를 살펴보자.
A[3] = 7이다. 7는 A[0] = 0, A[1] = 3, A[2] = 5 뒤에 붙을 수 있다. 이 때 D[0] = 0, D[1] = 1, D[2] = 2에서 D[2]가 가장 크다. 따라서 D[3] = D[2] + 1 = 3이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 |
i = 4일 때를 살펴보자.
A[4] = 9이다. 9는 A[0] = 0, A[1] = 3, A[2] = 5, A[3] = 7 뒤에 붙을 수 있다. 이 때 D[0] = 0, D[1] = 1, D[2] = 2, D[3] = 3에서 D[3]이 가장 크다. 따라서 D[4] = D[3] + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 |
i = 5일 때를 살펴보자.
A[5] = 2이다. 2는 A[0] = 0 뒤에 붙을 수 있다. 따라서 D[5] = D[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 |
i = 6일 때를 살펴보자.
A[6] = 1이다. 2는 A[0] = 0 뒤에 붙을 수 있다. 따라서 D[6] = D[0] + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 |
i = 7일 때를 살펴보자.
A[7] = 4이다. 4는 A[0] = 0, A[1] = 3, A[5] = 2, A[6] = 1 뒤에 붙을 수 있다. 이 때 D[0] = 0, D[1] = 1, D[5] = 1, D[6] = 1에서 D[1] = D[5] = D[6] = 1이 가장 크다. 따라서 D[4] = D[1] + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 |
i = 8일 때를 살펴보자.
A[8] = 8이다. 8는 A[0] = 0, A[1] = 3, A[2] = 5, A[3] = 7, A[5] = 2, A[6] = 1, A[7] = 4 뒤에 붙을 수 있다. 이 때 D[0] = 0, D[1] = 1, D[2] = 2, D[3] = 3, D[5] = 1, D[6] = 1, D[7] = 2에서 D[3] = 3이 가장 크다. 따라서 D[4] = D[3] + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 4 |
이렇게 해서 배열 D를 다 완성했다. D의 값들 중 가장 큰 값(D[4] = D[8] = 4)가 수열 A = 3 5 7 9 2 1 4 8의 LIS의 길이다.
해당 길이를 가지는 부분수열을 찾는 방법은 여러 개가 있지만, 가장 간단한 것은 해당 값을 가지는 값부터 거꾸로 이어나가는 것이다. 0부터 순서대로 이어나가는 경우 해당 값을 마지막에 가진다는 보장이 없기 때문이다.
이 알고리즘은 N개의 수들에 대해 자기 자신 전의 모든 수를 다 훑어봐야 하므로 O(N2)의 시간복잡도를 가지는 알고리즘이 된다.
3.2. 두 번째 알고리즘: O(N log N)
두 번째 알고리즘은 첫 번째 알고리즘을 개량한 형태이다. 두 번째 알고리즘은 다음과 같은 의문에서 시작한다.D[i]를 계산하기 위해 A[0] ~ A[i - 1]를 꼭 다 훑어봐야 하는가?
첫 번째 알고리즘에서 A[0] ~ A[i - 1]를 훑어본 것은 A[i]보다 작은 A[j]를 가지는 j들 중 가장 큰D[j]를 찾기 위함이었다. 여기서 다음과 같은 생각을 이끌어낼 수 있다.
만약 D[j] = k를 만족하는 j 중 A[j]의 값이 가장 작은 j만 어딘가에 저장해 놓으면, 나중에 D[i] (i > j)를 계산할 때 그 값들만 참조하면 D[i]의 값을 쉽게 알 수 있다.
마찬가지로 수열 A = 3 5 7 9 2 1 4 8을 예로 설명하겠다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 |
위 표에 대해 하나의 표를 더 생각하자.
| D[i] | 0 |
| A[i] | 0 |
이 표는 D[i] = k인 값들 중 A[i]의 값이 가장 작은 값을 계속 저장한다. 이 표의 이름을 X라 하자.
i = 1일 때를 살펴보자.
A[1] = 3이다. 이때 X를 살펴보면 가장 마지막 A[i]의 값이 0이고, 이는 3보다 작다. 이 말은 현재 A[1] 앞의 수들로 만든 가장 긴 증가부분수열 중 마지막 값이 0인 증가부분수열이 있다는 말이다. 그리고 A[1]을 그 뒤에 붙일 수 있다. 따라서 따라서 D[1] = 0 + 1 = 1이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 |
| D[i] | 0 | 1 |
| A[i] | 0 | 3 |
i = 2일 때를 살펴보자.
A[2] = 5이다. 이때 X를 살펴보면 가장 마지막 A[i]의 값이 3이고, 이는 5보다 작다. 이 말은 현재 A[2] 앞의 수들로 만든 가장 긴 증가부분수열 중 마지막 값이 3인 증가부분수열이 있다는 말이다. 그리고 A[2]을 그 뒤에 붙일 수 있다. 따라서 D[2] = 1 + 1 = 2이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 |
| D[i] | 0 | 1 | 2 |
| A[i] | 0 | 3 | 5 |
i = 3일 때를 살펴보자.
A[3] = 7이다. 이때 X를 살펴보면 가장 마지막 A[i]의 값이 5고, 이는 7보다 작다. 따라서 D[3] = 2 + 1 = 3이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 |
| D[i] | 0 | 1 | 2 | 3 |
| A[i] | 0 | 3 | 5 | 7 |
i = 4일 때를 살펴보자.
A[4] = 9이다. 이때 X를 살펴보면 가장 마지막 A[i]의 값이 7이고, 이는 9보다 작다. 따라서 D[4] = 3 + 1 = 4이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 |
| D[i] | 0 | 1 | 2 | 3 | 4 |
| A[i] | 0 | 3 | 5 | 7 | 9 |
i = 5일 때를 살펴보자.
A[5] = 2이다. 이때 X의 A[i]들을 살펴보면 2는 0과 3 사이의 값이다. 그러므로 D[5] = 0 + 1 = 1이다.
X에서 D[i] = 1일 때의 A[i] 값은 현재는 3이나, A[5] = 2이므로 더 작은 2로 갱신해 준다. 이 말은 증가부분수열의 길이가 1인 수열 중 끝이 3으로 끝나는 증가부분수열(기존수열)과 끝이 2로 끝나는 증가부분수열(현재수열)이 있으므로, 이들 중 끝값이 더 작은 2를 X에 저장해 놓겠다는 것이다. 추후 D[i] = 2인 수열을 찾기 위해 A[5] = 2 뒤에 붙일 수 있는지만 확인하면 되기 때문이다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 |
| D[i] | 0 | 1 | 2 | 3 | 4 |
| A[i] | 0 | 2 | 5 | 7 | 9 |
i = 6일 때를 살펴보자.
A[6] = 1이다. 이때 X의 A[i]들을 살펴보면 1는 0과 2 사이의 값이다. 그러므로 D[6] = 0 + 1 = 1이다.
X에서 D[i] = 1일 때의 A[i] 값은 현재는 2이나, A[6] = 1이므로 더 작은 1로 갱신해 준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 |
| D[i] | 0 | 1 | 2 | 3 | 4 |
| A[i] | 0 | 1 | 5 | 7 | 9 |
i = 7일 때를 살펴보자.
A[7] = 4이다. 이때 X의 A[i]들을 살펴보면 4는 1과 5 사이의 값이다. 그러므로 D[7] = 1 + 1 = 2이다.
X에서 D[i] = 2일 때의 A[i] 값은 현재는 5이나, A[7] = 4이므로 더 작은 4로 갱신해 준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 |
| D[i] | 0 | 1 | 2 | 3 | 4 |
| A[i] | 0 | 1 | 4 | 7 | 9 |
i = 8일 때를 살펴보자.
A[8] = 8이다. 이때 X의 A[i]들을 살펴보면 8는 7과 9 사이의 값이다. 그러므로 D[8] = 3 + 1 = 4이다.
X에서 D[i] = 4일 때의 A[i] 값은 현재는 9이나, A[8] = 8이므로 더 작은 8로 갱신해 준다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| A | 0 | 3 | 5 | 7 | 9 | 2 | 1 | 4 | 8 |
| D | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 4 |
| D[i] | 0 | 1 | 2 | 3 | 4 |
| A[i] | 0 | 1 | 4 | 7 | 8 |
이렇게 해서 배열 D를 다 완성했다. D의 값들 중 가장 큰 값(D[4] = D[8] = 4)가 수열 A = 3 5 7 9 2 1 4 8의 LIS의 길이다.
이 알고리즘은 N개의 수들에 대해 X의 A[i]들을 훑어본다. 이때 X는 오름차순으로 항상 정렬되어 있으므로 이진 탐색을 사용할 수 있다. 이진 탐색을 사용하여 현재 A[i]보다 작은 A[j]를 X에서 찾는다.[1][2] 그 A[j]에 해당하는 D 값에 1을 더하면 D[i]를 쉽게 구할 수 있다.
따라서 이 알고리즘은 O(N log N)의 시간복잡도를 가진다.
4. 문제 예
4.1. 정렬 문제
사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞여 있고, 'A씨, 맨 뒤 / 맨 앞으로 가세요', 'A씨, B씨와 C씨 사이로 가세요' 꼴의 명령으로 사람들을 이동시킨다고 가정하자.)이 문제는 전형적인 LIS 응용 문제이다. 움직인 사람들의 총 수가 최소가 된다는 말은 움직이지 않은 사람들의 수가 최대가 된다는 것이다.
사람들의 번호들의 수열에서 이미 오름차순으로 정리된 쌍이 있다면 그들은 움직이지 않아도 된다. 따라서 그 수열의 LIS를 이루는 사람들은 움직이지 않고, 나머지 사람들이 그들 사이로 적절히 배열된다면 정렬할 수 있다.
[1] 이를 lower bound라고 한다.[2] 위 예시에서는 필요할 때마다 계속해서 X를 늘려나가는 식으로 묘사했는데, 만약 X의 초기값을 int_max 같이 매우 큰 값으로 채워놓으면 현재 X 안에 들어오지 않은 큰 D[i\]에 대해서도 같은 알고리즘을 적용시킬 수 있다.