일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 2023
- 너비 우선 탐색
- 우선 순위 큐
- dfs
- 다익스트라
- pytorch
- 문자열
- tensorflow
- lazy propagation
- dropout
- Overfitting
- back propagation
- BFS
- 미래는_현재와_과거로
- 조합론
- 크루스칼
- c++
- 이분 탐색
- 회고록
- 가끔은 말로
- 세그먼트 트리
- 자바스크립트
- 가끔은_말로
- NEXT
- DP
- 알고리즘
- 백트래킹
- 분할 정복
- object detection
- 플로이드 와샬
Archives
- Today
- Total
Doby's Lab
[알고리즘] 백준 13544번: 수열과 쿼리 3 (C++) 본문
https://www.acmicpc.net/problem/13544
쿼리마다 부분 배열을 정렬하여 값을 구하면
정렬 O(nlogn), 탐색 O(n), 쿼리의 수 O(m)으로
>> 시간 복잡도가 O(n^2 * logn * m)으로 시간 초과가 나게 된다.
그렇다고 해서 탐색을 이분 탐색으로 하기에도 이미 O(n * m)에 의해 시간 초과가 난다.
이럴 때 필요한 자료구조가 머지 소트 트리이다.
코드를 보면 아마 [머지 소트 트리 = 세그먼트 트리 + 머지 소트]라고 느낄 수 있다.
머지 소트 트리란 머지 소트 하는 과정을 각 구간 별로 노드에 담아 구간 별로 세그먼트 트리화 시킨 트리형 자료 구조다.
만들어지는 과정은 Merge Sort와 똑같이 O(NlogN)이다.
다만, 쿼리를 구하는 과정을 생각해보면 트리의 높이로 인한 시간 복잡도 O(logN),
탐색을 하되 이분 탐색으로 더 빠르게 하면 O(logN),
쿼리의 수 O(M)
>> O(M * (logN)^2)으로 구할 수 있다.
각 노드에 배열이 담기므로 트리를 2차원 배열로 선언해주어야 한다.
- 머지 소트 트리를 구성한 함수는 다음과 같다.
void init(int node, int start, int end){
if(start == end) msTree[node].push_back(arr[start]);
else{
msTree[node].resize(end - start + 1);
int mid = (start + end) >> 1;
init(2 * node, start, mid);
init(2 * node + 1, mid + 1, end);
merge(msTree[2 * node].begin(), msTree[2 * node].end()
,msTree[2 * node + 1].begin(), msTree[2 * node + 1]. end()
,msTree[node].begin());
}
}
분할 정복처럼 함수를 구현한다. merge() 함수를 통해 더 간편하게 구현할 수 있었다.
>> O(NlogN)
- 쿼리 함수
int query(int node, int start, int end, int left, int right, int val){
if(left > end || start > right) return 0;
if(left <= start && end <= right){
return msTree[node].end() - upper_bound(msTree[node].begin()
, msTree[node].end(), val);
}
int mid = (start + end) >> 1;
return query(2 * node, start, mid, left, right, val)
+ query(2 * node + 1, mid + 1, end, left, right, val);
}
[AC 코드]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// n의 범위가 1~100000 >> 트리의 범위는 1~400000
// 한 노드에 배열이 들어가야 하므로 2차원 벡터로 선언
vector<int> msTree[400000 + 1];
vector<int> arr;
int n;
void init(int node, int start, int end){
if(start == end) msTree[node].push_back(arr[start]);
else{
// merge 시킨 배열을 넣기위해 resize로 size 다시 할당
msTree[node].resize(end - start + 1);
int mid = (start + end) >> 1;
init(2 * node, start, mid);
init(2 * node + 1, mid + 1, end);
// 분할 정복으로 받아낸 자식 노드(left, right) 배열을 merge
merge(msTree[2 * node].begin(), msTree[2 * node].end()
,msTree[2 * node + 1].begin(), msTree[2 * node + 1]. end()
,msTree[node].begin());
}
}
int query(int node, int start, int end, int left, int right, int val){
if(left > end || start > right) return 0;
if(left <= start && end <= right){
// 더 빠르게 이분 탐색을 이용하여 탐색
return msTree[node].end() - upper_bound(msTree[node].begin()
, msTree[node].end(), val);
}
int mid = (start + end) >> 1;
return query(2 * node, start, mid, left, right, val)
+ query(2 * node + 1, mid + 1, end, left, right, val);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++){
int a;
cin >> a;
arr.push_back(a);
}
init(1, 0, n - 1);
int last_ans = 0;
int m;
cin >> m;
for(int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
// 쿼리에 XOR 연산
a ^= last_ans;
b ^= last_ans;
c ^= last_ans;
last_ans = query(1, 0, n - 1, a - 1, b - 1, c);
cout << last_ans << '\n';
}
return 0;
}
728x90
'PS > BOJ' 카테고리의 다른 글
[자료구조] 백준 13537번: 수열과 쿼리 1 (C++) (0) | 2022.03.03 |
---|---|
[알고리즘] 백준 7469번: K번째 수 (C++) (0) | 2022.03.02 |
[알고리즘] 백준 2485번: 가로수 (C++) (0) | 2022.02.26 |
[알고리즘] 백준 2224번: 명제 증명 (C++) (0) | 2022.02.26 |
[알고리즘] 백준 17829번: 222-풀링 (C++) (0) | 2022.02.26 |