백준 12015. 가장 긴 증가하는 부분 수열 2 - 문제풀이 (c++) (dp)
🔎 12015. 문제 보기
https://www.acmicpc.net/problem/12015
💡 문제 풀기 전
가장 긴 증가하는 부분 수열 이 문제와 비슷해보인다.
하지만 수열의 크기가 1,000,000로 시간 복잡도가 O(n^2)인 로직을 이용하면 시간을 통과하지 못한다. 그래서 O(nlog(n))로직을 생각해야 했다.
📝 코드 보기
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1111111];
int cache[1111111];
vector<int> v;
void binary_search(int x) {
int left=0, right=v.size(), mid=0;
int index=1e9;
while(left<=right) {
mid=(left+right)/2;
int num = v[mid];
if(num >= x) {
if(index> mid) {
index=mid;
}
right=mid-1;
} else {
left=mid+1;
}
}
v[index]=x;
}
void solve() {
v.push_back(a[0]);
for(int i=1; i<n; i++) {
if(v.back() < a[i]) {
v.push_back(a[i]);
} else {
binary_search(a[i]);
}
}
}
int main() {
cin >> n;
for(int i=0; i<n; i++) {
cin >> a[i];
}
solve();
cout << v.size() << "\n";
for(int i=0; i<v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}
🎈 코드 풀이 및 관련 개념
시간 복잡도: O(nlog(n))
시간 n은 수열 A를 탐색하는 시간
시간 log(n)은 이분 탐색을 통하여 벡터의 값을 바꾸는 시간이다.
방법
예를 들어 {1, 3, 7, 5}의 수열이 있다.
여기서 lis는 {1, 3, 7} 또는 {1, 3, 5}가 있다. 하지만 {1, 3, 7}보다 {1, 3, 5}가 무조건 더 좋은 수열이다. 그다음 수열에 {6}이 추가되면 {1, 3, 7, 6}은 안되지만 {1, 3, 5, 6}은 가능하다.
그래서 벡터를 이용해 하나의 값을 넣은 후 벡터 맨 뒤의 값(처음에는 배열의 첫 번째 값)과 주어진 수열의 값을 비교해서 각각의 로직을 실행한다.
Author And Source
이 문제에 관하여(백준 12015. 가장 긴 증가하는 부분 수열 2 - 문제풀이 (c++) (dp)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minseojo/백준-12015.-가장-긴-증가하는-부분-수열-2-문제풀이-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)