DP LIS(최장증가수열) + lower_bound 사용
사용언어
Visual studio 2019 C++
유형
다이나믹 프로그래밍 - LIS(최장증가수열)
https://leleluv1122.github.io/algorithm/LIS/ 의 2탄으로…
저번에 설명했던 LIS는 10만 이하의 수에서 시간초과가 나지않은 풀이였다.
이번에는 10만이 넘어갈때에 풀이를 설명하고자 한다.
먼저, lower_bound를 알아야 한다.
lower_bound
- lower_bound는
#include <algorithm>에 포함되어있는 함수이다. - 이진탐색(Binary Search)기반의 탐색 방법이다.
- 찾으려는 key값이 없으면 key값보다 큰 가장 작은 정수의 값을 찾음.
LIS의 크기만을 구할때에는 밑의 풀이를 사용한다.
배열 LIS 풀이
int dp[10];
int arr[9] = { 0, 1, 6, 2, 5, 7, 3, 5, 6 }; // 0은 포함하지 않음
int len = 1;
dp[1] = arr[1];
for (int i = 1; i < 9; i++) {
if (dp[len] < arr[i]) {
dp[++len] = arr[i];
continue;
}
int idx = lower_bound(dp + 1, dp + len + 1, arr[i]) - dp;
dp[idx] = arr[i];
}
cout << len << endl;
vector LIS 풀이
vector<int> dp;
vector<int> v;
int arr[8] = {1, 6, 2, 5, 7, 3, 5, 6 };
for (int i = 0; i < 8; i++)
v.push_back(arr[i]);
dp.push_back(v[0]);
for (int i = 1; i < 8; i++) {
if (dp.back() < v[i]) {
dp.push_back(v[i]);
continue;
}
auto it = lower_bound(dp.begin(), dp.end(), v[i]);
*it = v[i];
}
cout << dp.size() << endl;
이렇게 하면 N의 개수가 10만이 넘어가도 시간초과가 나지않게 풀이를 작성할 수 있다.
백준 LIS + lower_bound 문제 (LIS의 size를 구하는문제)
사이즈를 구할때에는 위와같은 방식으로 풀면되지만, 배열까지 구할 경우 추가해야 되는 부분이 있다.
vector<int> dp;
vector<int> v;
stack<int> ans;
int p[MAX]; // MAX는 각 문제의 max값을 define이나 const를 사용하여 정의하면 된다.
int arr[8] = {1, 6, 2, 5, 7, 3, 5, 6 }; // 임의의 수
for (int i = 0; i < 8; i++)
v.push_back(arr[i]);
dp.push_back(v[0]);
p[0] = dp.size() - 1;
for (int i = 1; i < 8; i++) {
if (dp.back() < v[i]) {
dp.push_back(v[i]);
p[i] = dp.size() - 1; // p[i]에 lis의 크기를 넣어놓음
continue;
}
auto it = lower_bound(dp.begin(), dp.end(), v[i]);
*it = v[i];
p[i] = it - dp.begin(); // it의 자리의 값이 변경될 경우 p[i]의 값을 it자리값으로 바꿔줌
}
int cnt = dp.size() - 1;
for(int i = 7; i >= 0; i--) {
if(cnt == p[i]) { // cnt가 lis크기 넣어놓은 값과 같게되면 그 값이 LIS값이므로 push
ans.push(v[i]);
cnt--;
// 위에서부터 내려오기때문에 stack을 사용해서
// 값을 출력할때에는 정방향으로 출력할 수 있게한다.
}
}
cout << ans.size() << endl;
while(!ans.empty()) {
cout << ans.top() << " ";
ans.pop();
}
cout << endl;
백준 LIS + lower_bound 문제 (LIS의 사이즈와 배열을 둘다 구하는문제)
- 2568 전깃줄 - 2
2568 풀이 - 14002 가장 긴 증가하는 부분 수열 4
14002 풀이 - 14003 가장 긴 증가하는 부분 수열 5
14003 풀이
14002번 문제와 14003문제는 배열의 크기의 차이가 존재하지만 lower_bound로 풀 경우 풀이가 같게된다.
Comments