LIS

LIS(Longest Increasing Subsequence, 최장 증가 부분 수열)는 이름과 같이 주어진 수열에서 가장 긴 증가하는 부분 수열을 말한다. 아래에선 LIS와 기초적인 변형 문제들을 빠르게 해결하는 방법을 서술한다.

수식이 많은 것에 비해 엄밀하지 못하므로 주의.

아래에서 $A$ 는 주어진 수열이며, $M$ 은 $O(\max_{}{ A[i] } - \min_{}{ A[i] })$ 를 뜻한다.

기본형

$D[i] = \displaystyle\max_{ j < i \wedge A[j] < A[i] }{ D[j] }+1$

위는 아주 기본적인 형태의 점화식으로, 시간복잡도는 $O(N^2)$ , 공간복잡도는 $O(N)$ 이다. 이를 $O(NlgN)$ 으로 줄이는 방법은 여러 가지가 있으며, 가장 떠올리기 쉬운 방법으론 펜윅 트리가 있다.

덤으로 수열 $A$ 를 원소들의 부호를 반전시킨 뒤 LIS를 구하면 원래 수열의 LDS가 나온다. 수열을 뒤집고 LDS를 구하면 원래 수열의 LIS가 나온다.

펜윅 트리

위 점화식에서 $max_{}{}$ 를 $O(N)$ 에 구하는 대신, 펜윅 트리로 $O(lgN)$ 에 구할 수 있다. $[0, A[i])$ 범위에 있는 $D[j]$ 중 가장 큰 값을 구하고, 거기에 $+1$ 을 하여 트리의 $A[i]$ 위치에 업데이트하는 식이다.

시간복잡도는 $O(NlgM)$ 이며, 공간복잡도는 $O(N+M)$ 이다. C++ 구현은 다음과 같다.

int mini = *min_element(begin(A), end(A)) - 1;
int maxi = *max_element(begin(A), end(A));
vector<int> D(N);
vector<int> T(maxi - mini);
for(int i = 0; i < N; i++) {
	for(int j = A[i] - mini; j; j -= j&-j)
		D[i] = max(D[i], T[j]);
	D[i]++;
	for(int j = A[i] - mini; j < T.size(); j += j&-j)
		T[j] = max(T[j], D[i]);
}
return D.back();

적당히 깔끔하고 활용성도 높지만 펜윅 트리를 알아야 하며, $A[i]$ 의 값이 크다면 좌표압축이나 동적 세그먼트 트리를 필요로 하게 되므로 다른 방법이 나을 수 있다.

이분탐색

$D[i]$ , 즉 i를 끝으로 하는 LIS의 길이는 당연하게도 항상 $i$ 이하이다. 그렇다면 값이 커질 수 있는 $A[i]$ 대신 항상 $N$ 이하임이 보장되는 $D[i]$ 를 인덱스로 잡으면 어떨까? 다음 조건을 만족하는 수열 $B$ 를 생각해 보자.

$B[k] = \displaystyle\min_{ D[i]=k }{ A[i] }$

$B[k] < B[k+1]$

초기에 $B$ 가 빈 수열일 때 위 조건을 만족함은 자명하다.

이제 $D[i]$ 를 구해야 하는데, 처음으로 $A[i] \leq B[k]$ 가 되는 $k$ 를 찾으면 된다. $B$ 가 순증가하므로 이분탐색을 사용할 수 있으며, $D[i] = k$ 임은 어렵지 않게 보일 수 있다.

따라서 $B[k]$ 를 $A[i]$ 로 업데이트해야 하고, $B[k-1] < A[i] \leq B[k]$ 이므로 위의 속성들을 여전히 만족한다.

시간복잡도는 $O(NlgN)$ 이며, 공간복잡도는 $O(N)$ 이다. C++ 구현은 다음과 같다.

vector<int> B;
for(int x : A) {
	auto it = lower_bound(begin(B), end(B), x);
	if(it == end(B)) B.push_back(x);
	else *it =  x;
}
return B.size();

더 짧게는 아래처럼도 가능하다. INF는 매우 큰 값을 의미하며, INT_MAX 등으로 잡아주면 된다.

vector<int> B(N, INF);
for(int x : A) *lower_bound(begin(B), end(B), x) = x;
return find(begin(B), end(B), INF) - begin(B);

또한, 위 코드들에서 lower_bound 대신 upper_bound를 사용한다면 증가 수열 대신 단조 증가 수열을 구할 수 있다.

정리

$O(NlgN)$ 에 LIS를 구하는 두 방법을 알아봤다. 둘 중 어느 게 나은지는 상황에 따라 다르기 때문에, 문제마다 적절히 활용하는 것이 좋을 것이다.

이제 이를 응용해서 여러 문제들을 풀어보자.

Pair LIS

두 순서쌍에 대해 $(a, b) < (c, d)$ 는 $a < c \wedge b < d$ 라 정의하자. 이 때 순서쌍의 열인 $A$ 의 LIS를 구해야 한다.

변수가 하나 늘었기 때문에 어떻게 해야 하나 싶지만, 위의 방법을 단순히 응용하는 것으로 풀 수 있다.

