14438번: 수열과 쿼리 17 
문제 링크: 14438번: 수열과 쿼리 17
개요
배열 크기 n과 쿼리의 수 m이 최대 100,000이므로 매 구간 최솟값을 출력할 때마다 구간을 전부 탐색하는 시간복잡도 O(n×m)의 방식으로는 시간 초과와 마주할 수밖에 없다.
각 구간의 최솟값을 세그먼트 트리에 저장하여 사용해야 한다. 세그먼트 트리의 개념은 아래 블로그에 잘 설명되어있다.
세그먼트 트리(Segment Tree)
풀이
아래 설명할 세 함수는 모두 node, start, end라는 인자를 갖고 있다. node는 세그먼트 트리상에서 현재 노드의 인덱스이며, start와 end는 arr 배열 상에서의 현재 탐색 범위의 양 끝 인덱스이다. 세 함수는 모두 재귀의 형태를 가지는데, 위에서 말한 세 인자는 재귀를 거치며 segTree[node]가 arr[start]부터 arr[end]까지의 범위를 담당하는 노드임이 유지되도록 변화한다.
세그먼트 트리 생성 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
//최솟값 저장하는 세그먼트 트리 만들기
int makeSegTree(int node, int start, int end) {
if (start == end) return segTree[node] = arr[start];
int mid = (start + end) / 2;
int leftRst = makeSegTree(node * 2, start, mid);
int rightRst = makeSegTree(node * 2 + 1, mid + 1, end);
segTree[node] = min(leftRst, rightRst);
return segTree[node];
}
main 함수에서 이 함수를 makeSegTree(1, 1, n)의 형태로 호출할 것이다. 세그먼트 트리의 루트 노드(1, 전체 범위 담당)부터 시작하여 재귀의 형태로 자식 노드로 뻗어 내려가고, 자식 노드의 값을 이용해 부모 노드의 값을 생성하는 방식이다.
start == end인 경우, 리프 노드에 도달했다는 뜻이므로 현재 세그먼트 트리의 노드(segTree[node])에 arr 배열의 값(arr[start])을 대입하고 재귀를 중단해준다.
그 외의 경우, 아직 리프 노드에 도달하지 않았다. 세그먼트 트리에서 인덱스가 node인 노드의 자식 노드의 인덱스는 node * 2, node * 2 + 1이다. 현재 범위를 반으로 나눠 왼쪽 범위의 최솟값과 오른쪽 범위의 최솟값을 재귀를 통해 구한 후 두 값 중 더 작은 값을 현재 세그먼트 트리의 노드에 저장하고 반환해준다.
세그먼트 트리 업데이트 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void updateSegTree(int node, int start, int end, int idx, int newVal) {
//탐색 범위에 갱신할 위치가 포함되지 않는 경우
if (idx < start || end < idx) return;
//현재 범위가 갱신할 위치의 리프 노드인 경우
if (idx == start && start == end) {
segTree[node] = newVal;
return;
}
//갱신할 위치가 현재 탐색 범위에 포함되는 경우
int mid = (start + end) / 2;
updateSegTree(node * 2, start, mid, idx, newVal);
updateSegTree(node * 2 + 1, mid + 1, end, idx, newVal);
segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]); //자식 노드로부터 업데이트
return;
}
이 함수는 arr상에서 idx의 위치에 해당하는 세그먼트 트리의 리프 노드의 값을 newVal로 업데이트해주고, 그 노드의 값에 영향받는 모든 부모 노드의 값 또한 업데이트해준다. makeSegTree 함수와 마찬가지로 main 함수에서는 updateSegTree(1, 1, n, idx, newVal)의 형태로 호출하여 루트 노드부터 시작하여 뻗어내려간다.
현재 탐색 범위에 갱신할 위치가 포함되지 않는 경우, 업데이트 작업을 할 필요가 없으므로 바로 재귀를 중단해준다.
현재 범위가 갱신할 위치의 리프 노드인 경우, 세그먼트 트리의 해당 노드의 값을 업데이트 해주고 재귀를 중단해준다.
그 외의 경우는 현재 탐색 범위가 리프 노드가 아니며, 갱신할 위치가 포함되는 경우이다. 현재 노드는 값을 갱신할 노드의 부모 노드라는 의미이다. 따라서 makeSegTree 함수와 마찬가지로 현재 범위를 나눠 재귀를 통해 자식 노드를 업데이트 한 후, 자식 노드로부터 현재 노드의 값을 업데이트해준다.
부분 합 반환 함수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//탐색 범위의 최솟값 얻기
int getMinVal(int node, int start, int end, int left, int right) {
//탐색 범위가 얻을 범위에 포함되지 않는 경우
if (left > end || right < start) return MAX_A;
//탐색 범위가 얻을 범위에 완전히 포함되는 경우
if (left <= start && end <= right) return segTree[node];
//탐색 범위가 얻을 범위에 걸치는 경우
int mid = (start + end) / 2;
int leftRst = getMinVal(node * 2, start, mid, left, right);
int rightRst = getMinVal(node * 2 + 1, mid + 1, end, left, right);
return min(leftRst, rightRst);
}
left와 right는 최솟값을 얻을 범위이며, 재귀를 거치며 변하지 않는다.
탐색 범위(start ~ end)가 얻을 범위(left ~ right)에 포함되지 않는 경우, 이 부분의 최솟값은 최종 결과에 영향을 미쳐서는 안 되므로 배열의 값으로 들어올 수 있는 정수 중 최댓값보다 1 큰 수를 저장해둔 MAX_A를 반환한다.
탐색 범위(start ~ end)가 얻을 범위(left ~ right)에 완전히 포함되는 경우, 세그먼트 트리에서 해당 노드의 값을 반환하면 된다. 그 외의 경우는 탐색 범위(start ~ end)가 얻을 범위(left ~ right)에 걸치는 경우이다. 위의 두 함수와 마찬가지로 현재 범위를 반으로 나눠 각 탐색 후 두 값 중 최솟값을 반환한다.
전체 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_N 100000
#define MAX_A 1000000001
int arr[MAX_N + 1], segTree[MAX_N * 4 + 4];
int min(int a, int b);
int makeSegTree(int node, int start, int end);
void updateSegTree(int node, int start, int end, int idx, int newVal);
int getMinVal(int node, int start, int end, int left, int right);
int main() {
int n, m;
scanf("%d", &n);
for (int i = 1; i <= n; i++) { //수열 입력받기
scanf("%d", &arr[i]);
}
makeSegTree(1, 1, n); //세그먼트 트리 만들기
scanf("%d", &m);
for (int i = 0; i < m; i++) { //쿼리 입력받기
int cmd, a, b;
scanf("%d %d %d", &cmd, &a, &b);
if (cmd == 1) { //값 변경 쿼리
updateSegTree(1, 1, n, a, b);
}
else { //부분 최솟값 출력 쿼리
printf("%d\n", getMinVal(1, 1, n, a, b));
}
}
return 0;
}
int min(int a, int b) {
return a < b ? a : b;
}
//최솟값 저장하는 세그먼트 트리 만들기
int makeSegTree(int node, int start, int end) {
if (start == end) return segTree[node] = arr[start];
int mid = (start + end) / 2;
int leftRst = makeSegTree(node * 2, start, mid);
int rightRst = makeSegTree(node * 2 + 1, mid + 1, end);
segTree[node] = min(leftRst, rightRst);
return segTree[node];
}
//세그먼트 트리 업데이트하기
void updateSegTree(int node, int start, int end, int idx, int newVal) {
//탐색 범위에 갱신할 위치가 포함되지 않는 경우
if (idx < start || end < idx) return;
//현재 범위가 갱신할 위치의 리프 노드인 경우
if (idx == start && start == end) {
segTree[node] = newVal;
return;
}
//갱신할 위치가 현재 탐색 범위에 포함되는 경우
int mid = (start + end) / 2;
updateSegTree(node * 2, start, mid, idx, newVal);
updateSegTree(node * 2 + 1, mid + 1, end, idx, newVal);
segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]); //자식 노드로부터 갱신
return;
}
//탐색 범위의 최솟값 얻기
int getMinVal(int node, int start, int end, int left, int right) {
//탐색 범위가 얻을 범위에 포함되지 않는 경우
if (left > end || right < start) return MAX_A;
//탐색 범위가 얻을 범위에 완전히 포함되는 경우
if (left <= start && end <= right) return segTree[node];
//탐색 범위가 얻을 범위에 걸치는 경우
int mid = (start + end) / 2;
int leftRst = getMinVal(node * 2, start, mid, left, right);
int rightRst = getMinVal(node * 2 + 1, mid + 1, end, left, right);
return min(leftRst, rightRst);
}