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

 

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

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

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

풀이!

 이 문제에서 가장 긴 증가하는 부분 수열의 길이를 구하는 알고리즘의 동작방식은 12015: 가장 긴 증가하는 부분 수열 2와 같다. 12015 문제와 다른 점은 이 문제는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력해야한다. 그렇기 때문에 경로를 저장하고 나중에 이 경로를 다시 찾아야한다. 먼저 가장 긴 증가하는 부분 수열의 길이를 구하는 방법은 아래 포스팅을 참고하면 된다!

https://donggul-godsang.tistory.com/94

[C/C++] 백준 12015: 가장 긴 증가하는 부분 수열2 (O(logn) 알고리즘)

 

Backtrace 알고리즘!

 부분 수열의 경로를 구하는 방법은 여러가지가 있는데 이 backtrace를 구현하는데 많은 시행 착오가 있었다. 크게 3개의 방법으로 시도해보았지만 1번 방법은 메모리 초과, 2번 방법은 시간초과가 나왔고 3번 방법으로 필요한 backtrace를 구현할 수 있었다. 앞선 방법으로는 풀지 못했지만 간단하게라도 적는 이유는 이 방법 자체가 틀린 것은 아니기 때문이다. 즉, 다른 조건에서의 문제에서는 이 방법으로 구현하는 것이 더 효과적일 수 있다는 말이다.

 

1. Map을 이용하여 그 이전의 수를 저장 (메모리 초과)

 첫번째로 이용한 방법은 map을 이용한 방법이다. map의 가장 큰 장점은 하나의 값을 알고 있을 때 바로 다음의 값을 알 수 있다는 것이다. 즉 key 값을 알고있으면 value값을 알 수 있기 때문에 key 값에 새로 들어온 값, value 값에 새로 들어온 값 전의 값(j=)lower_bound(dp,dp+max_index,arr[i])-dp)을 저장하여 backtrace를 쉽게 구현할 수 있게 해준다.

 

 다만 이 방법은 메모리 초과가 발생하는데 수열 A의 크기가 10^6이고 수열을 이루고 있는 수의 범위가 10^9*2이며 map이 vector나 array보다 더 많은 메모리를 차지하고 있기 때문에 메모리 초과가 발생하다.

 

 이 방법이 사실상 backtrace의 정석적인 방법인데 linked list 방식으로 for문을 이용하지 않고 계속 연결하여 경로를 구할 수 있다. 하지만 이 문제와 같이 수열을 이루고 있는 수가 너무 클 경우에는 사용할 수 없다.

 

 map뿐만 아니라 vector나 array를 사용하려고 하더라도 512MB가 5.12*10^8이기 때문에 메모리 초과가 나온다. 즉, 완전히 동적할당으로 구현하지 않는 한 가장 정석적인 풀이로 문제를 해결할 수 없다.

 

2. vector로 저장하고 이분탐색으로 이전의 수를 찾기 (시간 초과)

열을 이루고 있는 수만큼 배열을 잡을 수 없기 때문에 이진탐색을 이용하여 bactrace를 구하려고 시도해보았다.

 

 먼저 vector<pair<int,int>> backtrace를 잡고 3번 방식과 같이 backtrace를 저장해준다. 이후 경로를 구하는 과정에서 이진탐색을 이용하기 위해 sort를 이용해backtrace를 오름차순으로 정렬시켜준다. 이미 알고 있는 가장 긴 부분 수열의 원소를 이용하여 이진탐색을 진행해 이 원소의 전 값을 backtrace에 저장되어 있는 전 값을 찾도록 구현했다.

 

이렇게 할 경우에는 시간초과가 나왔는데 수열의 크기가 10^6이고 매 경우마다 이진탐색을 진행하기 때문에 시간복잡도가 O(N*logM)? 이상이 되기 때문인 듯하다.

기존의 정석적인 backtrace 방법을 이용하기 위해 변형을 주어 문제를 푸려고 했지만 탐색하는 시간이 오래걸려 실패했다.

 

3. Pair을 이용한 vector로 저장하고 for문으로 이전의 수 찾기  (정답)

 

 마지막으로 구현한 방법은 vector<pair<int,int>> backtrace; 을 선언하여 dp 배열에 바로 전 값, 즉 증가하는 부분 수열의 새로 추가하기 전 가장 위에 있던 값과 index를 저장하여 나중에 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력하는 방법이다.

단, 이 backtrace 방법은 dp[]배열에 새로운 값이 추가되거나 기존의 값이 바뀔 때, 즉 답이 될 수 있는 경우에만 진행했다. 다만 이 구현에서 조심해야할 점은 dp배열의 값과 arr[i]의 값이 같을 때 배열이 바뀌게 되면 backtrace의 문제가 생길 수 있기 때문에 backtrace에 새로운 쓰레기 값을 넣고 다음 수를 탐색했다.

 dp[0]=arr[0];
  backtrace.push_back(make_pair(0,dp[0])); 
  int max_index=1;
  for(int i=1;i<n;i++){
    int j=lower_bound(dp,dp+max_index,arr[i])-dp;    
    if(dp[j]==arr[i]) // 같은 값일 때 문제 생김 배열이 바뀌면서 backtrace 문제 생길 수 있음{
    {
      backtrace.push_back(make_pair(-5,0)); //쓰레기값
      continue;
    }    
    dp[j]=arr[i];
    if(j==max_index)
      max_index++;
    n_index++;
    backtrace.push_back(make_pair(j,dp[j]));
  
  }

 

 이후 일차원 for문 한번만을 이용하여 index가 backtrace와 같을 때 reverse_index에 저장 값을 저장하고 index를 하나 낮춰 다음 backtrace값을 구했다. 결국 맨 마지막 값에서부터 맨 처음 값까지 탐색을 할 경우 값이 거꾸로 출력이 되기 때문에 이 순서를 바꾸는 연산을 마지막으로 해주면 문제를 해결할 수 있다.

