[BOJ] 백준 10868번: 최솟값

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

10868번: 최솟값

 

주어진 문제의 크기를 보고 알맞은 시간 복잡도의 자료구조와 알고리즘을 선택하고 설계하는 것이 중요합니다. 기껏 프로그램을 구현했는데, 시간초과로 인해 처음부터 다시 풀어야 하는 상황은 피해야 합니다.

 

naive한 풀이로는 아래 코드처럼 매 query마다 a번째 정수부터 b번째 정수를 탐색하면서 최솟값을 찾아 출력하는 O(MN)의 풀이를 생각해볼 수 있습니다. 다만 N과 M 모두 최대 10만이므로 1초에 약 1억 번의 연산을 수행한다고 할 때 1초 내에 통과할 수 없음을 알 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int N, M, a[100001], l, r;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	
	for(int i = 1; i <= N; ++i){
		cin >> a[i];	
	}

	for(int i = 0; i < M; i++){
		cin >> l >> r;
		cout << *min_element(a+l, a+r+1) << '\n';
	}
}

 

매 query마다 구간이 주어지고 그 구간 내에서 일정한 동작을 요구하는 문제는 전형적인 인덱스 트리(indexed tree), 세그먼트 트리(segment tree) 문제입니다. 다른 예로 구간 합 구하기(백준 2042), 구간 곱 구하기(백준 11505) 문제 등이 있습니다. 이러한 문제들에 대해서도 추후 다뤄보겠습니다. 모든 세그먼트 트리 문제는 indexed tree로 풀 수 있지만 그 역은 성립하지 않습니다. 따라서 indexed tree로 풀이합니다.

 

인덱스 트리는 구성하는 방법과 동작 등을 이해하고 나면 빠른 시간 내에 구간에 대한 query를 수행할 수 있는 강력한 도구입니다. 잘 이해가 안가면 한번쯤 외워보고 여러 번 반복해서 보시는 것을 추천드립니다. 어느샌가 빠르게 인덱스 트리를 설계할 수 있게 되실 겁니다. 코드는 다음과 같습니다.

 

#include <bits/stdc++.h>
#define SIZETR (262144) // 2^18
using namespace std;

const int INF = 0x7fffffff;
int N, M, a[100001], l, r;
int tree[SIZETR]; 
int OFFSET = 1;

void init(){
	while(OFFSET < N) OFFSET <<= 1;
	for(int i = 0; i < N; ++i){
		tree[OFFSET + i] = a[i];
	}	
	for(int i = N; i < OFFSET; ++i){
		tree[OFFSET + i] = INF;
	}
	for(int i = OFFSET - 1; i > 0; --i){
		tree[i] = min(tree[i << 1], tree[(i << 1) +1]);
	}
}

int query(int left, int right){
	left += (OFFSET - 1);
	right += (OFFSET - 1);
	int res = INF;
	while(left <= right){
		if(left % 2 == 1) res = min(res, tree[left++]);
		if(right % 2 == 0) res = min(res, tree[right--]);
		left >>= 1;
		right >>= 1;
	}
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	
	for(int i = 0; i < N; ++i){
		cin >> a[i];	
	}
	
	init();
	
	while(M--){
		cin >> l >> r;
		cout << query(l, r) << '\n';
	}
}

 

Perfect binary tree라고 보시면 됩니다. init() 함수가 인덱스 트리를 구성하는 함수입니다. leaf node에 주어진 값들을 채워넣고 나머지 빈 구간에는 이번 문제처럼 최솟값을 찾는 경우 가장 큰 값(INF)을, 구간 합 구하기의 경우 0을, 구간 곱 구하기의 경우 1을 채워줍니다.

 

while(OFFSET < N) OFFSET <<= 1;

OFFSET은 leaf node의 시작 index로 주어진 수들의 갯수 N 이상인 가장 작은 2의 거듭제곱수입니다. 따라서 위 코드를 통해 init() 함수에서 OFFSET을 구해줍니다. 주어진 문제에서 N은 최대 10만까지 주어질 수 있으므로 10만 이상인 가장 작은 2의 거듭제곱수는 2^17(131,072)입니다. 트리의 사이즈를 의미하는 SIZETR은 OFFSET이 최대 2^17까지 가능하므로 여기에 2를 곱한 값인 2^18(262,144)로 설정한 것입니다. 

 

부모 노드의 경우 자식 노드를 대표하는 값을 넣어줍니다. 이번 문제의 경우 최솟값을 구하는 문제이니 부모 노드는 자식 노드 중 최소가 되는 값을 채워주고, 구간 합, 곱 구하기 문항의 경우 각각 자식 노드의 합과 곱을 채워주게 됩니다.

 

인덱스 트리에 익숙하지 않으실 경우 직접 코드를 보면서 문제의 sample input을 가지고 init() 함수를 따라 종이에 직접 인덱스 트리를 그려보는 것을 추천드립니다. 0번 index는 구현의 편의상 사용하지 않으며 1번 index가 트리의 root node가 되는 것을 유의해주세요.  그려보신 후에 query() 함수를 따라 구간에 대한 최솟값을 처리하는 과정을 직접 해보시는 것을 추천드립니다. 

 

left % 2 == 1일 경우는 left가 두 자식 노드 중 오른쪽에 위치한 경우이므로 그 부모 노드는 "left와 right 사이에 포함되지 않는 left - 1"과 left에 대한 대푯값이 됩니다. 따라서 그 부모 노드로 올라가서 처리하는 것이 아닌 "left의 값"에 대해서 처리한 후 다음(오른쪽) 구간(left++)의 부모 노드(left /= 2)로 넘어가게 됩니다. (left의 오른쪽 구간은 left와 right 사이에 포함되므로)

 

right % 2 == 0일 경우는 right가 두 자식 노드 중 왼쪽에 위치한 경우이므로 그 부모 노드는 "left와 right 사이에 포함되지 않는 right + 1"과 right에 대한 대푯값이 됩니다. 따라서 그 부모 노드로 올라가서 처리하는 것이 아닌 "right의 값"에 대해서 처리한 후 다음(왼쪽) 구간(right--)의 부모 노드(right /= 2)로 넘어가게 됩니다. (right의 왼쪽 구간은 left와 right 사이에 포함되므로)

 

인덱스 트리는 complete binary tree이므로 구현을 배열로 쉽게 할 수 있습니다.

부모 노드의 index를 i 라고 할 때 왼쪽 자식 노드의 index는 2*i, 오른쪽 자식 노드의 index는 2*i + 1임을 확인할 수 있습니다. 반대로 자식 노드의 index를 i라고 한다면 부모 노드의 index는 i / 2 임을 확인할 수 있습니다. (정수 연산)

 

위 코드와 같이 구현할 경우 M번의 query에 대해서 각 query 당 logN의 수행시간이 필요하므로 시간복잡도는 O(MlogN)입니다.