12015번_가장 긴 증가하는 부분 수열2 / 가장 긴 증가하는 부분 수열3_BOJ

문제 링크

12015번 가장 긴 증가하는 부분 수열2 : https://www.acmicpc.net/problem/12015

12738번 가장 긴 증가하는 부분 수열3 : https://www.acmicpc.net/problem/12738

문제 설명 및 해결 아이디어

최장 증가 수열(LIS_Longest Increasing Subsequence)에 관한 설명은 아래 블로그에 자세히 나와있다.

http://jason9319.tistory.com/113?category=670441

다음 내용은 허락맡고 가져온 내용임을 밝힌다. 

이 블로그에는 잘 정리된 내용들이 많기때문에 많이 들어가보면 좋다.

이번 포스팅에서만 유일하게 내용을 가져왔고, 다음부턴 링크만 제공하겠다.

http://jason9319.tistory.com/113?category=670441

이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다.

LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다.

쉬운 이해를 위해서 예를 들어보겠습니다.

다음과 같은 수열이 존재한다고 해봅시다.

여기서 LIS를 찾는다면 

다음과 같이 빨간 부분으로 색칠된 부분이 LIS가 됩니다.

눈치 빠르신 분들은 벌써 알아채셨을겁니다. 

LIS는 앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대 길이가 되도록 숫자를 선택하는 경우입니다.

보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이됩니다.

즉, 그 수열에서 존재하는 모든 부분 증가 수열 중 길이가 최대인 수열의 길이가 답이 되는거죠.

이것을 구현하기 위해서 가장 쉽게 생각 할 수 있는건 O(N^2)의 시간복잡도를 가지는 DP로 구현하는 것입니다.

DP 테이블 dp[x]의 정의를 하자면 

dp[x] : x번째 수를 마지막 원소로 가지는 lis의 길이 

가 됩니다.

이런 방식으로 구현할 경우 

dp[x]가 이미 채워져 있다면 x보다 큰수의 y의 수열값 arr[y]도 arr[x]보다 크다면 dp[y]는 dp[x]+1이 될 수 있음을 고려해 볼 수 있습니다.

이러한 아이디어를 기반으로 2중 포문을 채워나가면서 O(N^2)의 시간 복잡도에 LIS를 해결 할 수 있습니다.

2중 포문 부분의 소스를 공개하자면 다음과 같이 되겠군요.

for (int i = 0; i < n; i++) {
    if (dp[i] == 0)dp[i] = 1;
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j]) {
            if (dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }
}

하지만 N이 10만이 넘는다면 ..?

우리는 O(N^2)의 방법으로 LIS 문제를 해결할 수 없게 됩니다.

그렇기 때문에 우리는 O(NlogN)의 방법으로 LIS를 해결하는 방법을 배워야 합니다.

O(NlogN)으로 LIS를 구현하는 방법은 대표적으로 두가지가 있는데

하나는 세그먼트 트리를 이용하여 arr[x]의 위치에 x번째 수를 마지막 원소로 가지는 lis의 길이를 업데이트하여 

매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값+1을 업데이트하는 방식으로 처리를 한다면

N번을 확인하면서 최댓값을 찾는데 O(logN)시간이 걸리니 총 O(NlogN)의 시간이 걸릴 것입니다.

하지만 이 방법을 소개하려던건 아니고 좀 더 간단한 방법을 소개해 드리려고 합니다.

바로 이분 탐색을 이용하는 방법입니다.

이번에도 O(N)의 방법으로 수열을 처음부터 확인할건데 이번에는 이분탐색을 이용하여 LIS를 유지하기 위한 최적의 위치에다가 수를 삽입하는 방식입니다.

자리를 찾는데 lower_bound를 이용하기 때문에 O(logN)의 시간복잡도를 가지게 되어 총 O(NlogN)의 시간복잡도를 가지게 됩니다.

최적의 위치를 찾는방법은 생각보다 간단한데요.

벡터를 하나 생성 한 뒤 -INF(나올 수 없는 가장 작은 값)를 삽입해 줍니다.

이후 매번 수열을 볼때마다 벡터의 맨 뒤 원소와 현재 보고있는 수열의 원소를 비교하여 수열의 원소가 더 클 시 벡터에 push_back해준 뒤 LIS의 크기(답)을 1증가 시켜줍니다.

