[동적 계획법][시간 초과 해결] KLIS: K-th Longest Increasing Sequence

#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
 
std::vector<std::vector<std::pair<int, int>>> cache;
int elements[500];
int skip;
const long long MAX = INT32_MAX;
 
int  N = 0;
int cacheCount[501][500] = {0,};
 
int bsearch(int len, int x, int lo, int hi)
{
    int mid = (lo+hi)/2;
    if(lo + 1 == hi) {
       return lo;
    }
    else if (cache[len][mid].first <= x)
        return bsearch(len, x, lo, mid);
    else
        return bsearch(len, x, mid, hi);
}
//count(0, 0); => -1, -1
int count(int len, int start)
{
    if(len == cache.size() - 1) return 1;
  
      int & ret = cacheCount[len][start];
    if(ret != -1) return ret;
      ret = 0;
  
    int current = cache[len][start].first;
    int currentI = cache[len][start].second;
 
    for(int i = cache[len + 1].size() -1; i >= 0 ; i--)
    {
        if(currentI < cache[len+1][i].second && current < cache[len+1][i].first) 
            ret = (int)std::min<long long> ( MAX , (long long)ret + count(len + 1, i));
    }
    return ret;
}
//reconstruct(0,0, )
void reconstruct(int len, int start, std::vector<int>& listt)
{
    int next = -1;
    int current = cache[len][start].first;
    int currentI = cache[len][start].second;
//std::cout<<"current: "<< current << "current i : "<< currentI<<" skip: "<<skip<<"\n";
    if(len != 0) {
//std::cout<<"push==============================\n";
        listt.push_back(current);
    }
    if(len + 1 != cache.size()) 
        next = bsearch(len +1, current, 0, cache[len+1].size());
  
//std::cout<<"next: "<<next<<"\n";
    for(int i = next; i >= 0;i--)
    {
      int idx = cache[len+1][i].second;
      int cnt = count(len+1, i);
//std::cout<<" count: "<< cnt<<" idx: "<< idx<< " i :"<<i<<"\n";
      if(idx < currentI) break; 
      if(cnt <= skip)
        skip -= cnt;
      else
      {
        reconstruct(len+1, i, listt);
        break;
      }
    }
}
void push(std::pair<int, int> x, int lo, int hi)
{
    int len = cache.size() - 1;
    int top = cache[len].size() - 1;
    int mid = (lo + hi)/2;
    std::vector<std::pair<int, int>> tmp {x};
 
    if (cache[len][top].first < x.first)
    {
       cache.push_back(tmp);
    }
    else if(lo + 1 == hi){
       cache[hi].push_back(x);
    }
    else if (cache[mid].back().first >= x.first)
        return push(x, lo, mid);
    else
        return push(x, mid, hi);
}
 
int lis(int i)
{
   if(i == N) return cache.size() - 1;
   std::pair<int, int> a = std::make_pair(elements[i], i); 
   push(a, 0, cache.size());
   return lis(i+1);
}
 
int main()
{
    int testCase = 0;
    scanf("%d",&testCase);
    for(int i = 0; i < testCase; i++)
    {
        cache.clear();
        scanf("%d%d", &N, &skip);
        skip = skip-1;
        for(int j = 0; j < N; j++)
            scanf("%d", &elements[j]);
        std::vector<std::pair<int,int>> tmp = {std::make_pair(-1,-1)};
        
        cache.push_back(tmp);
        printf("%d\n", lis(0));
        memset(cacheCount, -1, sizeof cacheCount);
        count(0, 0);
 
          std::vector<int> listt;
        reconstruct(0, 0, listt);
//std::cout<<"---------list: ";
          for(int j = 0; j < listt.size(); j++)
          printf("%d ", listt[j]);
        printf("\n");
    }
}

 

1. 동적 계획법을 사용해 모든 경우의 수 를 저장한다.

 

std::vector<std::vector<std::pair<int, int>>> cache;
 
