BOJ - 10868번, 최솟값 문제 Segment Tree를 이용한 풀이

이번 문제는 주어진 N개의 정수들에 대해 M번의 구간 최솟값을 묻는 질의에 올바른 답을 반환하는 알고리즘을 구현하는 것이 목표입니다.

 

물론, 구간의 최솟값을 확인하기 위해 linear한 탐색 방식을 취할 수 있겠지만, 이렇게 하는 경우

 

- worst case

100,000(N의 최댓값) x 100,000(M의 최댓값) = 10^12번의 연산

 

위와 같이 연산의 횟수가 너무 커서 시간 초과를 결과로 받게 될 것입니다.

 

따라서 지난번에 정리한 세그먼트 트리의 개념을 구간 합을 구하는 대신 최솟값을 구할 수 있도록 변형해서 이번 문제를 풀이하는 방식을 채택해 봤습니다.

https://kkkdh.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%AC

세그먼트 트리 (Segment Tree) 개념 정리

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

10868번: 최솟값

---

문제 설명

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

---

풀이 과정 정리

앞서 정리한 바와 같이 세그먼트 트리 자료구조를 구축한 뒤에 질의를 응답하면, 다음과 같은 시간 복잡도와 공간 복잡도를 갖게 됩니다.

 

- 시간 복잡도

트리 구축: O(NlogN)

한 번의 구간 최솟값 질의: O(N + K(max N)), 여기서 K는 최솟값을 구하는 구간의 크기를 의미

 

- 공간 복잡도

트리: O(NlogN)

 

트리를 구축하는데 O(NlogN)의 공간 복잡도가 필요한 이유는 트리의 높이가 logN이고, 최하단의 트리의 너비가 N이기 때문입니다.

 

이렇게 트리를 구축하기 위해 트리의 모든 노드를 재귀적으로 한 번씩 탐색하며, 구간의 최솟값을 계산하는 과정을 진행하고, 두 개의 값에 대한 최솟값을 판단하기 위해서는 상수 시간 복잡도가 소모되기 때문에, 트리 구축에 드는 시간 복잡도 또한 O(NlogN)이라고 판단했습니다.

init 함수를 이용해서 세그먼트 트리를 구축한다. (각 노드는 구간의 최솟값을 갖는다.)

기존에 정리한 세그먼트 트리 구축 과정에서 구간합을 세그먼트 트리의 각 노드에 저장하는 대신 해당하는 구간의 최솟값을 저장할 수 있도록 하는 findMin() 함수만 다음과 같이 구현하면

세그먼트 트리를 이용해 구간의 최솟값을 구하는 함수

참고로 세그먼트 트리의 크기는 다음과 같이 선언해서 사용했습니다.

log 100000 = 대략 10 ~ 20 사이의 값이므로

로그의 밑이 2이고, 2의 20승이면(2^20), 대략 1,000,000이므로 10만보다 훨씬 크기 때문에 트리의 높이를 커버하고도 남는다고 판단해서 저 정도로 값을 넣어줬습니다.

---

제출한 코드 (C++)

#include <iostream>
#include <algorithm>
#define MAX_ARR 100001
#define MAX 1000000001
using namespace std;

int n, m;
int arr[MAX_ARR];
int tree[2000001];

int init(int start, int end, int node) {
	if (start == end) return tree[node] = arr[start];
	int mid = (start + end) / 2;
	//divide current problem to two sub problems recursively (left child + right child)
	return tree[node] = min(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}

// start ~ end 사이의 노드에서 최솟값을 찾는다.
int findMin(int start, int end, int node, int left, int right) {
	if (left > end || right < start) return MAX; //ouf of the range
	//cout << "current site: " << start << " " << end << endl;
	if (left <= start && end <= right) return tree[node]; //in the range

	int mid = (start + end) / 2;
	// 구간이 겹치는 경우 맞는 경우에서 최솟값을 찾도록 재귀적으로 findMin 함수를 호출한다.
	return min(findMin(start, mid, 2 * node, left, right), findMin(mid + 1, end, 2 * node + 1, left, right));
}

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

	cin >> n >> m;

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

	init(0, n - 1, 1);

	for (int i = 0; i < m; i++) {
		int start, end;
		cin >> start >> end;
		cout << findMin(0, n - 1, 1, start - 1, end - 1) << "\n";
	}

	return 0;
}