이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 32 번째 글 입니다.
목차
골드2 : 이분 탐색 문제이다.
생각
기존에 dp로 풀었던 문제가 데이터의 개수만 달라져 새로운 문제가 되었다. 이번 문제는 풀이를 좀 참고하였으며 새로운 공부를 할 수 있었다.
이 문제는 먼저, 일반적인 dp문제로 풀수가 없다. dp로 풀기 위해서는, $O(n^2)$알고리즘인데, 그렇게 될 경우 n=1000000이라, 터진다. 따라서 시간 복잡도를 줄여야 한다. 그래서 방법을 달리한다.
현재 index까지 왔을 때, 가장 긴 증가하는 수열의 길이는 얼마인가?
이것이 기존 dp로 풀었을 때 정의였다. 그런데 조금 색다르게, 배열을 하나 두고 이걸 만들어보자.
a[] : 1 2 4 3
#1 1
#2 1 2
#3 1 2 4
$4 1 2 ?
이 다음에 우리는 4번째 index에 있는 3을 추가해야 한다. 3까지 포함해 보았을 때, 가장 증가하는 수열의 길이는 1 2 4 혹은 1 2 3 으로 3이다. 여전히 값은 3이지만 지금 하는 과정은 증가하는 수열을 나타내는 배열을 만들어보는 중이다. 어떤 것을 선택하는 것이 바람직 할까?
조금 생각해보면 1 2 3을 가지고 있는 것이 보다 현명하다. 결국 3을 1 2 4에서 추가하지 못하는 이유는 3이 4보다 작기 때문이다. 그리고 이 마지막 값은, 다음 요소에 대한 LIS를 구하는 데 있어 가장 핵심적인 숫자이다. 이 숫자가 가장 작은 숫자를 유지하면서 같은 LIS값을 갖는 것이 이후에 배열을 업데이트하는데 있어서 LIS를 구하는 것에 핵심적이다. 그래서 기본적으로는 내 요소를 포함하는 LIS를 만드는 것이 좋다. 따라서 이 상황에서 우리는 3보다 큰 요소 중 가장 첫번째에 나오는 요소와 3을 바꿔야 한다.
그렇다면 여기서 만약 이렇게 주어졌다고 생각해보자.
a[] : 1 2 3 2
#1 1
#2 1 2
#3 1 2 3
$4 1 2 ?
여전히 같은 상황이다. 4번째 index인 2는 3보다 작기 때문에 추가할 수 없다. 그렇다면, 위의 논리대로라면 2는 3과 바꿔야 한다. 하지만 그럴 경우 1 2 2로 LIS에 합당하는 배열을 만들지 못한다. 실질적으로 4번째 index에서 LIS는 1 2 3 이다. 즉, 유지되어야 한다. 따라서, 우리는 2를 LIS에서 찾아 자기 자신과 바꾸는 작업을 해야 한다.(위의 작업과의 일관성을 위해 이렇게 설명. 사실은 바꾸지 않는다라는 표현이 맞을지 모름)
lowerBound
위의 두 문제를 다 만족하는 것이 있다. 바로 lowerBound이다. lowerBound는, 내가 원하는 값의 가장 하한선의 위치를 찾아주고(같은 것을 고를 수 있음), 내가 원하는 값이 없을 경우, 내 값보다 큰 원소 중 가장 첫번째로 나오는 요소의 위치를 반환한다. 이 두 기능은, 위에서 설명한 문제의 해결책과 동일하다. 따라서 우리는 이 함수를 사용할 수 있다.
Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
const int MAX = 1000000;
int N, ans = 0;
int a[MAX+1];
vector<int> v;
void push(int num){
if (v.back() < num) v.push_back(num);
else {
auto p = lower_bound(v.begin(), v.end(), num);
*p = num;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
v.push_back(MAX);
for (int i = 0; i < N; i++) push(a[i]);
cout << v.size() << '\n';
return 0;
}