백준 2357번: 최솟값과 최댓값
문제
문제 바로가기> 백준 2357번: 최솟값과 최댓값
풀이
indexed tree 또는 segment tree를 이용해서 풀 수 있는 문제이다. 지난번에 백준 2042번: 구간 합 구하기를 segment tree를 이용해서 풀어보아서 이번에는 indexed tree를 이용하여 문제를 풀어보았다. 나는 개인적으로 indexed tree가 더 직관적이라서 이해가 쉽고 구현 난이도가 더 낮은 것 같다고 생각했다! 앞으로 indexe tree를 더 애용할 것 같다. 문제는 구간 최솟값과 최대값을 구하는 문제였는데, min_tree와 max_tree를 만들어서 문제를 풀었다. 자세한 내용은 주석을 참조하면 쉽게 이해할 수 있으리라 생각한다!
( 요즘 주석을 다는 습관을 갑자기 가지려고 노력 중인데 이렇게 하면 나중에 다시 볼 때도 빠를게 볼 수 있고, 확실히 이해하고 넘어 가는데에도 도움이 되는 것 같다! )
#include<iostream>
#include<vector>
#define INF 1000000001
using namespace std;
int N, M, n, a, b, tree_size=1;
vector<int> min_tree, max_tree; // 구간 최솟값, 최대값을 저장할 vector
void init(){
for(int i=tree_size-1; i>0; i--){ // 앞서 초기화한 leaf node 값을 가지고 internal node들을 구간 최소, 최대로 채워 나감
min_tree[i] = min(min_tree[i<<1], min_tree[(i<<1)|1]); // i<<1 (=i*2) , (i<<1)|1 (=i*2+1)
max_tree[i] = max(max_tree[i<<1], max_tree[(i<<1)|1]);
}
}
int minQuery(int left, int right){
left+=(tree_size-1); right+=(tree_size-1); // tree에 알맞는 index로 변환
int min_value = INF;
while (left<=right){ // O(log N)
if((left&1)==1) min_value = min(min_value, min_tree[left]); // tree의 right일 때 값을 취함
if((right&1)==0) min_value = min(min_value, min_tree[right]); // tree의 left일 때 값을 취함
left = (left+1)>>1; // (left+1)/2 node로 이동
right = (right-1)>>1; // (right-1)/2 node로 이동
}
return min_value;
}
int maxQuery(int left, int right){ // minQuery와 유사 (min과 max의 차이)
left+=(tree_size-1); right+=(tree_size-1);
int max_value = 0;
while (left<=right){
if((left&1)==1) max_value = max(max_value, max_tree[left]);
if((right&1)==0) max_value = max(max_value, max_tree[right]);
left = (left+1)>>1;
right = (right-1)>>1;
}
return max_value;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
while (tree_size < N) tree_size<<=1; // tree size를 구하기 위해 N보다 크면서 N과 가장 가까운 2의 거듭제곱을 구함.
min_tree.resize(tree_size<<1); // tree size 설정
max_tree.resize(tree_size<<1); // tree size 설정
for(int i=1; i<min_tree.size(); i++) min_tree[i] = INF; // minQuery시 비교를 위해 초기화 (max_tree는 초기화하지 않아도 0으로 되어 있음)
for(int i=tree_size; i<tree_size+N; i++){ // tree의 leaf node들을 입력 값으로 채움
cin>>n;
min_tree[i] = n;
max_tree[i] = n;
}
init(); // min_tree, max_tree를 만듦
for(int i=0; i<M; i++){
cin>>a>>b;
cout << minQuery(a, b) << ' ' << maxQuery(a, b) << '\n'; // 구간 최소, 최대 출력
}
}
Author And Source
이 문제에 관하여(백준 2357번: 최솟값과 최댓값), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@danbibibi/백준-2357번-최솟값과-최댓값-d48d83lf저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)