[백준 11053 / 백준 12015] 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence) - 1

백준에서 문제를 풀어보다가 LIS 시리즈물들이 있길래 이 김에 공부할 겸 정리도 한번 해보려고 합니다.

PS 분야에서는 꽤나 유명한, 매우 well-known한 주제이기도 합니다.

 

백준에는 무려 6문제나 있지요. 사실 뒤에 숫자는 레벨이라고 봐도 됩니다. 고로 2번 문제 난이도 < 3번 문제 난이도 < 4번 문제 난이도... 뭐 이런식이지요.

 

백준 11053번 문제 "가장 긴 증가하는 부분 수열"

https://www.acmicpc.net/problem/11053

문제부터 한번 보겠습니다. 첫번째 문제입니다.

 

최장 증가 부분 수열

일단 Longest Increasing Subsequence가 무엇인지를 좀 알고 넘어가면 좋을 듯 합니다.

사실 부분수열이면 subsequence이지요. 그렇다면 수열은 sequence라고 보시면 됩니다.

 

subsequence라고 하는 녀석은 연속되지 않아도 됩니다. 이 부분이 간단하지만 핵심적인 내용인데, (반면 substring은 연속되어야 합니다.)

위 문제에서 예시를 보면, 10 20 30 50이 최장 증가수열입니다.

 

하지만 원본 배열에서는 20과 30 사이에 10이 들어있어서 20과 30은 연속되지 않습니다. 그래도 subsequence가 맞다는 것이지요.

 

그러면 길이가 N인 배열의 subsequence의 개수는 //(2^N//)개가 되겠네요. 각각의 원소가 부분 수열에 포함되거나, 그렇지 않거나 하니깐요.

 

그러므로 Brute force로 문제를 풀려고 한다면 당연히 시간 복잡도는 //(O(2^N)//)가 나오게 됩니다.

 

문제에서 주어진 //(N=1000//)이므로 완전탐색으로는 풀 수 없겠지요.

 

그렇다면 어떻게 풀 수 있을까요?

 

동적 계획법 풀이 (Dynamic Programming)

LIS는 유명한 동적계획법 문제 중 하나이기도 합니다. 1차원 다이나믹 프로그래밍으로 //(O(N^2)//)의 시간복잡도로 문제를 해결할 수 있습니다.

 

간단하게 점화식을 새운 뒤 부분 문제들을 풀면 됩니다.

 

헌데 문제 특성 상, 부분 문제인 이미 만든 Subsequence들을 저장을 해야 하는데, 리스트 형태로 되어 있으면 다루기가 힘들지요.

 

그래서 subsequence의 마지막 값만을 이용해서 점화식을 정합니다.

 

//(dp[i]//)는 //(i//)번째 원소를 부분 수열의 마지막으로 하는 수열 중 가장 긴 수열의 길이

로 정의합니다.

 

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

