[백준/C++] 2357번: 최솟값과 최댓값

문제

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

---

문제 요약

n개의 정수들이 주어질 때, m개의 쿼리에 대해서 답을 출력한다.

 

각 쿼리마다 a와 b가 주어지고, a번째 정수부터 b번째 정수까지 가장 작은 정수와 가장 큰 정수를 출력한다.

 

n과 m은 0 이상 100,000이하이다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

# define ll long long

using namespace std;

int n, m;

int arr[100010];

vector<ll> min_tree;
vector<ll> max_tree;

// node번 노드를 [start, end] 범위에서 최대값을 갖는 노드로 초기화 하는 함수
ll max_init(ll node, ll start, ll end) {
    // 리프 노드일 경우, 자기 자신이 최대
    if (start == end) {
        return max_tree[node] = arr[start];
    }

    // 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여 초기화
    ll mid = (start + end) / 2;
    return max_tree[node] = max(max_init(node * 2, start, mid), max_init(node * 2 + 1, mid + 1, end));
}

// node번 노드를 [start, end] 범위에서 최소값을 갖는 노드로 초기화 하는 함수
ll min_init(ll node, ll start, ll end) {
    // 리프 노드일 경우, 자기 자신이 최소
    if (start == end) {
        return min_tree[node] = arr[start];
    }

    // 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여 초기화
    ll mid = (start + end) / 2;
    return min_tree[node] = min(min_init(node * 2, start, mid), min_init(node * 2 + 1, mid + 1, end));
}

// [start:end]에서 최댓값을 갖는 node번 노드에서 [left:right]에서 최댓값 구하기
ll max_value(ll node, ll start, ll end, ll left, ll right) {
    // 범위가 겹치지 않는 경우
    if (left > end || right < start) {
        return -1e9;
    }

    // [start, end]가 [left, right]에 포함된 경우
    if (left <= start && end <= right) {
        return max_tree[node];
    }

    ll mid = (start + end) / 2;

    return max(max_value(node * 2, start, mid, left, right), max_value(node * 2 + 1, mid + 1, end, left, right));
}

// [start:end]에서 최솟값을 갖는 node번 노드에서 [left:right]에서 최솟값 구하기
ll min_value(ll node, ll start, ll end, ll left, ll right) {
    // 범위가 겹치지 않는 경우
    if (left > end || right < start) {
        return 1e9;
    }

    // [start, end]가 [left, right]에 포함된 경우
    if (left <= start && end <= right) {
        return min_tree[node];
    }

    ll mid = (start + end) / 2;

    return min(min_value(node * 2, start, mid, left, right), min_value(node * 2 + 1, mid + 1, end, left, right));
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    // 세그먼트 트리의 노드 수 초기화 (최악의 경우, 리프노드가 2 * n개이므로)
    min_tree.resize(n * 4 + 1);
    max_tree.resize(n * 4 + 1);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    max_init(1, 1, n);
    min_init(1, 1, n);

    for (int i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;

        cout << min_value(1, 1, n, a, b) << " " << max_value(1, 1, n, a, b) << "\n";

    }

    return 0;
}

---

코드 설명

세그먼트 트리를 이용하여 문제를 해결한다.

 

각 세그먼트 트리의 루트 노드는 1번 원소부터 n번 원소까지 범위에서 최댓값과 최솟값을 갖는다.

 

a번 원소부터 b번 원소까지 범위에서 최대값과 최솟값을 갖는 각 노드는 2개의 자식노드를 갖는다.

+ 왼쪽 자식 노드는 a번 원소부터 (a + b) / 2번 원소까지 범위에서 최대값과 최소값을 갖는다.

+ 오른쪽 자식 노드는 (a + b) / 2 + 1번 원소부터 b번 원소까지 범위에서 최대값과 최소값을 갖는다.

 

1. 각 세그먼트 트리를 vector로 선언하고, n × 4 + 1 크기로 초기화한다.

+ 세그먼트 트리는 완전 이진트리이어야 하므로, 리프 노드 개수가 2 × n개이기 때문이다.

 

2. 각 세그먼트 트리의 루트 노드를 [1:n] 범위에서 최댓값을 갖는 노드로 초기화한다.

+ 이 때, 재귀적으로 왼쪽 자식 노드와 오른쪽 자식 노드를 초기화 하면서 트리 내 노드를 모두 초기화한다.

 

3. 각 쿼리마다 루트 노드에서부터 [a:b]에서의 최댓값, 최솟값을 재귀적으로 구한다.

 

3 - 1. 찾는 범위와 현재 노드에 해당하는 범위를 비교한다.

 

3 - 2. 겹치지 않으면 넘어가고, 포함되면 현재 노드의 값을 반환하고, 아니라면 왼쪽 자식과 오른쪽 자식에 재귀적으로 탐색한다.

 

4. 쿼리 결과를 출력한다.

---

고찰

세그먼트 트리를 구현하기 위해서는 크게 3가지 과정이 필요하다.

 

1. 세그먼트 트리 크기 할당 (4 × n + 1)

 

2. 세그먼트 트리의 각 노드 값 구하기 (재귀)

 

3. 세그먼트 트리에서 원하는 범위의 결과 값 탐색하기 (재귀)