[boj] 백준 2357 최솟값과 최댓값 (c++) - 세그먼트 트리

[문제]

https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

[풀이]

세그먼트 트리(segment tree)를 사용해서 푸는 standard 문제이다. 세그먼트 트리는 특정 구간에 대한 연산을 효율적으로 하기 위해 사용되는데, 보통은 배열의 부분합(구간합)을 저장해놓고 쓴다. 이 문제에서는 최솟값과 최댓값을 구하기 위해 구간의 최솟값과 최댓값을 저장하도록 하였다. (세그먼트 트리도 차후에 알고리즘에 정리해야겠다)

 

    h = (int)ceil(log2(n)); //세그먼트 트리의 높이 log(n)

    min_tree = vector<int>(1<<(h+1)); //세그먼트 트리의 크기 2^(h+1)
    max_tree = vector<int>(1<<(h+1));

 

세그먼트 트리의 리프 노드 개수가 n개일 때, 높이는 log2(n)이다. ceil 연산은 올림을 해준다. 이 때 트리의 크기는 2^(h+1)이므로 각 트리를 1<<(h+1) 만큼 할당해준다. 

 

void init(int index, int start, int end){
    if(start==end){ //리프 노드
        min_tree[index] = max_tree[index] = arr[start];
        return;
    }
    else{
        int mid = (start+end)/2;
        init(2*index, start, mid);
        init(2*index+1, mid+1, end);
        min_tree[index] = min(min_tree[2*index], min_tree[2*index+1]); //구간의 최솟값 저장
        max_tree[index] = max(max_tree[2*index], max_tree[2*index+1]); //구간의 최댓값 저장
        return;
    }
}

 

세그먼트 트리 초기화 코드. index는 현재 노드 위치, start와 end는 구간을 나타낸다. start==end는 리프 노드를 나타내므로 min_tree와 max_tree에 해당 값을 저장한다. index 1부터 시작하여 왼쪽 자식 노드의 index는 2*index, 오른쪽 자식 노드의 index는 2*index+1이 된다. 보통의 세그먼트 트리는 각 자식 노드의 합을 부모 노드에 저장하지만 여기서는 최솟값과 최댓값을 저장하도록 하였다. 재귀를 이용해서 초기화된다.

 

pair<int, int> findMaxAndMin(int index, int start, int end, int left, int right){
    if(left > end || right < start){ //범위 밖
        return {INT32_MAX, 0};
    }
    else if(left <= start && end <= right){
        return {min_tree[index], max_tree[index]};
    }
    else {
        pair<int, int> l, r;
        int m = (start+end)/2;
        l = findMaxAndMin(2*index, start, m, left, right);
        r = findMaxAndMin(2*index+1, m+1, end, left, right);
        return {min(l.first, r.first), max(l.second, r.second)};
    }
}

 

이런 경우가 입력으로 주어질 진 모르겠지만 left > end 이거나 right < start 인 경우는 구간 밖이므로 min에 INT32_MAX, max에 0을 반환하여 선택되지 않도록 한다.

left와 right가 start, end를 포함하고 있는 경우 start, end의 최소, 최댓값을 반환하면 된다.

start, end가 left, right를 포함하고 있는 경우 해당 범위에 맞게 조정해줘야 한다. 따라서 l, r로 나누어 재귀호출을 해준후 그 중에서도 최솟값과 최댓값을 찾아 반환해준다.  

 

[코드]

 

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>

using namespace::std;

int n, m;
int arr[100001];
vector<int> min_tree, max_tree;

void init(int index, int start, int end){
    if(start==end){ //리프 노드
        min_tree[index] = max_tree[index] = arr[start];
        return;
    }
    else{
        int mid = (start+end)/2;
        init(2*index, start, mid);
        init(2*index+1, mid+1, end);
        min_tree[index] = min(min_tree[2*index], min_tree[2*index+1]); //구간의 최솟값 저장
        max_tree[index] = max(max_tree[2*index], max_tree[2*index+1]); //구간의 최댓값 저장
        return;
    }
}

pair<int, int> findMaxAndMin(int index, int start, int end, int left, int right){
    if(left > end || right < start){ //범위 밖
        return {INT32_MAX, 0};
    }
    else if(left <= start && end <= right){
        return {min_tree[index], max_tree[index]};
    }
    else {
        pair<int, int> l, r;
        int m = (start+end)/2;
        l = findMaxAndMin(2*index, start, m, left, right);
        r = findMaxAndMin(2*index+1, m+1, end, left, right);
        return {min(l.first, r.first), max(l.second, r.second)};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    int h;
    h = (int)ceil(log2(n)); //세그먼트 트리의 높이 log(n)

    min_tree = vector<int>(1<<(h+1)); //세그먼트 트리의 크기 2^(h+1)
    max_tree = vector<int>(1<<(h+1));

    for(int i=1; i<=n; i++){
        cin >> arr[i]; //리프 노드
    }

    init(1, 1, n); //자식 노드를 2*index, 2*index + 1로 표현하기 위해 1부터 시작

    int left,right;
    pair<int, int> answer;

    for(int i=1; i<=m; i++){
        cin >> left >> right;
        answer = findMaxAndMin(1, 1, n, left, right);
        cout << answer.first << " " << answer.second << "\n";
    }
}