- Today
- Total
Byeo
boj 2357 - 최솟값과 최댓값 본문
BOJ 2357 - 최솟값과 최댓값
목차
이 문제는 segment tree를 변형하면 해결할 수 있는 문제입니다. 기존에 child의 부분 합을 저장했다면, 이 문제에서는 child의 최소값과 최대값을 저장하면 됩니다.
Segment tree에 대한 설명은 [세그먼트 트리(Segment tree)]에서 볼 수 있습니다.
설명
BOJ 2357의 예제를 그대로 그려보면 다음과 같은 segment tree를 그릴 수 있을 것입니다!
Maximum Segment Tree
Minimum Segment Tree
18 ~ 23, 25 ~ 32 node는 segment tree의 코드를 따라 구현하면 관련이 없는 leaf ndoe입니다.
Code
1. 코드의 깔끔함을 위하여 같은 class로 구현하되, function pointer를 넘겨주어 minimum segment tree인지, maximum segment tree인지 구분할 수 있도록 하였습니다.
2. 문제상에서 segment tree의 update는 요구하지 않으므로 작성할 필요가 없습니다.
※주의할 점
3. Minimum tree인지, Maximum tree인지에 따라 node의 초기값 value가 달라집니다. BOJ 2357에서는 input의 최대값이 1,000,000,000 이므로 Minimum tree의 초기 value를 해당 값 이상으로만 설정해주면 됩니다.
4. Search의 첫 줄을 보시면, search range를 벗어난 query의 경우 init_val을 return하게 두었습니다. 만약 minimum tree에서 단순히 return 0을 했다면, caller에서 어떤 임의의 양수와 0을 비교하게 되므로 항상 0을 return하게 되어 정상적인 값을 얻어올 수 없습니다. 따라서 minimum tree의 out of range query 역시 INTMAX value를 return하도록 해야합니다.
#include<stdio.h>
#define INTMAX 1000000001
int N, M;
int arr[100000];
int min(int a, int b){
return a > b? b : a;
}
int max(int a, int b){
return a > b? a : b;
}
class Tree{
int node[400000];
public:
//node의 value들을 초기화, minimum tree의 경우 MAX value로 초기화 해야함을 유의
Tree(int init_val){
for(int i=0;i<N*4;i++){
node[i] = init_val;
}
}
//입력받은 array value를 기반으로 segment tree를 구성
int Init(int cur, int *arr, int left, int right, int (*func)(int,int)){
if(left==right){
node[cur] = arr[left];
return node[cur];
}
int mid = (left+right)/2;
return node[cur] = func(Init(cur*2,arr,left,mid,func), Init(cur*2+1,arr,mid+1,right,func));
}
//구간 검색 Query
int Search(int cur, int left, int right, int start, int end, int (*func)(int,int), int init_val){
if(left > end || right < start) return init_val;
if(start>=left && end <= right){
return node[cur];
}
int mid = (start+end)/2;
return func(Search(cur*2, left, right, start, mid, func, init_val), Search(cur*2+1, left, right, mid+1, end, func, init_val));
}
};
int main(){
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++){
scanf("%d",&arr[i]);
}
Tree *t_max = new Tree(0);
Tree *t_min = new Tree(INTMAX);
t_max->Init(1,arr,0,N-1, max);
t_min->Init(1,arr,0,N-1, min);
int a,b;
for(int i=0; i<M;i++){
scanf("%d %d",&a,&b);
printf("%d %d\n",t_min->Search(1,a-1,b-1,0,N-1,min,INTMAX), t_max->Search(1,a-1,b-1,0,N-1,max,0));
}
}
'알고리즘 (Algorihtm) > 백준' 카테고리의 다른 글
boj 16975 - 수열과 쿼리 21 (0) | 2021.07.15 |
---|---|
boj 11659 - 구간 합 구하기 4 (0) | 2021.07.15 |
boj 12899 - 데이터 구조 (0) | 2021.07.14 |
boj 9345 - 디지털 비디오 디스크(DVDs) (0) | 2021.07.13 |
boj 11505 - 구간 곱 구하기 (1) | 2021.07.02 |