int tindex=max_index-1;
  for(int i=n-1;i>=0;i--){
    if(tindex==-1)
      break;
    if(tindex==backtrace[i].first){
      reverse_backtrace.push_back(backtrace[i].second);
      tindex--;
    }
  }

 

 이 방법은 수열의 크기만큼만 메모리를 잡으면 되기 때문에 수열을 이루고 있는 수만큼 메모리를 잡아야하는 1번 방법에 비해 메모리를 획기적으로 줄이면서도 쉽게 답을 구할 수 있다.

 

 

깨달은 점

 문제의 난이도가 올라가면서 backtrace를 이용하여 경로를 구하는 문제가 점점 많아지는 것 같다. 따라서 이런 backtrace 방법을 여러개 공부해야할 것 같다. 특히 이번 문제 같은 경우는 가장 기본적인 방법으로 경로를 구하게 된다면 시간초과 혹은 메모리 초과가 나오고, 정석적인 풀이는 아니지만 dp배열이 일차원으로 되어있다는 점 그리고 dp배열을 뒤에서부터 탐색했을 때 index와 backtrace에 저장한 index의 값이 같을 때가 답이 되는 경우였기 때문에 이와 같은 탐색으로 해결이 가능했다.

 

 

소스코드!(정답)

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000009];
int dp[1000002];
vector<pair<int,int>> backtrace;
vector<int> reverse_backtrace;

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,n_index=1;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  
  dp[0]=arr[0];
  backtrace.push_back(make_pair(0,dp[0])); 
  int max_index=1;
  for(int i=1;i<n;i++){
    int j=lower_bound(dp,dp+max_index,arr[i])-dp;    
    if(dp[j]==arr[i]) // 같은 값일 때 문제 생김 배열이 바뀌면서 backtrace 문제 생길 수 있음{
    {
      backtrace.push_back(make_pair(-5,0)); //쓰레기값
      continue;
    }    
    dp[j]=arr[i];
    if(j==max_index)
      max_index++;
    n_index++;
    backtrace.push_back(make_pair(j,dp[j]));
  
  }  
  
  int tindex=max_index-1;
  for(int i=n-1;i>=0;i--){
    if(tindex==-1)
      break;
    if(tindex==backtrace[i].first){
      reverse_backtrace.push_back(backtrace[i].second);
      tindex--;
    }
  }
  
  cout<<max_index<<"\n";
  for(int i=max_index-1;i>=0;i--){
    cout<<reverse_backtrace[i]<<" ";
  }
}

 

1번 방법의 소스코드(메모리 초과)

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000009];
int dp[1000002];
map<int,int> backtrace;
vector<int> reverse_backtrace;

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  dp[0]=arr[0];
  backtrace[dp[0]]=1000000002;
  int max_index=1;
  for(int i=1;i<n;i++){
    int j=lower_bound(dp,dp+max_index,arr[i])-dp;    
    if(dp[j]==arr[i]) // 같은 값일 때 문제 생김 배열이 바뀌면서 backtrace 문제 생길 수 있음
      continue;
 
    dp[j]=arr[i];
    if(j==max_index)
      max_index++;
    if(j==0){
      backtrace[arr[i]]=-1; //-1이 나오면 끝내도록!     
    }      
    else
      backtrace[arr[i]]=dp[j-1];   
        
  }    
  
  int i=1;
  reverse_backtrace.push_back(dp[max_index-1]);
  int tmp=dp[max_index-1];
  while(tmp!=1000000002){    
    tmp=backtrace[tmp];
    reverse_backtrace.push_back(tmp);
  }
  cout<<max_index<<"\n";
  for(int i=max_index-1;i>=0;i--){
    cout<<reverse_backtrace[i]<<" ";
  }   
  
}

 

2번 방법의 소스코드(시간초과)

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[1000009];
int dp[1000002];
vector<pair<int,int>> backtrace;
vector<int> reverse_backtrace;

int b_search(int tmp,int n){
  int left=0,right=n-1;
  while(left<right){
    int mid=(left+right)/2;
    if(backtrace[mid].first>=tmp) right=mid;
    else left=mid+1;
  }
  return backtrace[left].second;
}

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,n_index=1;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  dp[0]=arr[0];
  backtrace.push_back(make_pair(dp[0],1000000002));
  int max_index=1;
  for(int i=1;i<n;i++){
    int j=lower_bound(dp,dp+max_index,arr[i])-dp;    
    if(dp[j]==arr[i]) // 같은 값일 때 문제 생김 배열이 바뀌면서 backtrace 문제 생길 수 있음
      continue;
 
    dp[j]=arr[i];
    if(j==max_index)
      max_index++;
    n_index++;
    
    if(j==0)
      backtrace.push_back(make_pair(arr[i],-1)); //-1이 나오면 끝내도록!            
    else
      backtrace.push_back(make_pair(arr[i],dp[j-1]));            
  }  

  sort(backtrace.begin(),backtrace.end());
  
  int i=1;
  reverse_backtrace.push_back(dp[max_index-1]);
  int tmp=dp[max_index-1];
  while(tmp!=1000000002){    
    tmp=b_search(tmp,n_index);
    reverse_backtrace.push_back(tmp);
  }
  cout<<max_index<<"\n";
  for(int i=max_index-1;i>=0;i--)
    cout<<reverse_backtrace[i]<<" "; 
  
}