int dp[1001]; //dp[i] -> i번째 값을 마지막으로 하는 subsequence중 가장 긴 녀석의 길이
int arr[1001];
int main() {
    int n;
    cin >> n;
    for (int i=0; i< n; i++) {
        cin >> arr[i];
        dp[i] = 1; //길이가 1인 경우로 초기화
    }
    for (int i=0; i < n; i++) {
        int& last_val = arr[i];
        for (int j=0; j < i; j++) {
            int& target_val = arr[j];
            if (last_val > target_val) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int ans = 0;
    for (int i=0; i<n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
	return 0;
}

 

위와 같이 구현해서 1번문제를 가볍게 풀 수 있습니다.

 

백준 12015번 문제 "가장 긴 증가하는 부분 수열 2"

그러면 다음 문제를 한번 보도록 합시다.

https://www.acmicpc.net/problem/12015

 

이전 문제와 달라진 점은 N의 크기 뿐입니다. N이 100만이 되었으니, 기존의 //(O(N^2)//)의 알고리즘으로는 시간 내에 풀이가 힘들게 되었습니다.

 

좀 더 효율적인 알고리즘이 있을까요?

 

NlgN 풀이 - 바이너리 서치

//(O(NlgN)//)의 시간복잡도를 갖는 LIS 풀이로 2가지가 있는 것으로 알고 있는데, 하나는 세그먼트 트리를 이용한 방법이고 다른 하나는 이번에 다루어볼 바이너리 서치를 활용한 방법입니다.

 

아이디어

일단 배열 A = {2, 5, 3}이라고 가정해봅시다.

그러면 LIS가 2개가 나옵니다.

{2, 5}와 {2, 3}이지요.

 

그러면 여기서 A배열 뒤에 7과 11이 추가된다고 생각해보겠습니다. 그러면 A = {2, 5, 3, 7, 11}이 됩니다.

 

그리고 이렇게 새로 추가된 7과 11 덕에 기존의 LIS도 더 길어지게 됩니다.

{2, 5} => {2, 5, 7, 11}

{2, 3} => {2, 3, 7, 11}

 

이러한 식으로 알고리즘이 전개됩니다. 여기에 A 배열 마지막에 8이 추가된다면 어떻게 될까요?

A = {2, 5, 3, 7, 11, 8}이 되는데, 요 8녀석이 기존에 알려진 LIS들 사이에 끼일 수 있을까요?

7과 11은 기존 LIS의 마지막 값 보다 명백히 큰 값이라서 그냥 뒤에다가 붙이면 된다는게 확실한데, 8은 마지막 값인 11보다 작습니다.

 

그러면 이 8이라는 녀석을 버려야할까요?

 

LIS에서 그리디한 성질

사실 이런 경우 11을 8로 바꾸는 경우가 무조건 더 좋습니다.

 

일단 수열이 여기서 끝난다고 하면, {2,3,7,11}이나 {2,3,7,8}이나 Increasing subsequence의 길이는 둘 다 같습니다.

 

이후 뒤에 어떤 수가 더 온다고 한 들, 8로 끝난 경우가 11로 끝난 경우보다 더 긴 수열을 만드는데 있어서 유리하거나 같습니다.

 

일단 당장 뒤에 오는 숫자의 범위를 3가지로 나누어 보겠습니다.

 

1) 11보다 큰 수가 오는경우, 

2) 9이상 11이하의 수가 오는 경우

3) 8이하의 수가 오는 경우.

 

1번 11보다 큰 수가 오는 경우, 8로 끝난 수열이나 11로 끝난 수열이나 둘 다 취할 수 있습니다.

예를 들어 이후 13이 온 경우

{2,3,7,11,13}과 {2,3,7,8,13}이 가능한데, 둘 다 같은 길이에 마지막 수가 13으로 끝나는 수열이 됩니다.

 

2번 9이상 11이하의 수가 오는 경우 8로 끝난 수열은 길이가 1추가되는데, 11로 끝난 수열은 길이를 추가할 수가 없습니다. 또한 마지막 수가 11이하의 수 이므로 기존 11로 끝난 수 보다 무조건 유리합니다.

 

3번 8이하의 수의 경우는 둘 다 수열을 연장할 수 없으니 두개의 수열 모두 추가 수를 취할 수 없으니, 상관이 없지요.

 

따라서 같은 길이라면 마지막 수가 작을 수록, 이후에 더 긴 수열을 만들기 위해서는 더 유리하다고 볼 수 있습니다. 이러한 점에선 LIS가 그리디한 성질을 만족한다고 할 수 있겠습니다.

 

"수열의 마지막 수가 작을수록 더 긴 LIS를 만드는데 유리하다" 고 볼 수 있겠습니다.

 

이러한 점으로 다음과 같은 알고리즘을 한번 만들어 볼 수 있습니다.

알고리즘 설계

가장 긴 증가부분수열이 될 수 있는 녀석들을 Active list라고 부르도록 하겠습니다.

Increasing subsequence들 몇개들을 가지고 있으면서, longest가 될 수 있는 녀석을 알아내는 것인데,

위에서 알아낸 Greedy한 성질로 전체를 다 만들지 않고 추려낼 수가 있습니다.

 

