[알고리즘] DP(Dynamic Programming) - LIS

안녕하세요, 여행벌입니다.

오늘은 대표적인 DP 문제 LIS에 대해서 포스팅해보겠습니다.

---

LIS ( Longest Increasing Subset )

 LIS는 이름 그대로 증가 부분 수열 중에서 가장 긴 부분 수열을 찾아내는 문제입니다.

 예를 들어, { 1 4 2 3 5 7 9 10 } 이 있다고 해봅시다.

 부분 수열이란 { 4 3 9 10 } 과 같이 수열에서 0개 이상의 숫자를 지우고 남은 수열을 말합니다.

 그 중, 증가 부분 수열이란 부분 수열의 원소들이 증가하고 있는 상태를 유지하는 것을 말합니다.

 { 1 2 3 5 7 9 } , { 4 5 7 9 10 } 등이 부분 증가 수열입니다.

  어떻게 증가 부분 수열 중 가장 길이가 긴 수열을 찾을 수 있을까요??

1) 완전 탐색

 가장 쉬운 방법은 모든 부분 증가 수열을 찾아보고, 그 중 가장 길이가 긴 수열을 찾는 방법입니다. 수열의 모든 부분에서 시작해서 모든 증가 수열을 DFS 탐색을 하듯이 탐색할 수 있습니다.

#include<vector>
#include<algorithm>

using namespace std;

int LIS(vector<int> A) {
	if (A.size() == 0) return 0;
	int ans = 0;
	for (int i = 0; i < A.size(); i++) {
		vector<int> B;
		// 시작점인 i보다 큰 애들을 다 입력하고 이어서 진행해본다.
		for (int j = i + 1; j < A.size(); j++)
			if (A[i] < A[j])
				B.push_back(A[j]);
		ans = max(ans, 1 + LIS(B));
	}
}

 다음과 같이 재귀적으로 코드를 구현할 수 있습니다.

 예를 들어 { 3, 1, 2, 5, 4 } 수열이 있다면, 다음과 같은 증가 부분 수열이 있습니다.

 { 3, 5 } / { 3, 4 } / { 1, 2 } / { 1, 2, 5 } / { 1, 2, 4 } / { 2, 5 } / { 2, 4 } / { 5 } / { 4 }

 이런 모든 경우의 수를 다 계산해서 가장 큰 값을 return 해주면 LIS 를 구할 수 있습니다. 완전 탐색이므로 당연히 굉장히 좋지 않은 시간 복잡도를 가지게 됩니다.

2) O(N^2) 시간 복잡도를 가지는 알고리즘

 메모리제이션을 이용하면 더 괜찮은 알고리즘을 구현할 수 있습니다.

 길이가 N인 수열이 있을 때,

 Dp[K] := (0 ~ K번 째 원소) 부분 수열 중 가장 큰 증가 부분 수열의 길이 라고 해보겠습니다

int LIS(vector<int> A) {
	int N = A.size();
	vector<int> Dp(N);
	Dp[0] = 1; 
	for (int i = 1; i < N; i++) {
		int m = 0;
		for (int j = 0; j < i; j++)
			if (A[j] < A[i])
				m = max(m, Dp[j]);
		Dp[i] = m + 1;
	}
	int ans = 0;
	for (int i = 0; i < N; i++)
		ans = max(ans, Dp[i]);
	return ans;
}

list =  { 3, 1, 2, 5, 4 } 수열을 생각해보겠습니다.

Dp[0] := { 3 } 에서 얻을 수 있는 가장 큰 증가 부분 수열의 길이이므로 1이 됩니다.

Dp[1] := { 3, 1 } 에서 가장 큰 증가 부분 수열의 길이이므로 1이 됩니다.

Dp[2] := { 3, 1, 2 } 에서 얻을 수 있는 가장 큰 증가 부분 수열의 길이이므로 2가 됩니다.

Dp[3] := { 3, 1, 2, 5 } 에서얻을 수 있는 가장 큰 증가 부분 수열의 길이이므로 3이 됩니다.

Dp[4] : = { 3, 1, 2, 5, 4 } 에서  얻을 수 있는 가장 큰 증가 부분 수열의 길이이므로 2가 됩니다.

 

 Dp 배열은 정의에 의해 다음과 같은 점화식이 성립합니다.

 Dp[K] := max(Dp[i], where 0 <= i < K and list[i] < list[K] ) + 1

 Dp[K]는 기존에 구한 가장 긴 증가 부분 수열에 list[K]를 뒤에 이어서 만들 수 있습니다. 따라서, list[K] 보다 값이 작아서 list[K]를 뒤에 이을 수 있는 증가 부분 수열 중에서 Dp 값이 가장 큰 값( 가장 길이가 긴 수열 )을 찾으면 Dp[K] 를 구할 수 있습니다.

 

 이중포문으로 Dp 배열을 채울 수 있으므로 O(N^2) 복잡도로 해결할 수 있습니다. 완전탐색보다는 많이 개선되었지만, 아직 N이 조금만 커져도 계산이 어렵다는 것을 알 수 있습니다.

