가장 긴 증가하는 부분 수열 문제 모음

 

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

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

 

수열의 길이 제한이 10^6이기 때문에 O(nlogn)으로 해결해야 한다.

이분탐색으로 길이'만' 구하기

 

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

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

 

제한이 작기에 dp로 역추적

 

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

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

 

이분탐색으로 길이와 원래 배열에서의 i 번째 값이 LIS에서는 몇번째 원소인지 기억하는 idx 배열로

LIS 역추적.

 

원리를 이해해보자. 이분탐색으로 LIS의 길이를 구하는 알고리즘은 원본 배열을 차례대로 순회하며 LIS 배열 끝에 추가할 수 있으면 push_back 하고, 끝값보다 작은 경우에는 가능한 자리에 밀어넣는 것이다.

때문에, 길이는 구할 수 있지만 구한 LIS 배열의 원소 정보는 보장이 안된다.

 

10, 50, 20, 50, 15, 80, 70, 75 이라는 수열이 있다고 해보자. 이때의 LIS는 

{10, 20, 50, 70, 75} 이고, 길이는 5이다.

원래의 방법으로 길이를 구해보자.

 

***기억해야 할 점***

현재 사용하는 인덱스 지정 방식은 lower bound 로, 찾으려 한 값이 처음 나타난 인덱스를 반환한다.

만약 값이 존재하지 않는다면 그 값 보다 큰 값이 처음으로 등장한 인덱스를 반환한다.

 

while(s < e) {

mid = (s + e) / 2;

if(k <= ans[mid]) {

    e = mid;

} else {    // ans[mid] < k 인 경우

    s = mid +1;

}

return s;

}

 

ex)  ans = {10, 50}, 타겟 = 20, s = 0, e = 1

 

-> mid = (0+1) / 2 = 0

 

-> ans[0] < 20

 

-> s = mid + 1    // s = 1

 

s == e 이므로 break

 

return s;

 

결국 lowerbound 가 반환하는 인덱스는 50의 인덱스. 구하려는 값이 처음 등장한 위치, 또는 그 값보다 큰 값이 처음으로 등장한 인덱스를 반환하는 것이다.

 

하는김에 upperbound에 대해서도 알아보자.

 

upperbound는 특정 k 값을 초과하는 값이 처음으로 등장한 인덱스를 반환한다.

 

while(s < e) {

mid = (s + e) / 2;

if(k < ans[mid]) {

    e = mid;

} else {    // ans[mid] <= k 인 경우

    s = mid +1;

}

return s;

 

 

ans[mid] 가 k 보다 작거나 같다면 upper_bound 가 아니므로 오른쪽으로 이동

ans[mid]가 k보다 크다면 upper_bound 만족, 더 작은 upper_bound 인덱스가 있는지 확인하기 위해 왼쪽으로 이동

탐색이 종료된 경우에는 마찬가지로 시작점 s를 반환해준다.

탐색은 s == e 일때 멈춘다는 점을 기억하자.

그리고 탐색범위는 웬만하면 [s, e)로 주도록 하자.

 

 

다시 본론으로 돌아와서 LIS 길이를 구하는 알고리즘에 의해 ans 배열이 어떻게 업데이트 되는지 알아보자.

 

10 -> {10}

50 -> {10, 50}

20 -> {10, 20}

50 -> {10, 20, 50}

15 -> {10, 15, 50}

80 -> {10, 15, 50, 80}

70 -> {10, 15, 50, 70}

75 -> {10, 15, 50, 70, 75}

 

최종 ans 배열은 {10, 15, 50, 70, 75} 라는 값을 가리킨다.

하지만 원래는 {10 20, 50, 70, 75} 여야 한다. 어째서 길이는 올바르지만 배열의 원소는 다를까?

 

{10, 50} 에서 20이 교체될 때, 20은 50의 값을 대체한다. 

50이 들어가야 했던 자리에 20이 들어가는 것이다.

또 다시 {10, 20, 50} 에서 15는 20의 자리를 대체한다. 두 경우 모두 길이에는 영향을 미치지 않는다.

만약 새로운 값으로 추가했다면 문제가 되었겠지만, '가능한' 자리를 대체하는 것이기 때문에 올바른 길이를 구할 수 있는 것이다.

 

역으로 생각해보면 길이가 올바른 이유는 올바른 배열의 원소들이 있어야 했던 자리를 다른 원소들이 대체 했기 때문이라면, 이를 복구할 방법 또한 존재한다는 것이다.

우선 길이를 구하는 해법의 배열이 틀린 이유는 원래 배열에서의 순서를 무시했기 때문이다. 그렇다면 우리가 찾아야 할 것은 원래 배열의 순서를 만족하면서 LIS 인 것을 찾으면 될 것이다.

 

LIS의 첫번째 값 부터 찾아나가는 것은 부적합하다. 경우의 수가 여러가지 존재하기 때문이다.

하지만 LIS의 가장 끝값 부터 찾는 경우의 수는 단 1가지이다. 

가장 마지막 원소는 가장 마지막으로 수정된 것이 정답이라고 생각하면 되기 때문이다.

 

위의 논리대로 예시의 LIS를 역추적해보자. 순서는 원본 배열을 따른다.

 

 

75 -> {10, 15, 50, 70, 75} --> 가장 마지막 값 75--- > {75}

70 -> {10, 15, 50, 70} --->  ok --> {75, 70}

80 -> {10, 15, 50, 80} ---> 무시해준다.

15 -> {10, 15, 50}  -----> 2번째 원소이므로 순서상 부적합.

50 -> {10, 20, 50} -----> {75, 70, 50}

20 -> {10, 20} -----> {75, 70, 50, 20}

50 -> {10, 50} ----> 무시해준다.

10 -> {10} ----> {75, 70, 50, 20, 10}

 

 

해당 배열을 역순으로 뒤집으면 LIS이다.

원리를 다시 알아보자.

 

 

원본 배열	10	50	20	50	15	80	70	75
LIS배열 인덱스	1	2	2	3	2	4	4	5

 

 

LIS 의 길이인 5를 값으로 갖는 배열의 원소를 추가해주는 것 부터 시작하여

가장 처음 만나는 이전 인덱스 값의 벨류를 LIS 배열에 추가해주는 것이다.

'가장 처음 만나는 인덱스'라는 순서를 무시하고 값이 수정된 경우나, 대소 관계가 맞지 않는 것을 방지하기 위함이다.

 

ex)  75, 70 -> ok(수정된 값이 아니기에 대소 관계, 원본 배열에서의 순서 모두 만족)

