boj, 백준) 2357. 최솟값과 최댓값 (C / C++)

1. 문제 링크

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

2357번: 최솟값과 최댓값

2. 문제 개요

 1~100,000개의 정수들이 있을 때 [a, b] 구간의 최솟값과 최댓값을 1~100,000번 찾는 문제.

 

3. 문제 힌트

 최소,최댓값을 찾는 것은 O(N)이고 찾으라는 명령이 M번 있다면 O(MN)으로 시간 초과이다.

 세그먼트 트리를 사용하여 O(MlogN)으로 문제를 해결할 수 있도록 잘 설계해보자.

 

 

4. 문제 풀이

이해를 돕기 위해 가장 일반적인 즉, 부분합을 구하는 세그먼트 트리를 생각해보자.

각 노드는 '자식들의 합'을 가지고 있다.

그렇다면 이 문제에서는 노드는 어떤 값을 가지고 있어야 할까?

☞바로 자식들의 최솟값과 최댓값을 저장하고 있어야 한다.

 

그래서, data를 세그먼트 트리로 바꾸는 과정만 코드로 살펴보면,

세그먼트 트리 생성자

세그먼트 트리의 Vector는 pair <int, int>이고, first는 최솟값, second는 최댓값을 저장하기 위해 초기값을 위의 그림과 같이 했다.

Data -> Segment tree로 바꾸는 함수 ( 초기화 )

리프 노드로 가면 자신의 값을 그대로 저장한다.

하지만 리프 노드에서 올라갈 때는 두 자식의 최솟값과 최댓값을 구하고 그것이 노드 자기 자신의 값이 된다.

 

일정 구간의 최소 최댓값을 구할 때는 부분합을 구하는 부분과 같다

한 가지 유의할 점은 부분합 때와같이 0을 반환할 것이 아니라 세그먼트 트리 생성자를 구현한 것처럼, 최솟값 최댓값 구하는데 영향이 가지 않도록 최솟값 자리에는 충분히 큰 값, 최댓값 자리에는 충분히 작은 값을 반환하도록 했다.

 

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, m;
vector<int> arr;

class SGT {
public:
	SGT() {}
	SGT(int tree_size) {
		tree.resize(tree_size,make_pair(0x7effffff,-0x7effffff));
	}

	pair<int, int> init_tree(int node, int start, int end)
	{
		if (start == end) {
			tree[node].first = tree[node].second = arr[start];
			return tree[node];
		}
		else
		{
			int mid = (start + end) / 2;
			pair<int, int> left = init_tree(2 * node, start, mid);
			pair<int, int> right = init_tree(2 * node + 1, mid + 1, end);

			tree[node].first = min(left.first, right.first);
			tree[node].second = max(left.second, right.second);
			return tree[node];
		}
	}

	//pair <min, max>
	pair<int, int> find_val(int node, int start, int end, int a, int b)
	{
		//a,b는 고정된 값
		if (end < a || b < start)
			return make_pair(0x7effffff, -0x7effffff);
		if (a <= start && end <= b)
			return tree[node];

		int mid = (start + end) / 2;
		pair<int, int> left = find_val(2 * node, start, mid, a, b);
		pair<int, int> right = find_val(2 * node + 1, mid + 1, end, a, b);
		pair<int, int> ret;
		ret.first = min(left.first, right.first);
		ret.second = max(left.second, right.second);
		return ret;
	}

	vector<pair<int, int>> tree;
};

int main()
{
	scanf("%d %d", &n, &m);
	arr.resize(n);
	//0 ~ n-1
	for (int i = 0; i < n; ++i)
		scanf("%d", &arr[i]);

	int tree_h = (int)ceil(log2(n));
	int tree_size = 1 << (tree_h + 1);
	SGT sgt_tree(tree_size);

	//convert arr to tree
	sgt_tree.init_tree(1, 0, n - 1);

	for (int i = 0; i < m; ++i)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		pair<int, int> ans;

		ans = sgt_tree.find_val(1, 0, n - 1, a - 1, b - 1);

		printf("%d %d\n", ans.first, ans.second);
	}

	return 0;
}

 

6. 결과 사진

지적, 댓글 언제나 환영입니다~