만약 수열의 원소가 벡터의 맨 뒤 원소보다 작을 경우 lower_bound를 이용하여 최적의 자리를 찾은 뒤 그 자리의 값을 해당 수열의 원소로 교체해 버립니다.

정당성에 대한 이해를 돕기 위하여 한가지 예를 들어보겠습니다.

만약 벡터에 현재 10 40 70 이라는 값이 들어있다고 할 때 50이 들어갈 위치를 찾기 위하여 lower_bound로 50을 찾는다면 이터레이터는 70의 위치를 가리키게 되어 70을 50으로 갱신할 것 입니다.

그러면 벡터에는 10 40 50 이라는 값이 들어가게 될 것입니다.

자, 이 다음 55라는 값이 들어온다면 우리는 70이라는 값이 50으로 갱신되지 않았다면 55라는 값을 벡터에 추가하지 못하여 손해를 봤을 것입니다.

우리가 lower_bound를 이용하여 x라는 값을 찾으면 x보다 크거나 작은값중 최솟값의 위치를 return하기 때문에

현재 구성된 lis구조를 유지하면서 앞으로 보게 될 수열들을 최대한 벡터가 많이 수용할 수 있도록 적절한 위치에 값이 갱신이 됩니다.

자, 이제 그림과 함께 보겠습니다.

빨간부분은 지금 보는 위치이고 파란칸을 벡터라고 하겠습니다. 10의 경우 첫번째 수이기 때문에 우선 벡터에 넣어줍니다.

3번째 인덱스까지는 벡터의 끝값이 항상 수열의 값보다 작기 때문에 전부 삽입해 줍니다. 

이후 4번째 인덱스의 값이 벡터의 끝값보다 작기 때문에 lower_bound로 탐색한 뒤 40을 25로 갱신해줍니다.

5번째 인덱스의 값또한 벡터의 끝값보다 작기 때문에 lower_bound로 탐색한 뒤 20을 20으로 갱신해줍니다.

6번째 인덱스의 값은 벡터의 끝값보다 크기 때문에 50을 추가해 줍니다.

7번째 인덱스의 값은 벡터의 끝값보다 작기 때문에 lower_bound로 탐색 한 뒤 50을 30으로 갱신해줍니다.

자 이때 만약에 뒤에 40이라는 값이 온다면 벡터의 끝값을 30으로 갱신하지 않았다면 40을 추가하지 못할것입니다.

하지만 매 순간 증가수열을 유지할 수 있는 최적의 장소를 찾아서 갱신하기 때문에 다음에 40이 올 경우 추가할 수 있게됩니다.

자 다시 돌아와서 70과 85를 벡터에 추가해준다면 우리는 이 수열에서의 LIS의 길이는 6이라는 사실을 알 수 있게됩니다.

쉬운 이해를 이해 소스코드를 첨부하겠습니다.

vt.push_back(-INF);
for (int i = 0; i < n; i++) {
    scanf("%d", &x);
    if (vt.back() < x) {
        vt.push_back(x);
           ans++;
    }
    else {
        auto it = lower_bound(vt.begin(), vt.end(), x);
        *it = x;
    }
}

한가지 주의 할 점은 벡터에 들어있는 값이 LIS를 이루는 요소와 무관하다는 것입니다.

수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색 된 최적의 위치가 앞에 있을 수도 있기 때문입니다. 

자 이제 O(NlogN)의 시간복잡도로 LIS 문제를 해결하실 수 있겠나요?

이제 LIS를 이용하는 여러가지 문제들을 풀어봅시다.

출처: http://jason9319.tistory.com/113?category=670441 [ACM-ICPC 상 탈 사람]

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 987654321
 
int n, num;
vector<int> vt;
//vector<int>::iterator it;
 
int main() {
    scanf("%d", &n);
    vt.push_back(-INF);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        if (vt.back() < num) {
            vt.push_back(num);
            cnt++;
        }
        else {
            auto it = lower_bound(vt.begin(), vt.end(), num);
            *it = num;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

ㄴㄴ

ㄴㄴㄴ