백준 2357번 최솟값과 최댓값

- 문제 설명

 

N 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 범위 중에서 제일 작은 정수 또는 제일 큰 정수를 찾아보자.

 

 

- 입력

 

1) N (1 <= N <= 100,000)

2) a, b 쌍 M 개 (1 <= M <= 100,000)

 

 

- 출력

 

M개의 줄에 a, b에 대한 최솟값, 최댓값

 

 

* 문제 풀이의 핵심

 

세그먼트 트리를 사용해서 구간 최솟값, 최대값을 빠르게 찾아야 시간초과가 발생하지 않고 해결할 수 있는 문제입니다.

 

 

1. 세그먼트 트리란?

 

주어진 쿼리에 빠르게 응답하기 위해 만들어진 트리로 주로 이진트리로 구성되며, 모든 인덱스의 값을 활용할 가능성이 높기 때문에 배열을 사용합니다.

 

세그먼트 트리를 통해서 구간 최솟값, 최댓값, 구간합 등을 O(logN) 시간에 구할 수 있게 됩니다.

 

 

ex) 구긴합을 빠르게 구하는 세그먼트 트리

 

1) 트리 생성

 

배열을 생성함으로서 트리를 생성합니다.

 

int input[LEN];

 

* 완전 이진트리이기 때문에 최대 노드의 개수는 2ⁿ-1 입니다. (n은 높이)

 

 

2) 트리의 구성

 

int init(int start, int end, int node) {
	if (start == end) return tree[node] = input[start];
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

 

 

트리의 원소는 구간을 나타냄

 

 

3) 구간합 찾기

 

int sum(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;

	if (left <= start && right >= end) return tree[node];
	int mid = (start + end) / 2;
	return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

 

입력값)

10
75 30 100 38 50 51 52 20 81 5

 

 

입력값의 2~5 인덱스 합 구간

 

 

4) 최종 소스코드

 

#include<iostream>

using namespace std;

const int LEN = 100000;

int tree[LEN * 3];

int input[LEN];

int init(int start, int end, int node) {
	if (start == end) return tree[node] = input[start];
	int mid = (start + end) / 2;
	return tree[node] = init(start, mid, node * 2) + init(mid + 1, end, node * 2 + 1);
}

int sum(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return 0;

	if (left <= start && right >= end) return tree[node];
	int mid = (start + end) / 2;
	return sum(start, mid, node * 2, left, right) + sum(mid + 1, end, node * 2 + 1, left, right);
}

int main() {
	int n;
	cin >> n;

	int i;
	for (i = 0; i < n; i++) {
		cin >> input[i];
	}

	init(0, n - 1, 1);

	cout << sum(0, n - 1, 1, 2, 5) << endl;
}

/*
10
75 30 100 38 50 51 52 20 81 5

*/

 

 

2. 알고리즘

 

최대값, 최솟값을 저장하는 트리를 각 각 생성해야 합니다.

 

1) 최솟값 트리 선언 및 초기화

 

int input[LEN];		// 배열 트리 선언

int initMin(int start, int end, int node) {		// 트리 초기화
	if (start == end) return tree[node].min = input[start];

	int mid = (start + end) / 2;
	return tree[node].min = min(initMin(start, mid, node * 2), initMin(mid + 1, end, node * 2 + 1));
}

 

 

2) 최솟값 구하기

 

int queryMin(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INT_MAX;

	if (left <= start && right >= end) return tree[node].min;

	int mid = (start + end) / 2;
	return min(queryMin(start, mid, node * 2, left, right), queryMin(mid + 1, end, node * 2 + 1, left, right));
}

 

- 구간합 트리 코드를 활용하여, 리턴부분에 덧셈 대신 min 함수를 대입하여 트리 초기화 및 최솟값을 구합니다.

 

 

3. 입출력 가속

 

- a, b 쌍이 최대 100,000개가 주어지기 때문에 입출력 가속을 사용하여 값을 입력 받아야 합니다.

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

 

 

- 소스코드

 

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

using namespace std;

const int LEN = 100000;

typedef struct VAL {
	int min;
	int max;
} VAL;

vector<VAL> tree(LEN * 3);

int input[LEN];

int initMin(int start, int end, int node) {
	if (start == end) return tree[node].min = input[start];

	int mid = (start + end) / 2;
	return tree[node].min = min(initMin(start, mid, node * 2), initMin(mid + 1, end, node * 2 + 1));
}

int initMax(int start, int end, int node) {
	if (start == end) return tree[node].max = input[start];

	int mid = (start + end) / 2;
	return tree[node].max = max(initMax(start, mid, node * 2), initMax(mid + 1, end, node * 2 + 1));
}

int queryMin(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INT_MAX;

	if (left <= start && right >= end) return tree[node].min;

	int mid = (start + end) / 2;
	return min(queryMin(start, mid, node * 2, left, right), queryMin(mid + 1, end, node * 2 + 1, left, right));
}

int queryMax(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return INT_MIN;

	if (left <= start && right >= end) return tree[node].max;

	int mid = (start + end) / 2;
	return max(queryMax(start, mid, node * 2, left, right), queryMax(mid + 1, end, node * 2 + 1, left, right));
}

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

	int n, m;
	cin >> n >> m;

	int i;
	for (i = 0; i < n; i++) {
		cin >> input[i];
	}

	initMin(0, n - 1, 1);
	initMax(0, n - 1, 1);

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

		int minVal = queryMin(0, n - 1, 1, a - 1, b - 1);
		int maxVal = queryMax(0, n - 1, 1, a - 1, b - 1);

		cout << minVal << " " << maxVal << "\n";
	}	
}

 

 

- 문제링크 : www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 참고 : 

1) 블로그1 : blog.naver.com/ndb796/221282210534

2) 블로그2 : www.crocus.co.kr/651