[C++ 백준 풀이][Gold I] 2357번 : 최솟값과 최댓값 / 10868번 : 최솟값 (세그먼트 트리 응용)

 

이 포스트는 프로그래밍 문제 사이트 백준 Online Judge의 2357번 : '최솟값과 최댓값' 문제와 10868번 : '최솟값' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 세그먼트 트리의 응용에 대해서 다룰 것입니다.

 

 

2357번 : 최솟값과 최댓값

 

N개의 정수를 입력받고, M개의 구간이 주어졌을 때 각 M개의 구간 내에서의 최솟값과 최댓값을 출력하는 문제입니다.

M개의 구간마다 다시 탐색을 수행하는 것은 시간적으로 불가능하기 때문에 짧은 시간 안에 최솟값과 최댓값을 찾는 알고리즘을 이용해야 합니다. (일반적인 탐색으로는 불가능함)

이를 위해서 세그먼트 트리의 응용이 필요한데, 이를 아래에서 다루도록 하겠습니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <cmath>
#include <vector>
#define INF 1000000001
using namespace std;

vector<int> Arr;
vector<pair<int, int>> Tree; // first : min, second : max

int initTreeMin(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node].first = Arr[Begin];
    int Mid = (Begin+End)/2;
    return Tree[Node].first = min(initTreeMin(Begin, Mid, Node*2), initTreeMin(Mid+1, End, Node*2+1));
}

int initTreeMax(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node].second = Arr[Begin];
    int Mid = (Begin+End)/2;
    return Tree[Node].second = max(initTreeMax(Begin, Mid, Node*2), initTreeMax(Mid+1, End, Node*2+1));
}

int findMin(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return INF;
    if(Left <= Begin && Right >= End) return Tree[Node].first;
    int Mid = (Begin+End)/2;
    return min(findMin(Begin, Mid, Node*2, Left, Right), findMin(Mid+1, End, Node*2+1, Left, Right));
}

int findMax(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return -INF;
    if(Left <= Begin && Right >= End) return Tree[Node].second;
    int Mid = (Begin+End)/2;
    return max(findMax(Begin, Mid, Node*2, Left, Right), findMax(Mid+1, End, Node*2+1, Left, Right));
}

int main() {
    int N, M, data, a, b;
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++) {
        scanf("%d", &data);
        Arr.push_back(data);
    }
    Tree.resize(N*4);
    initTreeMin(0, N-1, 1);
    initTreeMax(0, N-1, 1);
    for(int i=0; i<M; i++) {
        scanf("%d %d", &a, &b);
        printf("%d %d\n", findMin(0, N-1, 1, a-1, b-1), findMax(0, N-1, 1, a-1, b-1));
    }
}

 

이 문제의 핵심 아이디어는, 세그먼트 트리를 구현하여 기존의 Key 값인 구간 합을 저장하는 것이 아닌, 두 개의 값 Min과 Max를 저장하는 것입니다.

예를 들어 0~3의 최상위 노드에서는 0~3 구간의 Min 값과 Max 값을 저장하고, 또 각각의 0~1과 2~3 구간의 노드에서는 각각의 구간의 Min 값과 Max 값을 저장하도록 하는 것입니다.

이를 위해 Tree의 형태를 pair로 선언하여 Min 전용 Node와 Max 전용 Node가 따로 존재하도록 하였습니다.

 

이 문제가 기존의 세그먼트 트리 구현보다 쉬운 점은, 값을 update 해줄 필요가 없다는 것입니다.

따라서 initialize 함수만 구현하고 바로 find 기능만 구현하면 문제를 해결할 수가 있습니다.

어려운 점은 문제를 보고 세그먼트 트리의 응용을 떠올리지 못하면 접근하기가 어렵다는 것입니다.

 

우선 Tree의 Size는 로그 계산 없이 넉넉하고 단순하게 N의 4배로 잡았습니다.

그리고 Min과 Max 값을 Tree에 저장해야 하는데, 이를 위해서 따로 두 개의 함수를 잡았습니다.

init 함수는 기존 세그먼트 트리의 초기화 함수와 동일하게 작동하지만, 마지막 return 부분에서 두 그룹을 나누어 최소 및 최댓값을 리턴하는 것이 특징입니다.

재귀적으로 쪼개어 들어가면서 하나가 남았을 때(Begin = End) Arr의 해당 주소의 노드 값을 Key로 저장합니다. (1개 노드의 최솟값과 최댓값은 당연히 그 노드의 Key 값이기 때문)

 

find 함수는 세그먼트 트리에서 각각의 극값을 찾아서 리턴하는 함수입니다.

findMin 함수를 기준으로 설명하겠습니다.

Left가 End보다 커지거나 Right가 Begin보다 작아지는 경우에는 그 범위에서 절대로 최솟값이 나오지 않도록 INF 값을 리턴하도록 합니다.

Left~Right 범위가 Begin~End 범위를 포함하는 경우에는 그냥 그 구간의 최솟값을 리턴해주면 됩니다. (더 쪼개서 탐색을 할 필요가 없음)

 

함수를 모두 작성하였으면, 각 케이스에 대해 입력받은 구간에서 findMin과 findMax를 수행한 값을 순차적으로 출력만해주면 해결이 됩니다.

 

 

위의 풀이대로 작성한 코드를 제출해보면, 164ms의 시간에 모든 테스트케이스를 통과했음을 확인할 수 있습니다.

세그먼트 트리의 구현을 요구하는 문제다보니 범위 설정에서 헷갈리는 부분이 조금 있을 수도 있는 문제였습니다.

 

 

10868번 : 최솟값

 

이 문제는 위의 문제의 축소판에 가까운 문제입니다.

모든 입력이 같고 단지 구간에서 최솟값만 출력하면 됩니다.

따라서 위의 문제의 풀이 코드에서 일부를 제거하여 제출하면 됩니다.

 

↓ 풀이 코드는 아래 접은 글 내부에 정리되어 있습니다.

#include <cstdio>
#include <cmath>
#include <vector>
#define INF 1000000001
using namespace std;

vector<int> Arr;
vector<int> Tree;

int initTreeMin(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node] = Arr[Begin];
    int Mid = (Begin+End)/2;
    return Tree[Node] = min(initTreeMin(Begin, Mid, Node*2), initTreeMin(Mid+1, End, Node*2+1));
}

int findMin(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return INF;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    return min(findMin(Begin, Mid, Node*2, Left, Right), findMin(Mid+1, End, Node*2+1, Left, Right));
}

int main() {
    int N, M, data, a, b;
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++) {
        scanf("%d", &data);
        Arr.push_back(data);
    }
    Tree.resize(N*4);
    initTreeMin(0, N-1, 1);
    for(int i=0; i<M; i++) {
        scanf("%d %d", &a, &b);
        printf("%d\n", findMin(0, N-1, 1, a-1, b-1));
    }
}

 

코드 내용 자체는 동일하기 때문에 코드에 대한 설명은 생략하겠습니다.

Max와 관련된 함수와 변수들을 지워주면 됩니다.

 

 

풀이를 제출해보면 역시 동일한 방식으로 채점이 되며 짧은 시간 안에 모든 테스트케이스를 통과함을 확인할 수 있습니다.