[Algorithm] LIS 요소 역추적하기(backtracing)

실제 LIS 알고리즘을 통해 생성된 백터는 실제 LIS를 나타내지 않습니다. 

그렇기 때문에 LIS를 이루는 원소들을 알아내기 위해서는 추가 과정이 필요합니다.

 

아래 문제가 LIS 요소 역추적을 연습하기에 가장 좋은 문제입니다.

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

2568번: 전깃줄 - 2

일단, 전깃줄-2번 문제의 코드 설명에 앞서

https://yhwan.tistory.com/21님의 블로그 사진을 참고하여 정확하게 이해할 수 있었습니다.

[백준] 2568번: 전깃줄2 - python3

 

백터 bactrace를 하나 만들고 원래 배열v의 값을 LIS백터에 하나씩 넣으며 원래 배열v의 값이 LIS백터에서 차지하는 idx를 하나씩 backtrace백터에 push합니다.

그렇게 해서 backtrace백터가 완성되면, backtrace배열에서 각 숫자가 처음으로 나타나는 곳의 원래배열(v)의 값을 배열 맨 뒤에서부터 map에 표시해줍니다.

표시후 그곳을 제외한 곳을 최종 ans벡터에 넣어주면 됩니다.

 

코드 첨부(c++)

//전깃줄-2
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
int n, a, b;
vector<pair<int, int>> v;
vector<int> LIS;//값, idx
vector<int> backtrace;
vector<int> ans;
map<int, int> m;
 
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a>>b;
        v.push_back(make_pair(a, b));
    }
 
    sort(v.begin(), v.end());
 
    int idx = 0;
    for(int i=0; i<v.size(); i++){
        if(LIS.empty() || LIS.back()<v[i].second){
            LIS.push_back(v[i].second);
            backtrace.push_back(LIS.size()-1);
        }else{
            int idx = lower_bound(LIS.begin(), LIS.end(), v[i].second)-LIS.begin();
            backtrace.push_back(idx);
            LIS[idx] = v[i].second;
        }
    }
 
    int temp = LIS.size()-1;
    for(int i=backtrace.size()-1; i>=0; i--){
        if(backtrace[i]==temp){
            temp--;
            m[i] = 1;
        }
    }
 
    for(int i=0; i<v.size(); i++){
        if(m.count(i)==0){
            ans.push_back(v[i].first);
        }
    }
 
    sort(ans.begin(), ans.end());
 
    cout<<n-LIS.size()<<"\n";
    for(int i=0; i<ans.size(); i++){
        cout<<ans[i]<<"\n";
    }
 
    return 0;
}

 

github 첨부(https://github.com/jungahshin/algorithm/blob/master/c:c%2B%2B/2568.cpp)

jungahshin/algorithm