[적용한 알고리즘]
세그먼트 트리, LIS
[아이디어]
[생각의 흐름 / 절차]
내용
[교훈]
오래전부터 LIS 를 쓰면 풀리겠다고 생각했는데
도저히 N^2 의 DP로는 안풀려 잠깐 포기하고 있었던 문제였는데,
최근에 세그먼트 트리를 이용해서 풀 수 있다고 하여
블로그를 보고 열심히 구현해봤다.
(http://kks227.blog.me/220791986409)
NlogN 으로 구현 가능한게 세그먼트 트리와 이분탐색이라는데,
이분탐색을 이용하는 방법도 고민해봐야겠다.
<코드>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
bool compare (pair<int, int> a, pair<int, int> b){
if (a.first == b.first){ //첫번째 비교 대상이 같다면
return a.second > b.second; //두번째 애를 비교해 큰 놈을 뒤로 보내준다.
}
else {
return a.first < b.first;
} // 오름차순으로 정렬해주세요
}
void update(vector<int> &tree, int node, int start, int end, int index, int delta){
if (index < start || index > end) return; // 범위 밖에 있는 경우
tree[node] = max(tree[node], delta);
if (start != end){ //리프 노드가 아닌 경우
int mid = (start + end) / 2;
update(tree, node * 2, start, mid, index, delta);
update(tree, node * 2 + 1, mid + 1, end, index, delta);
}
}
// 내가 구하고 싶은 값의 범위 : left ~ right, 현재 체크 하고 있는 노드의 범위 : start ~ end
int getMAX(vector<int> &tree, int node, int start, int end, int left, int right){
if (left > end || right < start) { // 만약에 포함이 안되어있는 경우
return -1;
}
if (left <= start && end <= right){
return tree[node];
}
int mid = (start + end) / 2;
return max(getMAX(tree, node * 2, start, mid, left, right), getMAX(tree, node * 2 + 1, mid + 1, end, left, right));
}
int main(){
int n;
scanf("%d", &n);
vector<pair<int, int>> a;
int tree_height = (int)ceil(log2(n));
int tree_size = (1 << (tree_height + 1));
vector<int> tree(tree_size);
for (int i = 0; i < n; i++){
int x; scanf("%d", &x);
a.push_back(make_pair(x, i));
}
sort(a.begin(), a.end(), compare);
for (int i = 0; i < n; i++){
int idx = a[i].second;
int temp_max = getMAX(tree, 1, 0, n - 1, 0, idx);
update(tree, 1, 0, n - 1, idx, temp_max + 1);
}
printf("%d\n", n - tree[1]);
return 0;
}'Algorithm > BOJ' 카테고리의 다른 글
| [백준] 1753번 최단경로 (0) | 2019.11.27 |
|---|---|
| [백준] 12738번 가장 긴 증가하는 부분 수열 3 (0) | 2019.11.23 |
| [백준] 2268번 수들의 합 (0) | 2019.11.23 |
| [백준] 11505번 구간 곱 구하기 (0) | 2019.11.23 |
| [백준] 1275번 커피숍2 (0) | 2019.11.23 |