LIS

가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)가장 긴 증가하는 부분 수열은 주어진 배열에서 순서를 유지한 채로 길이가 가장 긴 증가하는 부분 수열을 찾는 문제이다. 예를 들면 배열 [10, 9, 2, 5, 3, 7, 101, 18]이 주어지면 이 배열에서 길이가 가장 긴 증가하는 부분 수열은 [2, 3, 7, 101]이며 길이는 4이다. 간단해 보이는데, 접근 방법을 모르면 어려운 유형이므로 기록한다. 해결 방법해결 방법은 2가지가 있다. 동적 계획법을 이용한 방법과 이분 탐색을 활용한 방법이다. 동적 계획법, 시간복잡도 O(N^2)#include using namespace std;int n,a[1003],cnt[1003],res;int main() { ..

코드// 데이터의 크기가 100만 => O(N^2)은 시간 내에 불가// O(NlogN) 풀이법#include #include using namespace std;int n, a[1000003], num, res;int main() { cin >> n; for(int i = 0; i > num; auto k = lower_bound(a, a+ res, num); if(*k == 0) res++; *k = num; } cout 가장 긴 증가하는 부분 수열 (11053번) 문제와 유사하지만 데이터 크기가 차이난다. 데이터 크기가 100만이기 때문에 O(NlogN)으로 해결해야 한다. lower_bound를 이용해, 들어오는 값의 위치를 찾고 만약 새로 들어오는 값이면 r..

코드#include using namespace std;int n, a[1003], cnt[1003],res;int main() { cin >> n; fill(cnt, cnt + 1003, 1); for(int i = 0; i > a[i]; } for(int i = 0; i O(N^2)으로 가장 긴 증가하는 부분 수열(LIS, longest increasing subsequence)를 구하는 문제.