const long long MAX = INT32_MAX;
int cacheCount[501][500] = {0,};
 
 
//count(0, 0); => -1, -1
int count(int len, int start)
{
    if(len == cache.size() - 1) return 1;
  
      int & ret = cacheCount[len][start];
    if(ret != -1) return ret;
      ret = 0;
  
    int current = cache[len][start].first;
    int currentI = cache[len][start].second;
 
    for(int i = cache[len + 1].size() -1; i >= 0 ; i--)
    {
        if(currentI < cache[len+1][i].second && current < cache[len+1][i].first) 
            ret = (int)std::min<long long> ( MAX , (long long)ret + count(len + 1, i));
    }
    return ret;
}

 

count 함수는 nlgn 시간 복잡도를 가지는 lis함수를 통해

lis의 정보를 얻어낸 데이터를 통해 모든 경우의 수를 구한다.

 

이 함수는 각 원소들을 다음 번 올 수 있는 자리 원소들과 비교하므로

부분문제를 해결하는데 최대 n

생성되는 부분문제는 n 이므로

총 n^2만큼의 시간이 걸린다.

 

cache[len][start]

= 증가수열의 len번째에 올수있는 원소들 중에서 start번째 원소를 저장한다.

 

lis함수를 통해 나오는 이중 벡터 cache 는 다음과 같은 정보를 포함하고 있다.

 

1. 원소가 증가 수열에 포함될때 해당하는 위치 (len)

2. 증가수열의 최대 길이 (cache.size()-1)

3. len번째에 올 수 있는 원소들의 개수 (cache[len].size() -1)

4. 원소 (cache[len][start].first)

5. 원소들의 인덱스 (cache[len][start].second)

6. len번째 원소들의 대소 (start 가 클수록 작다)

 

6번의 정보를 통해 우리는 따로 정렬을 하지 않고 문제를 사전순서대로 

생성하여 k번째 수열을 출력할 수 있다.

 

cacheCount[len][start]

= cache[len][start]의 원소에서 생성될 수 있는 모든 lis의 경우의 수를 저장한다.

 

cacheCount 배열을 통해 count 함수를 최적화 할 수 있다.

 

 

 

2. k번째 lis 생성

 

 

std::vector<std::vector<std::pair<int, int>>> cache;
 
int bsearch(int len, int x, int lo, int hi)
{
    int mid = (lo+hi)/2;
    if(lo + 1 == hi) {
       return lo;
    }
    else if (cache[len][mid].first <= x)
        return bsearch(len, x, lo, mid);
    else
        return bsearch(len, x, mid, hi);
}
//reconstruct(0,0, )
void reconstruct(int len, int start, std::vector<int>& listt)
{
    int next = -1;
    int current = cache[len][start].first;
    int currentI = cache[len][start].second;
 
    if(len != 0) listt.push_back(current);
 
    if(len + 1 != cache.size()) next = bsearch(len +1, current, 0, cache[len+1].size());
 
    for(int i = next; i >= 0;i--)
    {
      int idx = cache[len+1][i].second;
      int cnt = count(len+1, i);
 
      if(idx < currentI) break; 
      if(cnt <= skip) skip -= cnt;
      else
      {
        reconstruct(len+1, i, listt);
        break;
      }
    }
}

 

reconstruct 함수는 O(lg n * n) 의 시간 복잡도를 가지는 함수이다.

cache는 이미 정렬되어 있으므로 이진 탐색으로 다음 len에서 원소를 찾아 낼 수 있다.

 

이 함수는

lis의 첫번째 원소부터 마지막 원소까지 차근 차근 구하며 listt에 집어넣는다.

 

skip이 더 작은 경우는

해당하는 원소로 klis가 만들어진다는 뜻이므로 포함시키고 len + 1 로 넘어가

다음 원소를 구한다.

 

skip이 더 큰 경우에는

해당하는 원소로 klis가 만들어지지 않는다는 뜻이므로 포함시키지않고

skip에서 해당하는 원소로 만들어지는 경우의 수를 빼고

해당원소보다 다음으로 큰 원소로 넘어간다.

 

 

3. 시간복잡도  

lis를 구하는데 O(nlgn)

count를 구하는데 O(n^2)

klis를 구하는데 O(nlgn)

 

count함수가 다른 함수보다 더 크므로

시간복잡도는 이 함수에 지배된다.

 

따라서 count함수를 O(nlgn)으로 줄일 수 있으면

총 시간 복잡도는 O(nlgn) 이 될 것 이다.

 

 

KLIS