같은 길이의 Increasing subsequence라면, 마지막 수가 가장 작은 녀석 하나만 알고 있어도 Longest IS를 구할 수 있다는 점입니다.

물론 i값을 0부터 N-1까지 증가시켜가면서 만드는 것이기 때문에 위치에 따른 dependency도 체크를 할 수있습니다.

 

알고리즘은 다음과 같습니다.

 

1. 만약 //(A[i]//)가 모든 Active list의 마지막 수 보다 작다면, 길이 1짜리 Active list를 하나 만든다.

2. 만약 //(A[i]//)가 모든 Active list의 마지막 수 보다 크다면, 가장 긴 Active list를 하나 복붙을 한 뒤, 마지막에 //(A[i]//)를 붙인다.

3. 만약 //(A[i]//)가 Active list 마지막 수들 중 가장 작은녀석 보다는 크고, 가장 큰 녀석 보다는 작다면, Active list 마지막 수 들 중에서 //(A[i]//)보다는 작은 녀석 중 가장 큰 리스트를 골라서, 그 리스트의 복사본 뒤에 //(A[i]//)를 붙인다.

 

끝까지 진행한 뒤, Active list중 가장 긴 녀석의 길이가 LIS의 길이가 됩니다.

 

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

위에 있는 수열로 위 알고리즘을 진행해보면, 아래와 같이 나옵니다. geeksforgeeks 블로그의 값을 그대로 긁어왔습니다.

 

 

 

위와 같이 진행이 됩니다.

 

그러면 이 Active List들을 잘 가지고 있어야 하는데 어떤식으로 구현을 하면 좋을까요?

 

구현 전략

 

NlgN 풀이를 하려는 이유는 배열의 길이가 꽤 길기 때문에 시간복잡도를 줄이기 위해서입니다.

그런데 저러한 Active List를 다 가지고 있게 되면, //(O(N^2)//)의 공간 복잡도를 갖게 되는데 NlgN으로 푸는 시간복잡도를 갖는 경우 대충 N이 10만 ~ 100만 정도 될 터인데, 이러한 N값의 N 제곱의 공간 복잡도는

필요 메모리 양이 꽤 많아서 보통 모두 할당할 수 없습니다.

 

그래서 저 Active list 전체를 다 저장하는 것 외의 방법을 찾아야 합니다.

 

그런데 Active list들의 데이터 특징을 좀 살펴보면, 같은 길이의 active list는 앞서 알게 된 그리디한 성질 때문에 하나만 가지고 있습니다. 그리고 모든 active list의 길이는 1,2,3,4 와 같은 식으로 같은 길이의 리스트는 하나만 나오고

점진적으로 1만큼 차이가 나는 것을 알 수 있습니다.

 

따라서 Active list의 마지막 숫자만 가지고 있어도 될 것 같은 느낌이 듭니다.

그렇게 저장할 경우 //(O(N)//)의 공간복잡도를 갖는 배열 하나만 가지고 있어도 됩니다.

따라서 Active list의 마지막 숫자의 값만 가지고 있는 배열을 따로 만들도록 하겠습니다.

 

이 배열을 list라는 벡터로 저장하고 구현을 한 소스코드 내용입니다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 1000006
int arr[MAXN];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
	}
	vector<int> list;
	for (int i = 0; i < n; i++) {
		auto& a = arr[i];

		if (list.size() == 0) list.push_back(a);
		else if (a < list[0]) list[0] = a;
		else if (a > list.back()) list.push_back(a);
		else {
			auto it = upper_bound(list.begin(), list.end(), a - 1);
			*it = a;
		}
	}

	printf("%u\n", list.size());

	return 0;
}

 

이렇게해서 백준 12015번 문제인 가장 긴 증가하는 부분 수열 2 문제를 풀 수 있습니다.

 

 

 

--------------------------------------------------------------------------

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

https://www.crocus.co.kr/681

https://www.acmicpc.net/workbook/view/801

https://jaimemin.tistory.com/1095

https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

https://jason9319.tistory.com/113