최솟값

알고리즘 구분 : 세그먼트 트리, 자료 구조, 희소성 배열

문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

입력
첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력
M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 출력한다.

예제 입력 1
10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10
예제 출력 1
5
38
20
5

문제 풀이

나는 세그먼트 트리를 공부하기 위해서 일부러 관련 유형의 문제를 찾아서 풀었기에, 바로 세그먼트 트리를 구현하여 문제를 풀었다.
만약 그렇지 않고, 바로 이 문제를 보고 있을 경우, 이 문제에서 M번만큼 반복되며 입력되는 구간 별 최솟값을 출력해야한다는 부분을 통해 시간 제한이 1초이기에 시간 복잡도를 중요하게 생각해야 한다는 것을 파악해야 한다. 그렇기에, 세그먼트 트리 구현을 통해 시간 복잡도를 줄여 나가야 하는 문제임을 파악할 수 있어야 한다.
세그먼트 트리는 트리 구조이기에 시간 복잡도가 O(logN)을 가지게 된다. 그렇기에, 입력받을 때마다 전체 구간을 순회하면서 탐색하는 O(N)의 시간복잡도보다 훨씬 단축되기에, TLE없이 AC를 받을 수 있다.
세그먼트 트리 구현은 가장 일반적인 세그먼트 트리 구현을 진행하면 되는 문제이다. 그렇기에, 세그먼트 트리를 공부하는 입장에서 배울 수 있는 문제이지 않을까 싶다.

먼저 세그먼트 트리를 직접 표현해보면 아래와 같다.

소스 코드에서 init함수가 처음에 N줄만큼 입력된 값들에 대한 세그먼트 트리를 구성하는 함수이며, 이후 M번동안 입력받는 구간에서의 최솟값을 구하는 함수는 findMin함수이다.

init 함수 : 세그먼트 트리를 구현해야 되는 원 배열의 시작 idx와 끝 idx와, 세그먼트 트리의 시작 지점을 매개변수로 하여 세그먼트 트리 구현

findMin 함수 : 찾아야 하는 구간을 left, right 매개변수로 받으며, 해당 배열의 전체 구간의 시작과 끝을 start와 end로, 세그먼트 트리에서 찾기 시작하는 지점을 node 변수로 받아서 범위를 줄여나가며 해당하는 구간에서의 최솟값을 찾는 함수

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define maxNum 100,000

int n, m;
vector<int> num;
vector<int> tree;
int init(int start, int end, int node);
int findMin(int start, int end, int node, int left, int right);

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

    cin >> n >> m;
    tree.resize(4 * n);
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        num.push_back(input);
    }

    init(0, n -1, 1);

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        cout << findMin(0, n - 1, 1, a - 1, b - 1) << endl;
    }

    return 0;
}

// start : 시작 idx, end : 마지막 idx
int init(int start, int end, int node) {
    if(start == end) {
        return tree[node] = num[start];
    }
    int mid = (start + end) / 2;
    
    // 둘 중의 더 최솟값이 해당 노드의 값이 됨
    return tree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}

// start : 시작 idx, end : 끝 idx, left, right : 최솟값을 구하는 범위
int findMin(int start, int end, int node, int left, int right) {
    // 범위 밖에 있는 경우
    if(left > end || right < start) return 1000000001;
    
    // 범위 안에 있는 경우
    if(left <= start && end <= right) return tree[node];
    
    // 범위를 더 쪼개야 하는 경우
    int mid = (start + end) / 2;
    return min(findMin(start, mid, node * 2, left, right), findMin(mid + 1, end, node * 2 + 1, left, right));
}

• 문제 출처 : https://www.acmicpc.net/problem/10868
• 해당 풀이는 백준에서 "맞았습니다!!"판정을 받았습니다.