개요

백준 2357: 최솟값과 최댓값

• 입력
  첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

• 출력
  M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

접근 방식

1. 세그먼트 트리의 각 노드에 해당 구간의 최대값과 최솟값을 한번에 저장하기위해 각 노드를 pair로 구성하였다.

2. pair<int,int>의 first값에는 해당 노드가 담당하는 구간의 최솟값, second값에는 해당 노드가 담당하는 최대값이 담겨있다.

3. 2^17이 최초로 10만을 넘어가는 수이므로 트리의 최대 노드 갯수는 2^18을 넘지 않는다. 또한 segTree의 초기값은 0,0으로 설정해줄 것이므로

   		//세그먼트 트리를 0,0으로 초기화해줌 
   		segTree.resize(262144,zeroPair);

   이런식으로 초기화를 하였다.

4. 두 노드의 최솟값 최대값을 비교해서 새로 pair을 만들어야
   하므로 따로 함수를 작성해 빼주었다.
   초기값인 (0,0)과 연산이 된다면 무조건 최솟값이 0으로 바뀔 것이므로 예외처리를 해줬다.

   //두 pair 비교해서 새로운 pair 만들기
   pair<int, int> MakeNewPairByComparing(pair<int,int> a, pair<int,int> b) {
   	//초기값으로 설정한 (0,0)이 있을때  (설정안하면 모든 노드 최솟값은 전부 0으로 됨) 
   	if (a ==zeroPair) {
   		if (b == zeroPair) {
   			return zeroPair;
   		}
   		else
   			return b;
   	}
   	else if(b==zeroPair) {
   		return a;
   	}
   
   	pair<int, int> retPair;
   	retPair.first = a.first > b.first ? b.first : a.first;
   	retPair.second = a.second > b.second ? a.second : b.second;
   	return retPair;
   }

5. 리프 노드들은 동일한 값을 최솟값, 최대값에 저장하는식으로
   구현하고,
   부모 노드들은 두 자식 리프노드들을 비교하는 식으로 구현하였다.

   for (int i = 0; i < N; i++) {
   	cin >> tmp1;
   	segTree[firstLeafNodeIdx + i]=make_pair(tmp1,tmp1);
   }
   for (int i = firstLeafNodeIdx - 1; i > 0; i--) {
   	segTree[i] = MakeNewPairByComparing(segTree[i * 2], segTree[i * 2 + 1]);
   }

6. 기본 구간합 문제이나 구간곱 문제 같은 문제는 재귀를 통해 곱이나 합을 하면 답이 나왔지만,
   이 문제는 해당 구간의 최솟값 최대값을 저장하는 노드를 반환해야하므로,
   두 노드를 비교해서 새로운 pair값에 갱신해서 return해줬다.

   //타겟 구간의 왼쪽값, 타겟구간의 오른쪽값, 노드인덱스, 현재 탐색하는 구간의 왼쪽값, 오른쪽값
   pair<int,int> FindMinAndMax(int targetL,int targetR,int nodeNum,int curL,int curR) {
   	//탐색하는 구간이 목표구간을 벗어난경우 0,0을 반환 
   	if (curR < targetL || targetR < curL) return zeroPair;
   	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
   
   	//평균값 mid
   	int mid = (curL + curR) / 2;
   	//curL값부터 mid값 까지의 최솟값과 최댓값 pair로 
   	pair<int, int> firstVal = FindMinAndMax(targetL, targetR, nodeNum * 2, curL, mid);
   	//mid+1값부터 curR값까지의 최소,최대값 pair로 저장
   	pair<int, int> secondVal = FindMinAndMax(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
   	return MakeNewPairByComparing(firstVal,secondVal);
   }
   

전체 코드

#include<iostream>
#include<vector>

using namespace std;

//각 노드는 최솟값, 최댓값을 가진 pair로 구성되고, 리프노드들은 최소 최대값을 같은 값을 가진다.
vector<pair<int, int>> segTree;

int N = 0, M = 0, firstLeafNodeIdx = 1;
pair<int, int> zeroPair = { 0,0 };

//두 pair 비교해서 새로운 pair 만들기
pair<int, int> MakeNewPairByComparing(pair<int,int> a, pair<int,int> b) {
	//초기값으로 설정한 (0,0)이 있을때  (설정안하면 모든 노드 최솟값은 전부 0으로 됨) 
	if (a ==zeroPair) {
		if (b == zeroPair) {
			return zeroPair;
		}
		else
			return b;
	}
	else if(b==zeroPair) {
		return a;
	}

	pair<int, int> retPair;
	retPair.first = a.first > b.first ? b.first : a.first;
	retPair.second = a.second > b.second ? a.second : b.second;
	return retPair;
}

//타겟 구간의 왼쪽값, 타겟구간의 오른쪽값, 노드인덱스, 현재 탐색하는 구간의 왼쪽값, 오른쪽값
pair<int,int> FindMinAndMax(int targetL,int targetR,int nodeNum,int curL,int curR) {
	//탐색하는 구간이 목표구간을 벗어난경우 0,0을 반환 
	if (curR < targetL || targetR < curL) return zeroPair;
	if (targetL <= curL && curR <= targetR) return segTree[nodeNum];

	//평균값 mid
	int mid = (curL + curR) / 2;
	//curL값부터 mid값 까지의 최솟값과 최댓값 pair로 
	pair<int, int> firstVal = FindMinAndMax(targetL, targetR, nodeNum * 2, curL, mid);
	//mid+1값부터 curR값까지의 최소,최대값 pair로 저장
	pair<int, int> secondVal = FindMinAndMax(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
	return MakeNewPairByComparing(firstVal,secondVal);
}

//a,b사이의 최솟값과 최댓값 pair로 저장해서 출력하는 함수
void query(int a, int b) {
	
	pair<int, int> Ans = FindMinAndMax(a-1, b-1,1,0,firstLeafNodeIdx-1);
	cout<<Ans.first<<" " << Ans.second<<'\n';
}

void Input() {
	int tmp1,tmp2;
	//세그먼트 트리를 0,0으로 초기화해줌 
    //2^17이 최초로 10만을 넘어가는 수이므로 트리의 최대 노드 갯수는 2^18을 넘지 않는다
	segTree.resize(262144,zeroPair);
	cin >> N>>M;
	//N개보다 큰 2의 배수될때까지 2곱해줌
	while (firstLeafNodeIdx<N) {
		firstLeafNodeIdx *= 2;
	}
	
	for (int i = 0; i < N; i++) {
		cin >> tmp1;
		segTree[firstLeafNodeIdx + i]=make_pair(tmp1,tmp1);
	}
	for (int i = firstLeafNodeIdx - 1; i > 0; i--) {
		segTree[i] = MakeNewPairByComparing(segTree[i * 2], segTree[i * 2 + 1]);
	}
	for (int i = 0; i < M; i++) {
		cin >> tmp1 >> tmp2;
		query(tmp1, tmp2);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

 }

문풀후생

노드를 비교해서 답노드를 return하는 식으로 구현해봤는데
재밌었다.
좀 아쉬웠던 부분은 query함수 부분에서 FindMinAndMax에서
curL, curR값을 초기값으로 리프노드의 모든 인덱스인
0부터 FirstLeafNodeIdx-1 값을 줘야하는 데,

처음 구현할땐 값을 가진 리프노드의 갯수인 0~ N-1값을 줘서
알아내는데 시간이 걸렸었다.

이 오류를 고치면서 세그먼트 트리의 구조에 대해 훨씬 이해하게 되서 좋았던 문제였다.