백준 2357 최솟값과 최댓값
-
[JAVA] 백준 2357 최솟값과 최댓값알고리즘 공부/문제 풀이 2021. 9. 29. 15:05
https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 분석 N개의 정수 범위에서 a ~ b까지의 최댓값과 최솟값을 구해라. a, b쌍이 최대 10만 개 주어질 수 있음! => 각 a, b의 쌍에 대해 최솟값과 최댓값을 구하면 시간초과 발생 해결 전략 구간 합을 로그의 시간복잡도롤 구할 수 있는 세그먼트 트리 (이진 트리의 형태로 왼쪽, 오른쪽 자식을 재귀적으로 탐색) 최댓값과 최솟값을 구하기 위한 세그먼트 ..