예전에 LIS알고리즘을 DP로 O(n^2)만에 구현하는 포스팅을 올린 적이 있다. 하지만 이 알고리즘을 쓰기엔 시간복잡도가 크다보니 시간초과가 나는 문제가 많다.
LIS O(n^2) : https://code-feather.tistory.com/19
이번 포스팅에서는 이분탐색을 활용한 O(nlogn) LIS 알고리즘을 올려보려고 한다. 이분탐색을 써서 푸는 백준 문제는 아래 세 개가 있다.
가장 긴 증가하는 부분 수열 2
가장 긴 증가하는 부분 수열 3
가장 긴 증가하는 부분 수열 5
LIS 길이 구현 방법
외부 배열이나 벡터에서 각각의 숫자들의 lower bound를 구해 그 인덱스로 넣어주는 방식이다. 아래 그림은 LIS 이분탐색 과정이다.
이렇게 이분탐색으로 배열을 만들고 나면 크기 순서대로 숫자들이 정렬이 되어있다. 여기서 이 배열의 길이는 LIS의 길이와 같다. 여기서 주의해야할 점은 배열의 숫자들이 실제 부분 수열은 아니라는 것이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int A[1000000],N,LIS=1,r;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>N;
for(int i=0;i<N;i++)
{
cin>>A[i];
}
v.push_back(A[0]);
for(int i=1;i<N;i++)
{
if(v[v.size()-1]<A[i])
{
LIS++;
v.push_back(A[i]);
continue;
}
r = lower_bound(v.begin(),v.end(),A[i]) - v.begin();
v[r] = A[i];
}
cout<<LIS;
}
LIS 수열 구현 방법
LIS 길이 구현 방법과 거의 비슷한 방식으로 구현한다. 다만 추가적으로 각 숫자마다의 lower_bound를 저장하는 새로운 d배열이 필요하다.
arr | 3 | 5 | 7 | 9 | 2 | 1 |
lower_bound | 0 | 1 | 2 | 3 | 0 | 0 |
각각의 숫자마다 lower_bound값이 이렇게 나타났었는데 이를 어떤 배열에 저장해두자. 이 배열에서 맨 마지막부터 이터레이션을 할 것이다. 이터레이션 중 최초로 LIS - 1값 (여기서는 3)이 나오면 이 수(여기서는 9)를 저장한다. 이후에는 LIS-2가 나오면 저장하고, 다음에는 LIS-3 ..... 0까지 뒤에서부터 최초로 나오는 수들에 해당하는 수들을 stack이나 배열에 저장한다. 이제 이 수들을 출력해주면 해당하는 부분수열이 잘 나온다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int A[1000000], N, LIS = 1, r, check[1000001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> A[i];
}
v.push_back(A[0]);
check[0] = 0;
for (int i = 1; i < N; i++)
{
if (v.back() < A[i])
{
LIS++;
v.push_back(A[i]);
check[i] = LIS - 1;
}
else
{
r = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
v[r] = A[i];
check[i] = r;
}
}
cout << LIS << "\n";
vector<int> ans(LIS);
int index = LIS - 1;
for (int i = N - 1; i >= 0; i--)
{
if (check[i] == index)
{
ans[index] = A[i];
index--;
}
}
for (int i = 0; i < LIS; i++)
{
cout << ans[i] << " ";
}
}
'정보 > 알고리즘&자료구조' 카테고리의 다른 글
최장 증가 부분 수열 DP O(N^2) (1) | 2024.02.07 |
---|---|
Knapsack Problem Dynamic Programming C++ (1) | 2024.02.01 |
C++ <algorithm> sort()로 배열 정렬하기 (0) | 2024.01.14 |