반응형
https://www.acmicpc.net/problem/10868
참고
- 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree)
- 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree)
세그먼트 트리의 노드에 저장된 값은 아래 두 노드 중 작은 값이어야 한다.
isMin 함수를 이용하여 더 작은 값을 판단하여 init을 하면서 tree에 저장한다.
int isMin(int a, int b)
{
return (a < b) ? a : b;
}
int init(int left, int right, int node)
{
if (left == right) return tree[node] = arr[left];
int mid = (left + right) / 2;
return tree[node]
= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}
마찬가지로 특정 구간에 대해 isMin으로 더 작은 값을 판단하면 된다.
이때, 구간을 벗어나는 경우는 주어진 값 중 가장 큰 값을 return 해야 주어진 구간에서 작은 값을 찾을 수 있다.
int getMin(int left, int right, int a, int b, int node)
{
if (b < left || right < a) return 0x7fff0000;
if (a <= left && right <= b) return tree[node];
int mid = (left + right) / 2;
return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}
이 문제에서는 구간을 바꾸지 않으므로 update 함수는 필요없다.
전체 코드는 다음과 같다.
#include <stdio.h>
int N, M;
int arr[100100];
int tree[400400];
int isMin(int a, int b)
{
return (a < b) ? a : b;
}
int init(int left, int right, int node)
{
if (left == right) return tree[node] = arr[left];
int mid = (left + right) / 2;
return tree[node]
= isMin(init(left, mid, node * 2), init(mid + 1, right, node * 2 + 1));
}
int getMin(int left, int right, int a, int b, int node)
{
if (b < left || right < a) return 0x7fff0000;
if (a <= left && right <= b) return tree[node];
int mid = (left + right) / 2;
return isMin(getMin(left, mid, a, b, node * 2), getMin(mid + 1, right, a, b, node * 2 + 1));
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);
init(1, N, 1);
for (int i = 0; i < M; i++)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", getMin(1, N, a, b, 1));
}
return 0;
}
Bottom-Up 방식은 다음과 같다.
먼저 tree를 최악의 값으로 모두 변경한다.
start Index를 구하기 위해 n을 구했으므로, 1 << (n + 1)이 모든 tree의 최대 index가 된다.
for (n = 1; (1 << n) <= N; n++);
start = 1 << n;
start--;
int maxTreeIndex = (1 << (n + 1));
for (int i = 0; i <= maxTreeIndex; i++) tree[i] = 0x7fff0000;
tree는 들어오는 값과 비교하면서 더 작은 값으로 바꾼다.
int isMin(int a, int b)
{
return (a < b) ? a : b;
}
void update(int index, int value)
{
index += start;
while (index > 1)
{
tree[index] = isMin(tree[index], value);
index /= 2;
}
}
getMin도 ans를 가장 큰 값으로 설정한 후, 가장 작은 값을 구하도록 수정하면 된다.
int getMin(int left, int right)
{
int ans = 0x7fff0000;
left += start;
right += start;
while (left < right)
{
if (left % 2 == 0) left /= 2;
else
{
ans = isMin(ans, tree[left]);
left += 1;
left /= 2;
}
if (right % 2 == 1) right /= 2;
else
{
ans = isMin(ans, tree[right]);
right -= 1;
right /= 2;
}
}
if (left == right) ans = isMin(ans, tree[left]);
return ans;
}
전체 코드는 다음과 같다.
#include <stdio.h>
int N, M;
int tree[400400];
int start;
int isMin(int a, int b)
{
return (a < b) ? a : b;
}
void update(int index, int value)
{
index += start;
while (index > 1)
{
tree[index] = isMin(tree[index], value);
index /= 2;
}
}
int getMin(int left, int right)
{
int ans = 0x7fff0000;
left += start;
right += start;
while (left < right)
{
if (left % 2 == 0) left /= 2;
else
{
ans = isMin(ans, tree[left]);
left += 1;
left /= 2;
}
if (right % 2 == 1) right /= 2;
else
{
ans = isMin(ans, tree[right]);
right -= 1;
right /= 2;
}
}
if (left == right) ans = isMin(ans, tree[left]);
return ans;
}
int main()
{
int n;
scanf("%d %d", &N, &M);
for (n = 1; (1 << n) <= N; n++);
start = 1 << n;
start--;
int maxTreeIndex = (1 << (n + 1));
for (int i = 0; i <= maxTreeIndex; i++) tree[i] = 0x7fff0000;
for (int i = 1; i <= N; i++)
{
int x;
scanf("%d", &x);
update(i, x);
}
for (int i = 0; i < M; i++)
{
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", getMin(a, b));
}
return 0;
}
반응형
'알고리즘 > BAEKJOON' 카테고리의 다른 글
BOJ 5397 : 키로거 (0) | 2023.01.18 |
---|---|
BOJ 2357 : 최솟값과 최댓값 (0) | 2023.01.16 |
BOJ 1708 : 볼록 껍질 (0) | 2022.12.28 |
BOJ 1935 : 후위 표기식2 (1) | 2022.12.26 |
BOJ 1918 : 후위 표기식 (0) | 2022.12.26 |
댓글