[백준 2357번] 최솟값과 최댓값

난이도: 골드 1

2357번: 최솟값과 최댓값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100

www.acmicpc.net

기말고사 전에 공부해서 풀었던 문제이지만...

블로그에 글로 정리하기에는 바빠서 지금에서야 정리해서 올립니다.

언뜻 보면 쉬워 보이는 최솟값, 최댓값 찾기 문제입니다.

처음엔 별 생각 없이 배열에 정렬해서 넣고 주어진 구간을 전부 탐색하여 최솟값, 최댓값을 찾아왔으나...

시간 초과가 걸렸습니다.

숫자의 크기가 크고, 갯수가 최대 10만 개가 되는 상황에서, 만약 10만개의 구간 a, b 쌍이 주어진다면?

10만 * 10만 = 약 100억 번, 그것도 최소 + 최대 두 번의 비교연산을 각각 해서 총 200억 번의 비교 연산을 해야 할 수 있습니다.

2초 안에 실행될 리가 없는 것이죠.

관련 알고리즘을 찾아보던 중, 백준 블로그에서 세그먼트 트리라는 알고리즘을 소개하고 있는 것을 보게 되었습니다.

세그먼트 트리 (Segment Tree)

문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i

www.acmicpc.net

설명은 위 블로그에 너무나도 잘 되어 있습니다.

이를 요약하자면, (사실 기말고사 기간 전에 봤던 내용이라 가물가물합니다. 저도 다시 봐야겠네요 ㅠ)

각 구간에 대한 정보를 저장하는 binary tree 형태의 자료구조입니다.

글에서는 특정 구간의 합을 예시로 들었지만, 저는 이를 약간 변경하여 특정 구간의 최소값과 최대값을 담도록 각 node를 구성했습니다.

하고 싶은 것을 즐겁게