[백준/C++/Platinum(5)] 14003 - 가장 긴 증가하는 부분 수열 5

14003번: 가장 긴 증가하는 부분 수열 5

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

“가장 긴 증가하는 XX수열”이라는 문제는 꽤 종류가 많다. 시간 간격을 두고 한두 문제씩 복습하면서 배우기 좋다.

 

 

앞으로 가장 긴 증가하는 부분 수열을 줄여거 LIS(Longest Increasing Subsequence)로 줄여서 부르겠다.

이런 수열들의 길이를 구하는 문제를 먼저 설명하고, 이 문제를 설명하려고 했는데, 이미 다른 사람들이 설명을 잘 해놓아서 따로 적고 싶지는 않았다. 심지어는 나무위키에도 해당 개념에 대한 문서가 있었는데, 그걸 참고해서 우선 “LIS의 길이 구하는 알고리즘”을 이해했으면 이 블로그 글도 무리 없이 이해할 수 있을 것이라고 생각한다.

출처 : 아래 링크

최장 증가 부분 수열 - 나무위키

 

문제 :

LIS 문제들은 많지만, 그 문제들 중 가장 강한 문제 축에 속하는게 이 녀석이다. 길이만 구하는게 아니라, 실제로 그 수열까지 출력시켜야 하기 때문이다. 그냥 코드 복붙을 할 수는 없다는 말씀! 나무위키에서 보면, 두번째 방법 맨 마지막에 A[i]라는 배열이 이미 만들어져 있음을 알 수 있다.

 

-> 이 녀석을 풀어보면서 먼저 이해해보자.

12015번: 가장 긴 증가하는 부분 수열 2

 

A[i]를 출력하면 되는 거 아닌가? 싶을 수도 있지만 그렇지는 않다. 이미 원래 수열이 대충 오름차순으로 되어 있지 않는 이상, 중간의 값이 변동되면서 이전에는 없던 수가 A[i]에 끼어 들어 갈 수도 있기 때문이다.

 

이러한 반례로

8
10 20 30 1 40 2 50 3

정도가 있겠다.

 

당연히 LIS는 10, 20, 30, 40, 50으로, 5개의 숫자를 가진다. 하지만 알고리즘이 끝까지 돌아가면 A[i]는 1 2 3 40 50이 되고, 이는 실제로는 존재할 수 없는 수열이다.

 

여기서 우리가 주목 해야하는 것은 “믿을 수 있는 정보”이다. A[i]의 마지막 인덱스는 여태껏 계산한 모든 부분 수열 중에 제일 긴 증가 수열의 끝 부분을 무조건 가지고 있을 수 밖에 없다.

 

마지막 인덱스는

1. 여태껏 나온 수 중에 가장 큰 수가 나온 경우

2. 제일 긴 수열 보다 한 숫자 짧은 수열이지만 기존의 LIS의 끝보다 작은 끝을 가지고 있기에 업데이트 되는 경우

밖에는 업데이트 되지를 않는다.

 

위의 예시에는 A[i]를 보았을때 LIS가 통으로 뭔지는 몰라도 일단 “50으로 끝난다”는 것 정도는 알 수 있다는 소리이다.

여기서부터 역추적을 시작할 수 있는데, 50이라는 마지막 숫자가 막 A[i]에 추가되는 때를 생각해보자.

 

50은 제일 큰 숫자이고, 그래서 원래는 4개의 숫자를 가지고 있던 배열의 마지막에 추가가 될 것이다.

/*A[i] 배열
0  1  2  3 +  4(번째 인덱스)*/
1 20 30 40 + 50

이 되는데, 이때의 A[i]의 기존에 가지고 있던 마지막 인덱스를 생각해보자. 애초에 우리가 50이라는 숫자를 붙여도 된다고 생각한건 어째서일까? “여태까지 계산한 LIS가 통으로 뭔지는 몰라도 40으로 끝난다”는 정보가 있기 때문이다. LIS가 40으로 끝난다면 50을 뒤에다 붙여도 되지 않겠는가? 그래서, 마지막 인덱스가 업데이트 될때의 이전 마지막 인덱스 또한 믿을 수가 있다.

 

굳이 설명하지는 않겠지만, 이는 굳이 마지막 인덱스 뿐만 아니라 어떤 숫자를 이분 탐색을 통해서 업데이트하던, A[i]를 업데이트 한다면 A[i - 1]는 언제나 믿을 수 있는 정보를 가지고 있다. i - 1의 길이를 가지는 증가 수열 중에 제일 A[i - 1] 값이 작은 수열의 정보를 가지고 있기 때문이다.

 

나는 이를 일종의 체인으로 보았고, 업데이트 당시의 A[i], A[i - 1] 값을 키, 값 페어로 기록해주는 해쉬테이블이 있다면 n번의 역추적을 하는 것으로 LIS를 구할 수 있을 것이라고 생각했다.

 

코드 : 

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    vector<int> lis, a, pr;
    vector<unordered_map<int, int>> hash(1000005);
    
    //일단 수열 a를 input 받음
    cin >> n;
    for(int i = 0; i < n; i++){
        int input;
        cin >> input;
        a.push_back(input);
    }
    
    int j = 0;
    lis.push_back(a[0]);
    for(int i = 1; i < n; i++){
        int node = a[i];
        if(node > lis[j]) {
            lis.push_back(node);
						//이전의 A[i - 1]를 해쉬테이블에 기록.
            hash[j + 1][node] = lis[j];
            j++;
        } else {
            auto it = lower_bound(lis.begin(), lis.end(), node);
            //이전에도 같은 숫자가 있었다면 굳이 뒤의 
            //내용을 계산해 인덱스 번호를 올릴 이유가 없다.
						if(*it == node)
                continue;
            *it = node;
            
            int idx = (it - lis.begin());
            if(idx){ // A[0]을 갱신하는게 아니라면
								//이전의 A[i - 1]를 해쉬테이블에 기록.
                hash[idx][node] = *(it - 1);
            }
        }
    }
    
    cout << (j + 1) << '\n';
    int prev = lis[j];
    pr.push_back(lis[j]);
    for(int i = j; i > 0; i--){
        prev = hash[i][prev];
        pr.push_back(prev);
    }
    
    reverse(pr.begin(), pr.end());
    for(int n : pr){
        cout << n << ' ';
    }
    
    return 0;
}

그리고 이걸 정답으로 제출해서 맞을 수 있었다. 기존의 알고리즘에서 C++의 lower_bound 를 이용해서 코드를 줄이고 unordered_map을 해쉬테이블로 이용하는 전략이 굉장히 잘 먹혀들어가서 성취감도 있었다.

여담이지만, segtree 문제를 조금씩 풀어보고 있어서 드디어 세그먼트 트리에 관한 내용들을 조만간 포트팅 할 수 있을 것으로 보인다.