최솟값과 최댓값

백준 2357

GOLD I

1. 문제 내용
2. 해결 방안
3. 풀이 코드

---

문제 내용

문제 링크

해결 방안

주어진 정수들에 대해 매 구간이 주어지면, 해당 범위 내의 최솟값과 최솟값을 각각 출력하면 된다. N개의 정수와 M개의 범위가 주어질 때, 범위가 주어질 때마다 일일이 찾는 방법은 시간복잡도가 O(NM)이 나오기 때문에 시간이 오래 걸린다. 때문에, 주어진 데이터 세트의 특정 범위에 있는 데이터들에 대해 연산하는 데에 특화된 자료구조인 세그먼트 트리를 사용해야 한다.

우선, 세그먼트 트리를 생성해야 한다. 세그먼트 트리의 리프 노드는 주어진 각 데이터들이고, 리프 노드가 아닌 노드들은 임의의 범위에 대한 쿼리 값이 저장된다. 재귀를 통해 리프 노드가 나올 때까지 dfs 방식으로 반복하고, 리프 노드에 도달하면 주어진 데이터를 인덱스별로 저장한다.

각 범위가 주어졌을 때의 쿼리를 위한 함수도 만들어야 한다. 현재 범위가 주어진 탐색 범위 내에 있는 지를 판별하여, 만약 범위를 벗어나면 다시 돌아가도록 한다. 만약 완전히 범위 내에 있다면 현재 위치의 쿼리 결과를 반환하고, 일부 걸친 경우에는 두 부분으로 나누어 다시 쿼리를 진행한다. 이 문제에서의 세그먼트 트리의 작동 과정에 대해서는 코드를 통해 확인하도록 한다.

세그먼트 트리(Segment Tree)란?

이 설명을 보기에 앞서 무려 BOJ에서 제공하는 자료에서 너무나도 잘 설명되어 있으니 꼭 읽어보기를 추천한다.

세그먼트 트리(segment tree)는 연속적으로 존재하는 여러 개의 데이터에 대해, 특정한 구간의 데이터를 쿼리(query)하는 데에 특화된 데이터 구조이다. 다시 말해, 주어진 데이터 세트에서 특정한 범위 내의 데이터들의 합이나 곱, 또는 최댓값이나 최솟값을 구하는 등의 탐색부터 데이터 변조까지의 과정을 보다 효율적으로 할 수 있게 만들어진 그래프 트리라고 볼 수 있다. 임의의 데이터 세트를 세그먼트 트리로 만드는 데에는 O(Nlog₂N)만큼의 시간복잡도를 가지고, 만들어진 세그먼트 트리로는 O(log₂N)에 쿼리를 수행할 수 있다. 쿼리가 O(log₂N)에 수행될 수 있는 이유는 N개의 데이터에 대해 log₂N의 높이를 가지기 때문인데, 세그먼트 트리는 Full Binary Tree의 형태를 띠므로 높이가 log₂N인 트리의 최대 노드의 개수는 Perfect Binary Tree가 만들어질 때인 2^(log₂N + 1) - 1개이다.

풀이 코드

#include <iostream>
#include <vector>
#include <cmath>
#define MAX_N 100000
#define MAX_RANGE 1000000000

using namespace std;
using min_max = pair<int, int>;

// 정수의 개수와 쿼리의 개수
int n, m;
// 데이터 세트 저장
int arr[MAX_N + 1];
// 최솟값과 최댓값을 위한 세그먼트 트리
vector<int> min_tree, max_tree;

// 세그먼트 트리 생성
void init(int node, int start, int end) {
    // 리프 노드는 두 트리가 동일
    if(start == end)
        min_tree[node] = max_tree[node] = arr[start];
    // 리프 노드가 아닌 경우에는 min_tree와 max_tree에 각각 최솟값과 최댓값을 저장
    else {
        init(node * 2, start, (start + end) / 2);
        init(node * 2 + 1, (start + end) / 2 + 1, end);
        min_tree[node] = min(min_tree[node * 2], min_tree[node * 2 + 1]);
        max_tree[node] = max(max_tree[node * 2], max_tree[node * 2 + 1]);
    }
}

// 최솟값과 최댓값을 반환하는 쿼리
min_max query(int node, int start, int end, int left, int right) {
    // 만약 범위 밖이면 최솟값은 범위 외의 값을, 최댓값은 0을 반환
    if(end < left || start > right)
        return {MAX_RANGE + 1, 0};

    // 현재 범위가 탐색 범위에 완전히 감싸지면, 현재 위치의 최솟값과 최댓값 반환
    if(start >= left && end <= right)
        return {min_tree[node], max_tree[node]};
    
    // 현재 범위의 일부가 탐색 범위 내에 걸쳐 있다면,
    // 좌측 노드와 우측 노드의 최솟값과 최댓값을 비교하여 반환
    min_max mm_left = query(node * 2, start, (start + end) / 2, left, right);
    min_max mm_right = query(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    return {min(mm_left.first, mm_right.first), max(mm_left.second, mm_right.second)};
}

int main() {
    // Fast IO
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    // 정수의 개수와 쿼리의 개수 입력
    cin >> n >> m;

    // 높이가 H인 트리는 2^(H+1)-1개의 노드를 필요로 하나,
    // 루트 노드의 인덱스가 1부터 시작하므로 최대 2^(H+1)개의 공간이 필요함
    int height = (int)ceil(log2(n));
    min_tree = vector<int>(1 << (height + 1));
    max_tree = vector<int>(1 << (height + 1));

    // 범위가 1부터 N까지이므로, 인덱싱을 1부터 시작
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    
    // 세그먼트 트리 생성
    init(1, 1, n);

    // 각 범위에 대한 최솟값과 최댓값 출력
    int left, right;
    min_max result;
    for(int i = 0; i < m; i++) {
        cin >> left >> right;
        result = query(1, 1, n, left, right);
        cout << result.first << ' ' << result.second << '\n';
    }
    return 0;
}

---