최장 증가 부분 수열¶
$n$개의 수로 이루어진 배열 $a[0 \dots n-1]$이 주어집니다. 목표는 $a$에서 엄격하게 증가하는 가장 긴 부분 수열을 찾는 것입니다.
형식적으로는 다음을 만족하는 가장 긴 인덱스 수열 $i_1, \dots i_k$를 찾습니다.
이 글에서는 이 문제를 해결하는 여러 알고리즘을 다룹니다. 또한 이 문제로 환원할 수 있는 몇 가지 다른 문제도 다룹니다.
동적 계획법을 이용한 $O(n^2)$ 풀이¶
동적 계획법은 매우 광범위한 종류의 문제를 해결할 수 있게 해 주는 아주 일반적인 기법입니다. 여기서는 이 기법을 우리의 구체적인 문제에 적용합니다.
먼저 최장 증가 부분 수열의 길이만 구하고, 부분 수열 자체를 복원하는 방법은 나중에 알아봅니다.
길이 구하기¶
이를 위해 배열 $d[0 \dots n-1]$을 정의합니다. 여기서 $d[i]$는 인덱스 $i$의 원소에서 끝나는 최장 증가 부분 수열의 길이입니다.
Example
인덱스 4에서 끝나는 최장 증가 부분 수열은 길이가 3인 $\{3, 4, 5\}$이고, 인덱스 8에서 끝나는 가장 긴 것은 $\{3, 4, 5, 7, 9\}$ 또는 $\{3, 4, 6, 7, 9\}$로 둘 다 길이가 5이며, 인덱스 9에서 끝나는 가장 긴 것은 길이가 2인 $\{0, 1\}$입니다.
이 배열은 점진적으로 계산합니다. 먼저 $d[0]$, 그다음 $d[1]$, 이런 식으로 진행합니다. 이 배열을 모두 계산하고 나면, 문제의 답은 배열 $d[]$의 최댓값이 됩니다.
이제 현재 인덱스를 $i$라고 합시다. 즉, 값 $d[i]$를 계산하려 하며 이전 값 $d[0], \dots, d[i-1]$은 모두 이미 알고 있습니다. 그러면 두 가지 경우가 있습니다.
-
$d[i] = 1$: 구하려는 부분 수열은 원소 $a[i]$ 하나로만 이루어집니다.
-
$d[i] > 1$: 부분 수열은 $a[i]$에서 끝나며, 그 바로 앞에는 $j < i$이고 $a[j] < a[i]$인 어떤 수 $a[j]$가 옵니다.
$a[j]$에서 끝나는 그 부분 수열 자체도 $a[j]$에서 끝나는 최장 증가 부분 수열 중 하나라는 것은 쉽게 알 수 있습니다. 수 $a[i]$는 그 최장 증가 부분 수열을 수 하나만큼 늘릴 뿐입니다.
따라서 $a[j] < a[i]$인 모든 $j < i$를 순회하면서, $a[j]$에서 끝나는 최장 증가 부분 수열에 $a[i]$를 덧붙여 얻는 수열 중 가장 긴 것을 택하면 됩니다. $a[j]$에서 끝나는 최장 증가 부분 수열의 길이는 $d[j]$이고, 이를 하나 늘리면 길이는 $d[j] + 1$이 됩니다.
$$d[i] = \max_{\substack{j < i \\\\ a[j] < a[i]}} \left(d[j] + 1\right)$$
이 두 경우를 합치면 $d[i]$에 대한 최종 답을 얻습니다.
구현¶
다음은 위에서 설명한 알고리즘의 구현으로, 최장 증가 부분 수열의 길이를 계산합니다.
int lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i])
d[i] = max(d[i], d[j] + 1);
}
}
int ans = d[0];
for (int i = 1; i < n; i++) {
ans = max(ans, d[i]);
}
return ans;
}
부분 수열 복원하기¶
지금까지는 부분 수열의 길이를 구하는 방법만 배웠고, 부분 수열 자체를 구하는 방법은 아직 배우지 않았습니다.
부분 수열을 복원할 수 있도록 배열 $d[]$와 함께 계산할 보조 배열 $p[0 \dots n-1]$을 추가로 만듭니다. $p[i]$는 $i$에서 끝나는 최장 증가 부분 수열에서 끝에서 두 번째 원소의 인덱스 $j$가 됩니다. 다시 말해 인덱스 $p[i]$는 가장 큰 값 $d[i]$를 얻었던 바로 그 인덱스 $j$입니다. 이 보조 배열 $p[]$는 어떤 의미에서 조상을 가리킵니다.
그런 다음 부분 수열을 구하려면 $d[i]$가 최대인 인덱스 $i$에서 시작하여, 부분 수열 전체를 알아낼 때까지, 즉 $d[i] = 1$인 원소에 도달할 때까지 조상을 따라가기만 하면 됩니다.
복원 구현¶
앞 절의 코드를 조금 수정하겠습니다. 배열 $p[]$를 $d[]$와 함께 계산하고, 그 후에 부분 수열을 계산합니다.
편의를 위해 처음에는 조상을 $p[i] = -1$로 지정합니다. $d[i] = 1$인 원소의 조상 값은 $-1$로 남게 되며, 이는 부분 수열을 복원할 때 조금 더 편리합니다.
vector<int> lis(vector<int> const& a) {
int n = a.size();
vector<int> d(n, 1), p(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i] && d[i] < d[j] + 1) {
d[i] = d[j] + 1;
p[i] = j;
}
}
}
int ans = d[0], pos = 0;
for (int i = 1; i < n; i++) {
if (d[i] > ans) {
ans = d[i];
pos = i;
}
}
vector<int> subseq;
while (pos != -1) {
subseq.push_back(a[pos]);
pos = p[pos];
}
reverse(subseq.begin(), subseq.end());
return subseq;
}
부분 수열을 복원하는 다른 방법¶
보조 배열 $p[]$ 없이 부분 수열을 복원하는 것도 가능합니다. $d[i]$의 현재 값을 다시 계산하면서 최댓값이 어떻게 얻어졌는지도 확인하면 됩니다.
이 방법은 코드가 조금 더 길어지지만, 그 대가로 메모리를 약간 절약할 수 있습니다.
동적 계획법과 이진 탐색을 이용한 $O(n \log n)$ 풀이¶
이 문제를 더 빠르게 풀기 위해, $O(n^2)$에 동작하는 다른 동적 계획법 풀이를 구성한 뒤 나중에 이를 $O(n \log n)$으로 개선합니다.
동적 계획법 배열 $d[0 \dots n]$을 사용하겠습니다. 이번에는 $d[l]$이 원소 $a[i]$나 배열의 접두사에 대응하지 않습니다. $d[l]$은 길이가 $l$인 증가 부분 수열이 끝나는 원소 중 가장 작은 원소가 됩니다.
처음에는 $d[0] = -\infty$로, 나머지 모든 길이에 대해서는 $d[l] = \infty$로 둡니다.
이번에도 수를 먼저 $a[0]$, 그다음 $a[1]$과 같은 순서로 하나씩 처리하며, 각 단계에서 배열 $d[]$가 최신 상태를 유지하도록 합니다.
Example
배열 $a = \{8, 3, 4, 6, 5, 2, 0, 7, 9, 1\}$이 주어졌을 때, 모든 접두사와 각각의 동적 계획법 배열은 다음과 같습니다. 배열의 값이 항상 끝에서만 바뀌는 것은 아니라는 점에 주목하십시오.
$a[i]$를 처리할 때 다음과 같이 스스로 질문해 볼 수 있습니다. 현재 수 $a[i]$를 $d[0 \dots n]$ 배열에 기록하려면 어떤 조건이 성립해야 합니까?
$a[i]$에서 끝나는 길이 $l$의 최장 증가 수열이 존재하고, 더 작은 수에서 끝나는 길이 $l$의 최장 증가 수열이 존재하지 않으면 $d[l] = a[i]$로 설정합니다. 앞의 접근법과 마찬가지로, 길이 $l$의 최장 증가 수열에서 수 $a[i]$를 제거하면 길이 $l -1$의 또 다른 최장 증가 수열을 얻습니다. 따라서 길이 $l - 1$의 최장 증가 수열을 수 $a[i]$로 확장하려고 하며, 가장 작은 원소로 끝나는 길이 $l - 1$의 최장 증가 수열, 다시 말해 원소 $d[l-1]$에서 끝나는 길이 $l-1$의 수열이 가장 적합하다는 것은 분명합니다.
수 $a[i]$로 확장할 수 있는 길이 $l - 1$의 최장 증가 수열은 정확히 $d[l-1] < a[i]$일 때 존재합니다. 따라서 각 길이 $l$을 순회하면서 이 조건을 확인하여 길이 $l - 1$의 최장 증가 수열을 확장할 수 있는지 검사하면 됩니다.
또한 끝에 더 작은 수가 오는 길이 $l$의 최장 증가 수열을 이미 찾았는지도 확인해야 합니다. 따라서 $a[i] < d[l]$일 때만 갱신합니다.
$a[]$의 모든 원소를 처리한 후, 구하려는 부분 수열의 길이는 $d[l] < \infty$를 만족하는 가장 큰 $l$입니다.
$\pm\infty$ 패딩은 점화식을 서술하기 위한 편의일 뿐이며, 실제로 저장할 필요는 전혀 없습니다. 아래 구현들에서는 실제로 달성된 길이에 대한 항목만 유지합니다. 그러면 $d[]$는 한 단계마다 최대 한 원소씩 늘어나고, 그 끝을 넘어선 위치에 도달하는 것이 곧 $d[l] = \infty$가 의미하던 바이며, 답은 단순히 그 크기입니다.
int lis(vector<int> const& a) {
vector<int> d;
for (int x : a) {
size_t l = 0;
while (l < d.size() && d[l] < x)
l++;
if (l == d.size())
d.push_back(x);
else
d[l] = x;
}
return d.size();
}
이제 두 가지 중요한 관찰을 해 보겠습니다.
-
배열 $d$는 항상 정렬되어 있습니다: 모든 $l = 1 \dots n$에 대해 $d[l-1] < d[l]$입니다.
이는 자명합니다. 길이 $l$인 증가 부분 수열에서 마지막 원소를 제거하기만 하면, 더 작은 수로 끝나는 길이 $l-1$인 증가 부분 수열을 얻기 때문입니다.
-
원소 $a[i]$는 최대 하나의 값 $d[l]$만 갱신합니다.
이는 위의 구현에서 바로 따라 나옵니다. 배열에서 $d[l-1] < a[i] < d[l]$을 만족하는 위치는 단 하나뿐입니다.
따라서 이진 탐색을 사용하면 배열 $d[]$에서 이 원소를 $O(\log n)$에 찾을 수 있습니다. 사실 배열 $d[]$에서 $a[i]$보다 엄격하게 큰 첫 번째 수를 찾기만 하면 되고, 위의 구현과 같은 방식으로 이 원소의 갱신을 시도합니다.
구현¶
이로써 개선된 $O(n \log n)$ 구현을 얻으며, 이는 위의 구현과 위치를 찾는 방법만 다릅니다:
int lis(vector<int> const& a) {
vector<int> d;
for (int x : a) {
auto it = lower_bound(d.begin(), d.end(), x);
if (it == d.end())
d.push_back(x);
else
*it = x;
}
return d.size();
}
부분 수열 복원하기¶
이 접근법을 사용해서도 부분 수열을 복원할 수 있습니다. 간단한 방법은 두 개의 보조 배열을 유지하는 것입니다: 하나는 $d[]$의 각 위치를 $a[]$에서의 인덱스로 대응시키는 배열이고, 다른 하나는 $a[i]$로 끝나는 최적 부분 수열에서 이전 원소의 인덱스를 담는 "조상" 배열 $p[i]$입니다.
하지만 알고리즘이 이미 수행하는 이진 탐색의 부산물로 기록되는 보조 배열 $p[0 \dots n-1]$ 하나만 사용하여, 메모리를 더 효율적으로 쓰면서 부분 수열을 복원할 수 있습니다. $p[i]$를 $a[i]$가 최종적으로 놓이는 $d[]$에서의 위치로 정의하면, $a[i]$로 끝나는 최장 증가 부분 수열의 길이는 $p[i] + 1$이 됩니다.
이제 LIS의 길이가 $L$이라고 가정하고, $a[]$를 뒤에서부터 순회하면서 $p[i] = L - 1$인 마지막 원소를 고르고, 그다음 그보다 앞에 있는 $p[i] = L - 2$인 마지막 원소를 고르는 식으로 $p[i] = 0$까지 내려가 봅시다. 이렇게 고른 모든 원소는 직전에 고른 원소의 올바른 선행 원소입니다. 실제로, $p[j] = l + 1$인 $a[j]$를 이미 골랐다고 하고, $a[i]$를 그보다 앞에 있는 $p[i] = l$인 마지막 원소라고 합시다. $d[l]$은 항상 위치 $l$에 가장 최근에 놓인 원소를 담고 있으므로, $a[j]$가 처리되던 시점에 그 값은 $a[i]$와 같았습니다. 그리고 이진 탐색이 $a[j]$를 위치 $l + 1$에 놓은 것은 바로 $d[l] < a[j]$이기 때문이므로, $a[i] < a[j]$입니다.
이런 방식으로 원소들을 모은 뒤 마지막에 뒤집으면 최장 증가 부분 수열을 얻습니다.
vector<int> lis(vector<int> const& a) {
int n = a.size();
vector<int> d, p(n);
for (int i = 0; i < n; i++) {
auto it = lower_bound(d.begin(), d.end(), a[i]);
p[i] = it - d.begin();
if (it == d.end())
d.push_back(a[i]);
else
*it = a[i];
}
int l = d.size() - 1;
vector<int> subseq;
for (int i = n - 1; i >= 0 && l >= 0; i--) {
if (p[i] == l) {
subseq.push_back(a[i]);
l--;
}
}
reverse(subseq.begin(), subseq.end());
return subseq;
}
자료 구조를 사용한 $O(n \log n)$ 풀이¶
최장 증가 부분 수열을 $O(n \log n)$에 계산하는 위의 방법 대신, 몇 가지 간단한 자료 구조를 사용하는 다른 방식으로도 이 문제를 풀 수 있습니다.
첫 번째 방법으로 돌아가 봅시다. $d[i]$는 $j < i$이고 $a[j] < a[i]$인 $d[j] + 1$ 값이라는 것을 기억하십시오.
따라서 추가 배열 $t[]$를 다음과 같이 정의하면
값 $d[i]$를 계산하는 문제는 배열 $t[]$의 접두사에서의 최댓값을 찾는 문제와 동치가 됩니다:
(값이 변하는) 배열의 접두사 최댓값을 구하는 문제는 여러 가지 자료 구조로 풀 수 있는 표준적인 문제입니다. 예를 들어 세그먼트 트리나 펜윅 트리를 사용할 수 있습니다.
이 방법에는 분명히 몇 가지 단점이 있습니다. 구현의 길이와 복잡도 면에서 이 접근법은 이진 탐색을 사용하는 방법보다 좋지 않습니다. 또한 입력 수 $a[i]$가 특히 크다면 수를 압축하거나(즉, $0$부터 $n-1$까지 번호를 다시 매기거나) 동적 세그먼트 트리를 사용하는(트리에서 필요한 가지만 생성하는) 등의 기법을 써야 합니다. 그렇지 않으면 메모리 사용량이 너무 커집니다.
반면 이 방법에는 몇 가지 장점도 있습니다. 이 방법을 사용하면 동적 계획법 풀이의 까다로운 성질을 고민할 필요가 없습니다. 또한 이 접근법을 사용하면 문제를 매우 쉽게 일반화할 수 있습니다(아래 참조).
관련 문제¶
다음은 최장 증가 부분 수열을 구하는 문제와 밀접하게 관련된 몇 가지 문제입니다.
최장 비감소 부분 수열¶
이는 사실 거의 같은 문제입니다. 다만 이제는 부분 수열에 같은 수를 사용하는 것이 허용됩니다.
풀이도 본질적으로 거의 같습니다. 부등호를 바꾸고 이진 탐색을 약간 수정하기만 하면 됩니다.
최장 증가 부분 수열의 개수¶
처음에 다룬 방법을 사용할 수 있으며, $O(n^2)$ 버전과 자료 구조를 사용하는 버전 중 어느 것이든 괜찮습니다. 값 $d[i]$에서 끝나는 최장 증가 부분 수열을 얻는 방법이 몇 가지인지만 추가로 저장하면 됩니다.
$a[i]$에서 끝나는 최장 증가 부분 수열을 만드는 방법의 수는 $d[j]$가 최대인 $j$에서 끝나는 모든 최장 증가 부분 수열을 만드는 방법의 수를 모두 더한 값입니다. 그러한 $j$는 여러 개일 수 있으므로 이를 모두 더해야 합니다.
세그먼트 트리를 사용하면 이 접근법도 $O(n \log n)$에 구현할 수 있습니다.
이 문제에는 이진 탐색 접근법을 사용할 수 없습니다.
수열을 덮는 비증가 부분 수열의 최소 개수¶
$n$개의 수로 이루어진 배열 $a[0 \dots n - 1]$이 주어졌을 때, 각 색이 비증가 부분 수열을 이루도록 최소 개수의 색으로 수를 칠해야 합니다.
이를 풀기 위해, 필요한 색의 최소 개수가 최장 증가 부분 수열의 길이와 같다는 점에 주목합니다.
증명: 두 문제의 쌍대성을 증명해야 합니다.
최장 증가 부분 수열의 길이를 $x$로, 덮개를 이루는 비증가 부분 수열의 최소 개수를 $y$로 나타냅시다. $x = y$임을 증명해야 합니다.
$y < x$는 불가능함이 분명합니다. 순증가하는 원소가 $x$개 있다면 그중 어떤 두 원소도 같은 비증가 부분 수열에 속할 수 없기 때문입니다. 따라서 $y \ge x$입니다.
이제 귀류법으로 $y > x$가 불가능함을 보이겠습니다. $y > x$라고 가정합시다. 그러면 $y$개의 비증가 부분 수열로 이루어진 임의의 최적 집합을 생각합니다. 이 집합을 다음과 같이 변형합니다. 첫 번째 부분 수열이 두 번째 부분 수열보다 먼저 시작하고, 첫 번째 수열의 시작 수가 두 번째 수열의 시작 수보다 크거나 같은 두 부분 수열이 존재하는 한, 이 시작 수를 떼어 내어 두 번째 수열의 맨 앞에 붙입니다. 유한 번의 단계를 거치면 $y$개의 부분 수열이 남고, 이들의 시작 수는 길이가 $y$인 증가 부분 수열을 이룹니다. $y > x$라고 가정했으므로 모순에 도달합니다.
따라서 $y = x$가 성립합니다.
수열 복원하기: 원하는 대로 수열을 부분 수열로 분할하는 작업은 탐욕적으로 수행할 수 있습니다. 즉, 왼쪽에서 오른쪽으로 진행하면서 현재 수를, 현재 수보다 크거나 같은 수 중 가장 작은 수로 끝나는 부분 수열에 배정하십시오.