LIS(Longest Increasing Subsequence) 시리즈
02 Oct 2021
가장 긴 증가하는 부분 수열 문제는 수열의 부분 수열중 가장 긴 길이의 증가 수열을 찾는 문제입니다.
A. 가장 긴 증가하는 부분 수열
N (1 ≤ N ≤ 1000) 이고, 각 $A_i$의 범위는 (1 ≤ Ai ≤ 1000)입니다. A번의 경우 N의 범위가 1000이하 이기 때문에 dp를 이용한 이중 포문으로 구현하여 풀 수 있습니다.
dp[i]= i번째 인덱스가 LIS의 마지막 원소일때, LIS의 길이 입니다. d[i]=1로 모두 초기화 해주면, 아래 코드도 돌아갑니다. arr[i]<arr[j]인 경우 d[j]==d[i] 라는 것은 d[j]가 i번째 원소를 고려하지 않은 값이라는 뜻입니다.
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(arr[i]<arr[j]&&d[j]==d[i]){
d[j]=d[i]+1;
}
}
}
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#include <map>
#include <set>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
//using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
//vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
int dp[1000];
int arr[1000];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
if(dp[i]==0) dp[i]=1;
for (int j=i+1;j<n;j++){
if(arr[j]>arr[i]){
if(dp[j]<dp[i]+1)
dp[j]=dp[i]+1;
}
}
}
int ans = 0;
for(int i=0;i<n;i++){
ans = max(dp[i],ans);
}
cout<<ans;
return 0;
}
B. 가장 긴 증가하는 부분 수열 2
N (1 ≤ N ≤ 1,000,000) 이고, 각 $A_i$의 범위는 (1 ≤ Ai ≤ 1,000,000) 입니다. O(N^2)의 dp로 수행하면 시간 초과가 나기 때문에, 이분 탐색을 통해 O(nlogn)으로 구현을 해야합니다.
lower_bound() 을 이용해 크거나 같은 원소의 위치에 새로운 원소로 삽입하는 하여 풀 것입니다. 더 자세한 설명을 하자면, 벡터에 현재 10 40 70 이라는 값이 들어있다고 할 때 50이 들어갈 위치를 찾기 위해 lower_bound로 50을 찾는다면, iterator는 70의 위치를 가리키게 되어 70을 50으로 갱신할 것 입니다.
그러면 벡터에는 10 40 50 이라는 값이 들어가게 될 것입니다. 이 다음 55라는 값이 들어온다면 70이라는 값이 50으로 갱신되지 않았다면 55라는 값을 벡터에 추가하지 못하여 손해를 봤을 것입니다.
이를 고려하여 lowerbound를 이용하여 더 작은 값으로 벡터를 갱신하는 방법입니다. 이때 실제 벡터가 이루는 원소를 LIS와 관련이 없습니다. 단순히 LIS의 길이를 알아 내기 위한 벡터입니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#include <map>
#include <set>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
//using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
//vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
vector<int>v;
v.resize(n+1);
int ans = 0;
for(int i=0,p1;i<n;i++){
cin>>p1;
if(i==0)
{
v.push_back(p1);
ans+=1;
continue;
}
if(v.back()<p1)
{
v.push_back(p1);
ans+=1;
}
else
{
auto it = lower_bound(v.begin(),v.end(),p1);
*it = p1;
}
}
cout<<ans;
return 0;
}
C. 가장 긴 증가하는 부분 수열 3
N (1 ≤ N ≤ 1,000,000) 이고, 각 $A_i$의 범위는 (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) 입니다. B와 같은 방식으로 풀되, lower_bound()는 양수에 대해서만 동작하기 때문에 입력값에 10^9+1을 더하여 vector에 삽입할 것입니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#include <map>
#include <set>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
//using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
//vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
vector<ll>v;
v.resize(n+1);
int ans = 0;
for(int i=0;i<n;i++){
ll p1;
cin>>p1;
p1+=1e9+1;
if(i==0)
{
v.push_back(p1);
ans+=1;
continue;
}
if(v.back()<p1)
{
v.push_back(p1);
ans+=1;
}
else
{
auto it = lower_bound(v.begin(),v.end(),p1);
*it = p1;
}
}
cout<<ans;
return 0;
}
D. 가장 긴 증가하는 부분 수열 4
A번과 같은 범위인 N (1 ≤ N ≤ 1000) 이고, 각 $A_i$의 범위는 (1 ≤ Ai ≤ 1000)입니다. dp를 이용해 O(n^2)으로 구현해줍니다. 그리고 나서 역추적 하는 것을 통해 LIS를 출력하였습니다. dp값이 증가했을때, 비교한 인덱스 값을 대입해 주었습니다.
예를 들어 10,20,10,30,20,50 이 있을때, 역추적을 위한 인덱스 값은 -1, 0, -1, 1, 0, 3, 입니다. 그래서 v[5]=3부터 역추적을 시작해서 5→3→1→0 순으로 출력했습니다.
code
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#include <map>
#include <set>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
//using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> pii;
typedef pair<ll,ll> pl;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
//vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int arr[1001];
int v[1001];
void go(int p)
{
if(p==-1)
return ;
go(v[p]);
cout<<arr[p]<<" ";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
int dp[1001];
memset(v,-1,sizeof(v));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
cin>>arr[i];
}
for(int i=0;i<n;i++){
if(dp[i]==0) dp[i]=1;
for (int j=i+1;j<n;j++){
if(arr[j]>arr[i]){
if(dp[j]<dp[i]+1){
dp[j]=dp[i]+1;
v[j]=i;
}
}
}
}
int MAX = 0;
int index=0;
for(int i=0;i<n;i++){
MAX = max(MAX,dp[i]);
if(MAX==dp[i])
index=i;
}
cout<<MAX<<endl;
go(index);
return 0;
}
E. 가장 긴 증가하는 부분 수열 5
아직 못풀었습니다.