3) O(NlogN) 시간 복잡도를 가지는 알고리즘

 Dp 배열의 정의를 조금 바꾸고, Binary Search를 이용해 Dp 배열을 채워나가면 훨씬 더 좋은 알고리즘을 구현할 수 있습니다.

 

 Dp[ x ] := 길이가 x 인 증가 부분 수열 중 가장 작은 마지막 값 이라고 정의하겠습니다.

 

 예를 들어, [ 4 2 6 3 1 5 ] 에서 길이가 2인 증가 부분 수열은 4 - 6 / 4 - 5 / 2 - 6 / 2 - 3 / 2 - 5 / 3 - 5 / 1 - 5 처럼 여러가지가 있지만, 이 중 가장 작은 마지막 값은 3이므로 Dp[2] = 3 이 된다.

 

 이때, Dp 배열은 항상 증가 상태를 유지합니다. 왜냐하면, Dp[1] 은 길이가 1인 가장 작은 마지막 값이고, Dp[2] 는 Dp[1] 의 원소에 더 큰 원소를 이어서 얻은 값이고, Dp[3] 은 Dp[2] 의 원소에 더 큰 원소를 이은 값이기 때문입니다. 따라서, 우리는 Dp 배열에 대해서 Binary_Search 를 이용할 수 있고, 시간 복잡도를 O(NlogN) 으로 줄일 수 있습니다.

 

 지금 알고 있는 가장 큰 증가 부분 수열의 길이가 k이고 Dp[k] 까지 알고 있다고 해보겠습니다. 다음에 순회하는 원소가 Dp[k] 보다 크다면, 지금 구한 가장 큰 증가 부분 수열의 뒤에 원소를 이을 수 있으므로, Dp[k + 1] 을 갱신할 수 있습니다. 아니라면, 순회하는 원소를 Binary_Search를 이용해 Dp[1] ~ Dp[k] 중에 적절한 위치에 갱신을 하면 됩니다. 

int LIS(vector<int> v) {
	int N = v.size();
	vector<int> Dp(N + 1, INF);
	int longest = 1;
	Dp[0] = -INF;
	Dp[1] = v[0];
	for (int cur : v) {
		if (Dp[longest] < cur) {
			longest++;
			Dp[longest] = cur;
		}
		else {
			vector<int>::iterator it = lower_bound(Dp.begin(), Dp.end(), cur);
			*it = cur;
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++)
		if (Dp[i] != INF) ans = i;
	return ans;
}

 배열의 길이가 N일 때, 최대 증가 부분 수열의 길이는 N이므로 Dp 배열의 크기는 (N + 1) 이 되고, 초기화는 INF 로 초기화해둡니다. Dp[ 0 ] 은 길이가 0인 증가 부분 수열이므로 존재하지 않고, 이분 탐색을 위해 Dp[0] = -INF 로 초기화해두겠습니다. Dp[1] 은 길이가 1인 증가 부분 수열이므로 일단은 v[0] 으로 채워둡니다. longest는 현재 찾은 가장 긴 증가 부분 수열의 길이라고 하겠습니다.

 

 배열의 원소들을 앞에서부터 순회하며 현재 찾은 가장 긴 증가 부분 수열의 마지막 값인 Dp[longest] 보다 큰 값이라면 가장 긴 증가 부분 수열의 뒤에 값을 이어서 LIS 를 만들 수 있으므로, longest는 1 증가하고, Dp 값을 갱신할 수 있습니다. 아니라면, 현재 순회 중인 원소를 Binary_Search를 통해서 Dp 배열을 갱신하면 됩니다.

 

 예를 들어, { 3, 1, 4, 2, 5, 6 } 이 있다고 하겠습니다.

순서	DP[0]	DP[1]	DP[2]	DP[3]	DP[4]	DP[5]	DP[6]
초기값	-INF	3	INF	INF	INF	INF	INF
1) 3을 순회	-INF	3	INF	INF	INF	INF	INF
2) 1을 순회	-INF	1	INF	INF	INF	INF	INF
3) 4를 순회	-INF	1	4	INF	INF	INF	INF
4) 2를 순회	-INF	1	2	INF	INF	INF	INF
5) 5를 순회	-INF	1	2	5	INF	INF	INF
6) 6을 순회	-INF	1	2	5	6	INF	INF

 N개의 원소를 순회하면서, Binary_Search를 진행하므로 O(NlogN) 시간 복잡도를 가지는 것을 확인할 수 있습니다.

---