[동적 계획법][시간 초과] KLIS: K-th Longest Increasing Sequence
2021. 1. 14. 18:27ㆍ알고리즘/알고리즘 문제 [medium]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
std::vector<std::vector<std::pair<int, int>>> cache;
int elements[500];
double skip;
int N = 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);
}
//num(0, 0);
void num(int len, int start, std::string str)
{
if(len == cache.size() - 1)
{
skip -= 1;
if(skip < 0)
std::cout<<str<<"\n";
return;
}
int current = cache[len][start].first;
int currentI = cache[len][start].second;
int next = bsearch(len +1, current, 0, cache[len+1].size());
for(int i = next; i >= 0;i--)
{
if(currentI > cache[len+1][i].second) break;
num(len + 1, i, str + std::to_string(cache[len+1][i].first) + " ");
if(skip < 0)
return;
}
}
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()
{
std::ios_base :: sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int testCase = 0;
std::cin>>testCase;
for(int i = 0; i < testCase; i++)
{
cache.clear();
std::cin>>N>>skip;
skip = skip-1;
for(int j = 0; j < N; j++)
std::cin>>elements[j];
std::vector<std::pair<int,int>> tmp = {std::make_pair(-1,-1)};
cache.push_back(tmp);
std::cout<<lis(0)<<"\n";
num(0, 0, "");
}
|
cs |
1. LIS
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
std::vector<std::vector<std::pair<int, int>>> cache;
int elements[500];
int N = 0;
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);
}
|
cs |
이 함수는 이진 탐색을 이용하여 O(n lg n) 으로 최대 lis를 반환하는 함수이다.
이 함수를 통해 이차원 벡터로
lis의 끝부분들을 알 수 있으며
index 를 pair 을 사용하여 기록하면
쉽게
정렬된 lis들의 정보를 얻어 낼 수 있다.
2. KLIS
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
std::vector<std::vector<std::pair<int, int>>> cache;
double skip;
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);
}
//num(0, 0);
void num(int len, int start, std::string str)
{
if(len == cache.size() - 1)
{
skip -= 1;
if(skip < 0)
std::cout<<str<<"\n";
return;
}
int current = cache[len][start].first;
int currentI = cache[len][start].second;
int next = bsearch(len +1, current, 0, cache[len+1].size());
for(int i = next; i >= 0;i--)
{
if(currentI > cache[len+1][i].second) break;
num(len + 1, i, str + std::to_string(cache[len+1][i].first) + " ");
if(skip < 0)
return;
}
}
|
cs |
이 함수는 1.lis에서 만든 cache배열의 정보를 근거로
사전 순서대로 lis를 생성하면서
문제에서 주어진 k에 도달하면 그 lis를 출력하고 종료하는 함수이다.
이 함수의 복잡도는
skip * n * lgn 이고 skip >> n 이므로
n^2 lgn 보다 훨씬 크기 때문에
시간 초과가된다.
'알고리즘 > 알고리즘 문제 [medium]' 카테고리의 다른 글
| [동적 계획법][미니맥스]NUMBERGAME 숫자 게임 (0) | 2021.01.16 |
|---|---|
| [동적 계획법][시간 초과 해결] KLIS: K-th Longest Increasing Sequence (0) | 2021.01.15 |
| [동적 계획법] OCR 광학 문자 인식 (0) | 2021.01.13 |
| [동적 계획법] POLY 폴리오미노 (0) | 2021.01.11 |
| [동적 계획법] ASYMTILING 비대칭 타일링 (0) | 2021.01.10 |