반응형
SMALL
2357번 최솟값과 최댓값
-
백준 2357번 최솟값과 최댓값 (Python)알고리즘 2023. 9. 6. 11:11
N개의 정수가 주어질 때, 구간 a~b 사이에 최소, 최대값을 찾는 문제입니다. 아이디어 1. 세그먼트 트리 주어진 숫자 개수 N과 구간 쌍 M개의 범위가 (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)이므로 모두 탐색하면서 찾는다면 시간 초과가 발생할 것으로 예측됐습니다. 그래서 세그먼트 트리를 활용하게 됐습니다. 세그먼트 트리는 데이터가 연속적으로 존재할 때 특정 범위의 데이터의 합을 구하는 방법입니다. 세그먼트 트리 5 3 8 11 2 9 4 14 8 6 의 연속된 데이터가 있다고 가정해보도록 하겠습니다. 이 숫자들 중 여러 개의 특정 구간의 숫자 합을 구할 때, 계속해서 반복을 통해 구하게 된다면 O(N) 시간이 걸리게 되므로, 데이터의 개수가 많아진다면 시간 초과가 발생해 불가능하..