하지만 75, 80 --> LIS배열에서의 순서, 원본 배열에서의 순서 모두 만족하지만 이후 값이 수정되었으므로 대소관계가 어긋남

 

즉, 가장 왼쪽에서 부터 시작하여 LIS 배열을 역추적하는 방식은 중간중간 순서에 맞지 않게 배열을 수정한 것을 무시하고 올바른 배열을 구하는 방법으로 적절하다는 것을 알 수 있다.

 

'가장 마지막 값까지 도달하기 위해서 수정된 값들은 무시해주고, 현재와 연속한 상태의 이전 값들만을 참조하는 방식'

이라고 생각해도 되겠다.

 

원본 배열	10	50	20	50	15	80	70	75
LIS배열 인덱스	1 선택	2 무시 (연속성X)	2 선택	3 선택	2 무시 (순서 위반)	4 무시 (연속성X)	4 선택	5

 

모든 경우에서 가장 처음 등장한 값(연속성이 보장되는 값) 이 적용되는 이유는 간단하다.

원본 배열의 LIS 배열 인덱스를 생각해보면

5 (==LIS에서 5번째 인덱스) 가 나오기 위해서는 4가 반드시 선행되어야 한다.

4번째까지 채운 상태에서 5번째를 push_back 해야 되기 때문이다. 그중에서 첫번째 5와 가장 가까운 4가 올바른 LIS 배열의 원소인 것이다.

LIS배열 인덱스

1 선택

2 선택

3 무시

4 무시

5 무시

3 선택

4 선택

5

 

 

즉, n+1번째 인덱스가 등장하기 위해서는 반드시 n번째 인덱스가 1번은 선행되어야 하는데, 그 중에서 연속성이 보장되는 값  (가장 가까운 값)  만을 찾으면 되므로 역추적 방식의 해는 반드시 존재하게 되는 것이다.

 

 

 

역추적의 기본 원리와 길이가 업데이트 되는 방식을 같이 공부했던 흥미로운 문제였다.

 

전체 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> arr;
vector<int> ans;
vector<int> idx;
vector<int> LIS;

int lbs(int k) {
    int s = 0, e = ans.size() - 1, mid;

    while(s < e) {
        mid = (s + e) / 2;

        if(k <= ans[mid])
            e = mid;
        else
            s = mid + 1;
    }
    return s;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    arr.resize(N+1);
    idx.resize(N+1);
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    ans.push_back(arr[0]);
    idx[0] = 0;
    for(int i = 1; i < N; i++) {
        if(ans.back() < arr[i]) {
            ans.push_back(arr[i]);
            idx[i] = ans.size()-1;
        }
        else {
            int loc = lbs(arr[i]);
            ans[loc] = arr[i];
            idx[i] = loc;
        }
    }
    int lis = ans.size();
    cout << lis << "\n";
    for(int i = N-1; i >= 0; i--) {
        if(idx[i] == lis-1){
            lis--;
            LIS.push_back(arr[i]);
            if(lis == 0)
                break;
        }
    }
    reverse(LIS.begin(), LIS.end());

    for(int i = 0; i < LIS.size(); i++)
        cout << LIS[i] << " ";
}