-
백준 2357번 : 최솟값과 최댓값알고리즘/BOJ 2021. 6. 28. 16:37
문제 : https://www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
여러 구간이 주어지면 각 구간의 최대값과 최솟값을 빠르게 찾아야하는 문제이다. 당연한 소리지만 각 구간마다 완전탐색으로 최대값과 최솟값을 찾아주면 시간초과가 뜰 것이다. 그래서 O(logN) 복잡도로 찾을 수 있는 세그먼트트리 자료구조를 사용해야 한다.
void init(int node, int start, int end){ if(start == end){ mintree[node] = li[start]; maxtree[node] = li[start]; return; } int mid = (start+end)/2; init(node*2, start, mid); init(node*2+1, mid+1, end); mintree[node] = min(mintree[node*2], mintree[node*2+1]); maxtree[node] = max(maxtree[node*2], maxtree[node*2+1]); } pair<int, int> find(int node, int a, int b, int left, int right){ if(left > b || right < a) return make_pair(INT32_MAX, 0); if(a <= left && right <= b){ return make_pair(mintree[node], maxtree[node]); } pair<int, int> l, r; l = find(node * 2, a, b, left, (left + right) / 2); r = find(node * 2 + 1, a, b, (left + right) / 2 + 1, right); return make_pair(min(l.first, r.first), max(l.second, r.second)); }세그먼트 트리는 각 구간의 sum, 최대값 등등 여러 정보를 담을 수 있고 항상 longN 복잡도 내에서 찾을 수 있는 장점이 있다. 위는 세그먼트 트리의 코드로 init과 find 함수이다. 자세한 구현내용은 아래 백준 사이트 설명을 참조하자
https://www.acmicpc.net/blog/view/9
#include <iostream> #include <vector> #include <algorithm> #include<cstring> #include <cmath> #include <set> #include <map> #include <queue> #include <unordered_map> #include <deque> #include <string> typedef long long ll; using namespace std; int n, m; vector<int> li; vector<int> mintree, maxtree; void init(int node, int start, int end){ if(start == end){ mintree[node] = li[start]; maxtree[node] = li[start]; return; } int mid = (start+end)/2; init(node*2, start, mid); init(node*2+1, mid+1, end); mintree[node] = min(mintree[node*2], mintree[node*2+1]); maxtree[node] = max(maxtree[node*2], maxtree[node*2+1]); } pair<int, int> find(int node, int a, int b, int left, int right){ if(left > b || right < a) return make_pair(INT32_MAX, 0); if(a <= left && right <= b){ return make_pair(mintree[node], maxtree[node]); } pair<int, int> l, r; l = find(node * 2, a, b, left, (left + right) / 2); r = find(node * 2 + 1, a, b, (left + right) / 2 + 1, right); return make_pair(min(l.first, r.first), max(l.second, r.second)); } int main(int argc, char** argv) { cin.tie(NULL); ios_base::sync_with_stdio(false); cin >> n >> m; int h = (int)ceil(log2(n)); li.resize(n+1); mintree.resize((1<<(h+1)) + 10 ); maxtree.resize((1<<(h+1)) + 10 ); for(int i=1; i<=n; i++) cin >> li[i]; init(1,1,n); for(int iii=0; iii<m; iii++){ int a, b; cin >> a >> b; pair<int, int> ans = find(1, a, b, 1, n); cout << ans.first << " " << ans.second << "\n"; } return 0; }'알고리즘 > BOJ' 카테고리의 다른 글
백준 11505번 : 구간 곱 구하기 (C++) (0) 2021.07.01 백준 1062번 : 가르침 (C++) (0) 2021.07.01 백준 16562번: 친구비 (0) 2021.06.27 백준 11003번 : 최솟값 찾기 (0) 2021.06.26 백준 5430번: AC (C++) (0) 2021.06.26