안녕하세요, 여행벌입니다.
오늘은 대표적인 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) 시간 복잡도를 가지는 것을 확인할 수 있습니다.
'Computer Science > Algorithm' 카테고리의 다른 글
| [알고리즘] 비트마스킹(bitmasking) 이란 (2) | 2020.06.15 |
|---|---|
| [알고리즘] KMP : 문자열 검색 알고리즘 (0) | 2020.05.08 |
| [알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra) (0) | 2020.04.29 |
| [알고리즘] 트라이(Trie) 란 (0) | 2020.04.23 |
| [알고리즘] 깊이 우선 탐색(DFS)이란 (0) | 2020.04.06 |
