인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요~ 동적계획법 4번 LIS 문제 질문 있습니다.
작성
·
231
0
안녕하세요. 정말 감사하게 강의 잘 듣고 있습니다. 어려운 알고리즘도 너무 쉽게 설명을 잘 해주셔서 감사합니다.
추가로 계획된 알고리즘 강의도 기대됩니다. 개설하시면 바로 신청할 예정입니다.
저지사이트에 LIS 문제를 선생님이 알려주신 코드를 적용하여 잘 해결했는데요..
n<=100,000 인경우에는 O(n^2)알고리즘으로는 해결할 수 없다고 문제에 나와 있어서...시간초과가 납니다.
어떤 알고리즘을 적용하면 좋을지 조언을 구합니다. 감사합니다.~
답변 2
1
김태원
지식공유자
안녕하세요^^
LIS 문제를 O(NlogN) 복잡도로 짜는 방법이 있습니다. 이분검색을 이용하는 방법인데 다음 코드가 바로 그 방법입니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
freopen("input.txt", "rt", stdin);
int n, a;
cin>>n;
vector<int> arr;
arr.push_back(-2147000000);
for(int i=0; i<n; i++) {
cin>>a;
if(a>arr.back()) arr.push_back(a);
else{
auto it=lower_bound(arr.begin(), arr.end(), a);
*it=a;
}
//for(auto x : arr) cout<<x<<" ";
//cout<<endl;
}
cout<<arr.size()-1;
return 0;
}위에 코드에서 lower_bound 함수가 이분검색으로 a이상의 값 중 가장 작은 수의 위치를 찾아 줍니다. lower_bound에 대해서구글링해보세요.
0
