목차
LIS(Longest Increasing Subsequence)
Subsequence는 주어진 sequence에서 일부 원소를 제거해 얻을 수 있는 sequence입니다. 예를 들어, sequence $[1, 3, 2, 4, 6]$라 할 때 $[1, 3, 2, 4]$는 subsequence입니다. Subsequence는 원래 sequence의 순서를 유지해야 하지만, $[1, 2, 4]와 같이 연속적이지 않은 원소들로 이루어진 subsequence도 가능합니다.
LIS는 매우 유명한 동적 계획법 연습 문제 중 하나로, 주어진 sequence에서 가장 긴 증가하는 subsequence의 길이를 구하는 문제입니다. 이때 증가하는 subsequence는 원래 sequence에서 원소의 순서를 유지하면서, 각 원소가 이전 원소보다 크거나 같은 $[1, 3, 4, 6]$와 같은 subsequence를 말합니다.
완전 탐색
LIS 문제를 완전 탐색으로 풀 수 있습니다. sequence의 모든 부분 집합을 생성하고, 각 부분 집합이 증가하는 subsequence인지 확인하는 방식일 수도 있고, 또는 증가하는 모든 subsequence를 생성하고 가장 긴 subsequence를 찾는 방식일 수도 있습니다.
이 때 시간 복잡도는 $O(2^n)$이 됩니다.
모든 부분 집합을 생성하는 방법
#include <vector>
std::vector<std::vector<int>> generateSubsequences(const std::vector<int>& sequence, std::vector<int> current = {}, int index = 0) {
if (index == sequence.size()) {
return {current};
}
// 현 원소를 포함하지 않고 다음 원소로 넘어가는 경우
std::vector<std::vector<int>> subsequences = generateSubsequences(sequence, current, index + 1);
// 현 원소를 포함하고 다음 원소로 넘어가는 경우
current.push_back(sequence[index]);
std::vector<std::vector<int>> includeSubsequences = generateSubsequences(sequence, current, index + 1);
subsequences.insert(subsequences.end(), includeSubsequences.begin(), includeSubsequences.end());
return subsequences;
}
이런 뒤 각각의 부분 집합이 증가하는 subsequence인지 확인하고, 가장 긴 subsequence를 찾으면 됩니다. 이보다 간단한 방법은 다음과 같습니다.
증가하는 모든 subsequence를 생성하는 방법
#include <vector>
int LIS(const std::vector<int>& sequence, int index, std::vector<int>& current) {
if (index == sequence.size()) {
return 0;
}
int result = 0;
if (current.empty() || current.back() < sequence[index]) {
current.push_back(sequence[index]);
result = 1 + LIS(sequence, index + 1, current);
current.pop_back();
}
return std::max(result, LIS(sequence, index + 1, current));
}
위 알고리즘의 Time complexity는 $O(2^n)$입니다. 성능을 개선했어도 여전히 지수 시간 복잡도를 가지고 있기 때문에 큰 입력에 대해 사용하기 어렵습니다.
- $T(n) = 2T(n - 1) + O(1)$
- $T(n) = 2(2T(n - 2) + O(1)) + O(1) = 4T(n - 2) + 3O(1)$
- $T(n) = 4(2T(n - 3) + O(1)) + 3O(1) = 8T(n - 3) + 7O(1)$
- …
- $T(n) = 2^kT(n - k) + (2^k - 1)O(1)$
동적 계획법을 이용한 LIS
이 때 두 번째 해결책의 경우, 한 원소 이후의 LIS 중 가장 긴 subsequence를 구하는 문제가 반복되어 발생하고 있습니다. 이 때문에 overlapping subproblem이 발생하며, 이를 해결하기 위해 동적 계획법을 사용할 수 있습니다.
동적 계획법을 사용하면 시간 복잡도를 $O(n^2)$로 줄일 수 있습니다.
#include <vector>
#include <algorithm>
int LIS(const std::vector<int>& sequence, int index, std::vector<int>& cache) {
if (index == sequence.size()) {
return 0;
}
int& result = cache[index];
if (result != -1) {
return result;
}
result = 1;
for (int next = index + 1; next < sequence.size(); ++next) {
if (sequence[index] < sequence[next]) {
result = std::max(result, 1 + LIS(sequence, next, cache));
}
}
return result;
}
이 때 이 문제를 해결하기 위해서는 위에 작성한 함수를 다음과 같이 호출해야 합니다.
#include <vector>
int main() {
std::vector<int> sequence = {3, 1, 2, 4, 6};
std::vector<int> cache(sequence.size(), -1);
int result = 0;
for (int i = 0; i < sequence.size(); ++i) {
result = std::max(result, LIS(sequence, i, cache));
}
return 0;
}
마지막의 for loop을 생략하기 위해서는 다음과 같이 코드를 수정할 수 있습니다.
#include <vector>
#include <algorithm>
int LIS(const std::vector<int>& sequence, int index, std::vector<int>& cache) {
if (index == sequence.size()) {
return 0;
}
int& result = cache[index];
if (result != -1) {
return result;
}
result = 1;
for (int next = index + 1; next < sequence.size(); ++next) {
if (index == -1 || sequence[index] < sequence[next]) {
result = std::max(result, 1 + LIS(sequence, next, cache));
}
}
return result;
}
이 경우 main 함수는 다음과 같이 작성할 수 있습니다.
#include <vector>
int main() {
std::vector<int> sequence = {3, 1, 2, 4, 6};
std::vector<int> cache(sequence.size(), -1);
return LIS(sequence, -1, cache);
}
출처
- 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(구종만 저) p.230 ~ p. 235