최장 증가 수열
- Algorithm
- 2021년 6월 3일
주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열이다.
예를 들어, 341256784134라는 수열에서 LIS는 345678 or 125678 이 된다.
1. 찾는 방법
LIS의 크기 구하는 방법은 dp와 이분탐색에 따라 방법이 나뉘며 경로 추적(trace) 방법은 두 방법 모두 인덱스를 가리키는 배열을 하나 추가하여, 탐색하면서 해당 값의 앞의 수열 인덱스를 저장하는 방법으로 구현한다.
이 배열을 가지고 가장 큰 부분순열을 갖는 값부터 역 추적하며 순열을 구한다.
2. O(n^2)
dp를 이용해 찾는 방법이다.
현재 위치의 수를 끝으로 하는 최장 증가 수열의 값을 dp에 저장하는 방법으로 수열의 첫번째부터 끝까지 반복하며, 현재 위치보다 앞의 수들을 모두 비교하기 때문에 O(n^2) 만큼 걸린다.
1) lis 크기 구하기
void lis_dp(string str) {
vector<int> dp(str.length(), 0); //해당 index의 값을 끝으로 하는 가장 긴 수열의 값 저장
for (int i = 0; i <= str.length(); i++) {
dp[i] = 1; //처음값은 1로 시작
for (int j = 0; j < i; j++) {
if (str[i] > str[j] && dp[j] + 1 > dp[i]) { //현재 위치의 앞의값중 가장 긴 수열의 길이 find
dp[i] = dp[j] + 1;
}
}
}
cout << "\nmax length : " << max << endl << "Subsequence : ";
}
2) lis 원소 구하기 (trace)
void lis_dp(string str) {
vector<int> dp(str.length(), 0); //해당 index의 값을 끝으로 하는 가장 긴 수열의 값 저장
vector<int> backtrace_idx(str.length(), -1); //수열의 이전 값의 index값, -1이 처음 값
vector<char> lis; //최장 증가 수열 값 trace
int max = 0, idx;
for (int i = 0; i <= str.length(); i++) {
dp[i] = 1; //처음값은 1로 시작
for (int j = 0; j < i; j++) {
if (str[i] > str[j] && dp[j] + 1 > dp[i]) { //현재 위치의 앞의값중 가장 긴 수열의 길이 find
dp[i] = dp[j] + 1;
backtrace_idx[i] = j; // trace 추적 위해
}
}
// trace 추적위해
if (dp[i] > max) {
max = dp[i];
idx = i;
}
}
cout << "\nmax length : " << max << endl << "Subsequence : ";
/*최장 증가 수열 처음 부분까지 역 추적하며 vector에 추가*/
for (int i = idx; i >= 0; i = backtrace_idx[i]) {
lis.push_back(str[i]);
}
reverse(lis.begin(), lis.end()); //큰 값부터 추가했으므로 reverse
for_each(lis.begin(), lis.end(), [](char c) { cout << c << " "; }); // print
}
3. O(nlgn)
이분탐색을 이용하는 방법으로 추가배열에 최장 증가 수열의 값을 저장하는 방법이다.
배열의 인덱스가 수열의 길이를 나타내고, 인덱스의 값은 인덱스만큼의 길이의 수열을 갖는 값을 나타낸다.
추가배열에 마지막값보다 탐색한 현재 값이 더 크다면 배열 마지막에 값을 추가해준다.
(부분수열의 크기를 1증가 시켜주는 것)
탐색한 현재 값이 마지막 값보다 작다면, 추가배열에서 현재값보다 작은값들 중 가장 큰 값을 현재값으로 갱신해준다.
(이때 나오는 현재값보다 작은값들 중 가장 큰 값을 lower bound라고 한다)
추가 배열은 항상 오름차순으로 정렬되어있으므로, 이분 탐색으로 탐색이 가능하기 때문에 O(nlgn)이 된다.
1) lis 크기 구하기
void lis_bs(string str) {
/*부분 수열 자리수에 해당하는 value값 담기 위한 배열*/
vector<pair<char, int>> arr; // first = value,
for (int i = 0; i < str.length(); i++) {
//첫번째 값이거나 현재 값이 arr의 마지막 값보다 크다면 새로 추가 ==> 최장 증가 수열의 크기 1증가
if (arr.empty() || arr.back().first < str[i]) arr.push_back({str[i], i});
//현재 값이 arr 마지막 값보다 작다면, lis의 크기 증가는 안된다. lower bound의 값 갱신
else {
auto it = lower_bound(arr.begin(), arr.end(), make_pair(str[i], i), cmp);
*it = {str[i], i};
}
}
cout << "\nmax length : " << arr.size() << endl << "Subsequence : ";
}
2) lis 원소 구하기 (trace)
void lis_bs(string str) {
/*부분 수열 자리수에 해당하는 value값 담기 위한 배열*/
vector<pair<char, int>> arr; // first = value, second = idx ==> 배열의 길이가 lis 크기다.
vector<int> backtrace_idx(str.length(), -1); //수열의 이전 값의 index값, -1이 처음 값
vector<char> lis; //최장 증가 수열 값 trace
for (int i = 0; i < str.length(); i++) {
//첫번째 값이거나 현재 값이 arr의 마지막 값보다 크다면 새로 추가 ==> 최장 증가 수열의 크기 1증가
if (arr.empty() || arr.back().first < str[i]) {
if (!arr.empty()) backtrace_idx[i] = arr.back().second; //최장 증가 수열값 trace
arr.push_back({str[i], i});
}
//현재 값이 arr 마지막 값보다 작다면, lis의 크기 증가는 안된다. lower bound의 값 갱신
else {
auto it = lower_bound(arr.begin(), arr.end(), make_pair(str[i], i), cmp);
if (it != arr.begin()) backtrace_idx[i] = (it - 1)->second; // lis 값 trace ==> lower bound 위치가 맨 앞이라면 수행 x
*it = {str[i], i};
}
}
cout << "\nmax length : " << arr.size() << endl << "Subsequence : ";
//*최장 증가 수열 처음 부분까지 역 추적하며 vector에 추가*/
for (int i = arr.back().second; i >= 0; i = backtrace_idx[i]) {
lis.push_back(str[i]);
}
reverse(lis.begin(), lis.end()); //큰 값부터 추가했으므로 reverse
for_each(lis.begin(), lis.end(), [](char c) { cout << c << " "; }); // print
}
