Lis

개요

Longest Increasing Subsequence (최장 증가 부분수열) 은 자주 나오는 문제고 비슷한 문제가 이걸로 쉽게 환원이 되어 Well Known Problem 중 하나임.

푸는 방법이 크게 3가지로, 하나는 DP 이고 하나는 Binary Search 를 응용한 방법, 다른 하나는 Segment Tree 를 응용한 방법임.

DP

문제

가장 긴 증가하는 부분 수열

코드1

int inputs[1001];
int dp[1001]; // i 로 끝을 낼 때 최대 길이를 저장

int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> inputs[i];

	for (int i = 0; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (inputs[j] < inputs[i])
				dp[i] = max(dp[i], dp[j] + 1);
	}

	int ans = -1;
	for (int i = 0; i < n; i++)
		ans = max(ans, dp[i]);
	cout << ans;
}

시간 복잡도

O(\(\mathrm{N}^2\))

설명

가장 정석적인 방법이다.

dp[i] 는 i 번째 수열값을 끝으로 가지는 LIS 의 길이가 된다.

코드2

int inputs[1001];
pair<int, int> dp[1002]; // dp[i] => i보다 작은 수로만 LIS 를 구성. {end_value, length}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> inputs[i];
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < 1002; j++)
		{
			if (inputs[i] >= j) continue; // dp[j] 는 j 보다 크거나 같은 수는 못넣음

			if (dp[j].first < inputs[i]) // 마지막수보다 큰 수가 나오면 추가함
			{
				dp[j].first = inputs[i];
				dp[j].second++;
			}
			else if (dp[j].second <= dp[inputs[i]].second + 1) // inputs[j] 보다 작은 수로 만든 수열 + inputs[i] 가 가능한지 체크
			{
				dp[j].first = inputs[i];
				dp[j].second = dp[inputs[i]].second + 1;
			}
		}
	}
	
	cout << dp[1001].second;
}

시간 복잡도

O(\(NM\))

설명

dp[i] 는 i 보다 작은 수로만 이루어진 LIS 정보{마지막값(수열의 최댓값), 수열의 길이} 를 저장한다.

수의 범위가 작고, 배열의 위치가 아니라 포함하는 수의 크기에 제한이 있는 경우 사용할 수 있다.

Binary Search

문제

가장 긴 증가하는 부분 수열 5

코드

#define MAX_LINE 1000001
int inputs[MAX_LINE], indices[MAX_LINE];
int lis[MAX_LINE], cnt = 0;
int ans[MAX_LINE];

int main()
{
	int n;
	cin >> n;

	// LIS 업데이트
	for (int i = 0; i < n; i++) cin >> inputs[i];
	for (int i = 0; i < n; i++)
	{
		int * p;
		p = lower_bound(lis, lis + cnt, inputs[i]);
		*p = inputs[i];
		if (p - lis == cnt) cnt++;
		indices[i] = p - lis;
	}
	for (int i = n-1, p = cnt -1; i >= 0; i--)
		if (indices[i] == p)
			ans[p--] = inputs[i];
	
	cout << cnt << '\n';
	for (int i = 0; i < cnt; i++)
		cout << ans[i] << ' ';
}

시간 복잡도

O(nLogN)

설명

길이 구하기

우선 LIS 라는 순열을 저장할 배열을 만듬.

• 이 배열에 input 값을 넣는데, binary search 를 이용해 적당한 위치에 넣게 함.
• 그러면 LIS 배열의 크기는 최대 증가 부분수열이 길이가 됨 .

값 추적하기

LIS 배열에는 우리가 원하는 값이 들어있을 수 없음

• 2 3 1 4 이 왔다면 LIS 가 1 3 4 가 들어있어 2 3 4 와 다름

위와 같이 LIS 가 오염되는 경우는 LIS 가 중간에 업데이트 되는 경우임

• 이를 LIS 의 Index 로 나타내면 0 1 0 2 가 됨.
• 이는 뒤에서부터 차례대로 LIS 의 Index 가 줄어드는 대로 가져오면 해결됨.
• 이때 가장 최신값을 사용해야하는데, 가장 최신 값을 바탕으로 LIS 가 작성되기 때문임.

Segment Tree

코드

시간 복잡도

asdf