[백준] No.2357 - 최솟값과 최댓값 (C++, 세그먼트 트리)

문제

 

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

2357번: 최솟값과 최댓값

 

 

풀이

 

solved.ac 난이도: Gold 1

 

세그먼트 트리를 응용하여 해결하는 문제.

기존의 세그먼트 트리는 구간의 합을 트리의 부모 노드에 저장했다면

본 문제에 적용하는 세그먼트 트리는 구간의 최솟값과 최댓값을 저장한다.

 

세그먼트 트리에 대해서 잘 모르겠다면 백준님의 게시글을 참조하자.

세그먼트 트리 (Segment Tree) - Baekjoon Online Judge

 

처음 풀때는 vector<pair<int,int>> tree를 이용하여 하나의 트리구조에 최솟값과 최댓값을 모두 저장하였지만

계속 시간초과가 발생하여 구간의 최솟값만 저장하는 min_tree와 최댓값을 저장하는 max_tree로 구분하였다.

 

일단 tree의 크기는 숫자의 개수 N를 모두 리프 노드로 저장할 수 있는 크기여야 한다.

따라서 log2(N)의 값을 올림(ceil)해준 값이 트리의 높이(h)가 된다.

tree는 루트 노드를 포함해 주어 크기를 (1<<(h + 1))로 설정해준다.

 

이제 세그먼트 트리를 초기화해주는 

void init(int node, int start, int end) 함수를 구현하자.

 

 

void init(int node, int start, int end){
  if(start == end){
    min_tree[node] = max_tree[node] = arr[start]; 
    return;
  }else{
    init(node*2, start, (start + end)/2 );
    init(node*2 +1 , (start + end)/2 +1, end);
    min_tree[node] = min(min_tree[node*2], min_tree[node*2 +1]); 
    max_tree[node] = max(max_tree[node*2], max_tree[node*2 +1]);
    return;
  }
}

 

 

node는 현재 트리 노드의 인덱스 값을 나타낸다.

루트 node는 1에서부터 시작하는데, 그 이유는 1에서 부터 시작하면 선형 배열에서 node의 왼쪽 자식 노드는 node*2 의 인덱스를node의 오른쪽 자식 노드는 node*2 +1 의 인덱스를 가지기 때문이다.

 

start와 end는 현재 노드가 포함하는 구간의 범위 값이다.

만약 start == end라면 리프 노드를 나타내는 것이다.

따라서 최소 트리와 최대 트리를 해당 값으로 초기화해준다.

 

start != end라면

현재 노드가 가지는 범위를 반으로 나누어 각각의 재귀 호출해준다.

그 후, 자식 노드들은 이미 값을 가지고 있으므로 왼쪽 노드와 오른쪽 노드의 값을 비교해 최솟값, 최댓값을 찾아 설정해준다.

 

 

세그먼트 트리를 초기화해주었다면 이번에는 left~right 범위에서 최솟값과 최댓값을 구해 반환해주는 함수

pair<int,int> findMinMAx(int node, int start, int end, int left, int right) 를 구현하자.

 

 

pair<int,int> findMinMAx(int node, int start, int end, int left, int right){
  if(left >end || right < start ){
    return make_pair(INT32_MAX, 0);
  }else if(left <=start && end <= right){
    return make_pair(min_tree[node],max_tree[node]);
  }else{
    pair<int,int> l,r;
    l = findMinMAx(node*2, start,(start + end)/2 , left,right);
    r = findMinMAx(node*2 +1, (start + end)/2 +1, end , left,right);
    return make_pair(min(l.first, r.first),max(l.second, r.second));
  }
}

 

init함수와 동일하게 node는 트리에서의 해당 노드의 인덱스 값, start와 end는 해당 노드가 구간의 최솟,최댓값을 저장하고 있는 범위이다.

 

여기서 [left, right]와 [start, end]의 포함 관계는 4가지가 존재한다.

 

1. [left, right]와 [start, end]가 겹치지 않는 경우

 이 경우는 구해야 하는 범위가 해당 노드의 포함 구간과 전혀 다르므로 최솟값으로는 int형의 최댓값을, 최댓값으로는 0을 반환하여 

최솟값과 최댓값을 구하는데 영향이 없도록 만든다. 

 

2. [left, right]가 [start, end]를 포함하는 경우

이 경우는 구해야 하는 범위[left, right] 안에 해당 노드의 범위[start, end]가 포함되어 있기 때문에

그때의 최댓값과 최솟값을 이용할 필요가 있다. 따라서 해당 노드에서의 최솟값과 최댓값을 반환해주자.

 

3. [start, end]가 [left, right]를 포함하는 경우

노드의 구간이 구하려는 범위[left, right] 보다 크기 때문에 해당 노드의 최댓, 최솟값은 [left, right]에서의 값과는 다를 수가 있다.

따라서  노드의 범위[start, end]가 구하려는 범위[left, right] 안에 포함될 수 있도록 하위 노드를 탐색해야 한다.

 

4.  [left, right]와 [start, end]가 겹쳐지는 부분이 있는 경우

이 경우도 노드의 범위[start, end]가 [left, right] 안에 포함될 수 있도록 왼쪽 노드와 오른쪽 노드를 재귀 호출하여 하위 노드를 탐색해야 한다.

 

3,4번의  경우에만 왼쪽 노드와 오른쪽 노드를 재귀 호출하여 두 노드 중 최솟값과 최댓값을 구해내 반환한다.

 

 

추가적으로 해당 문제를 해결할 때 min_tree와 max_tree를 구분하여도 시간 초과가 발생하였는데

입출력을 scanf와 printf로 바꿔주자 통과되었다...

 

 

코드