펜윅 트리 / 동적 세그먼트 트리

하나는 단순히 펜윅 트리에서 차원을 하나 늘린, 2D 펜윅 트리를 사용해 문제를 푸는 것이다. 시간복잡도는 $O(Nlg^2M)$ 이며, 공간복잡도가 $O(N+M^2)$ 이다.

공간복잡도가 매우 크기 때문에 동적 세그먼트 트리가 사실상 강제된다. 이 경우 시간복잡도와 공간복잡도는 $O(Nlg^2M)$ 인데, 상수가 상당히 크기 때문에 다른 방법을 사용하는 게 권장된다.

이분탐색 응용

기존에 이분탐색을 위해 정의했던 $B$ 를 다시 생각해 보자.

$B[k] = \displaystyle\min_{ D[i]=k }{ A[i] }$

$B[k] < B[k+1]$

이는 순서쌍에 대해서도 동일하게 적용할 수 있다. 단 집합이나 순서쌍 간의 비교 연산을 적절히 정의해 주어야 하고, 사소한 차이점들도 있다. 그림을 직접 그려보면서 이해하면 편할 것 같다.

우선 순서쌍 간의 비교는 위에서 정의한 것과 같다. 이로 인해 최솟값이 하나가 아닐 수가 있는데, $(a, b)$ 와 $(c, d)$ 가 $a < c \wedge b \geq d$ 이거나 $a \geq c \wedge b < d$ 인 경우이다. 때문에 $B[k]$ 는 최솟값 하나가 아닌 이들의 집합이 된다.

또한 이로 인해 순서쌍의 두 값 중 어느 하나를 기준으로 오름차순 정렬을 하면, 다른 하나는 내림차순이 되는 것 역시 알 수 있다.

집합 $B[j]$ 의 모든 순서쌍 $(c, d)$ 에 대해 집합 $B[i]$ 의 어떤 순서쌍 $(a, b)$ 가 $(a, b) < (c, d)$ 를 만족하면 $B[i] < B[j]$ 라 하자.

그리고 집합 $B[i]$ 의 어떤 순서쌍 $(c, d)$ 가 $(c, d) < (a, b)$ 라면 $B[i] < (a, b)$ 이고, 그렇지 않으면 $(a, b) \leq B[i]$ 라 하자.

$D[i]$ 를 구하는 건 기존과 마찬가지로, 처음으로 $A[i] \leq B[k]$ 가 되는 $k$ 를 찾으면 된다.

$B[k]$ 에 $A[i]$ 를 업데이트할 때는, 우선 집합에 추가한 뒤 $A[i]$ 보다 큰 순서쌍들을 모두 지워줌으로써 최솟값들을 유지할 수 있다. 순서쌍들이 정렬되어 있을 때 이런 것들은 연속해서 존재하므로 빠르게 구할 수 있고, $B[k-1] < A[i] \leq B[k]$ 이니 위의 속성들을 여전히 만족한다.

아래는 이를 활용하여 조화로운 행렬 문제를 푸는 C++ 구현이다. 거의 설명 그대로 코드로 옮겼으며, Set 구조체를 제외하면 기존 LIS와 같기 때문에 눈여겨볼 점은 없다.

#include <bits/stdc++.h>
using namespace std;

struct pii {
	int x, y;
	bool operator<(const pii& b) const {
		return x < b.x;
	}
};
struct Set {
	set<pii> S;
	bool operator<(const pii& b) const {
		auto it = S.lower_bound(b);
		return it != S.begin() && (--it)->y < b.y;
	}
	void add(const pii& a) {
		auto it = ++S.insert(a).first;
		while(it != end(S) && a.y < it->y)
			it = S.erase(it);
	}
};

int main() {
	ios::sync_with_stdio(0);
	int M, N;
	cin >> M >> N;

	if(M == 2) {
		vector<pii> A(N);
		for(auto& [x, y]:A) cin >> x;
		for(auto& [x, y]:A) cin >> y;
		sort(begin(A), end(A));

		vector<int> B;
		B.reserve(N);
		for(auto [x, y] : A) {
			auto it = lower_bound(begin(B), end(B), y);
			if(it == end(B)) B.push_back(y);
			else *it =  y;
		}

		cout << B.size() << endl;
		return 0;
	}

	vector<pair<int, pii>> A(N);
	for(auto& [x, a] : A) cin >> x;
	for(auto& [x, a] : A) cin >> a.x;
	for(auto& [x, a] : A) cin >> a.y;
	sort(begin(A), end(A), [&](const auto& a, const auto& b) {
		return a.first < b.first;
	});

	vector<Set> B;
	B.reserve(N);
	for(auto [x, a] : A) {
		auto it = lower_bound(begin(B), end(B), a);
		if(it == end(B)) B.push_back({{ a }});
		else it->add(a);
	}
	cout << B.size() << endl;
}

분할정복

2D 세그먼트 트리를 사용하는 오프라인 문제는 분할정복으로도 해결할 수 있다고 한다. 나중에 배우면 추가할 예정

LIS의 개수

추가 예정.

K번째 LIS