난이도: 골드 1
문제 링크:www.acmicpc.net/problem/2357
기말고사 전에 공부해서 풀었던 문제이지만...
블로그에 글로 정리하기에는 바빠서 지금에서야 정리해서 올립니다.
언뜻 보면 쉬워 보이는 최솟값, 최댓값 찾기 문제입니다.
처음엔 별 생각 없이 배열에 정렬해서 넣고 주어진 구간을 전부 탐색하여 최솟값, 최댓값을 찾아왔으나...
시간 초과가 걸렸습니다.
숫자의 크기가 크고, 갯수가 최대 10만 개가 되는 상황에서, 만약 10만개의 구간 a, b 쌍이 주어진다면?
10만 * 10만 = 약 100억 번, 그것도 최소 + 최대 두 번의 비교연산을 각각 해서 총 200억 번의 비교 연산을 해야 할 수 있습니다.
2초 안에 실행될 리가 없는 것이죠.
관련 알고리즘을 찾아보던 중, 백준 블로그에서 세그먼트 트리라는 알고리즘을 소개하고 있는 것을 보게 되었습니다.
설명은 위 블로그에 너무나도 잘 되어 있습니다.
이를 요약하자면, (사실 기말고사 기간 전에 봤던 내용이라 가물가물합니다. 저도 다시 봐야겠네요 ㅠ)
각 구간에 대한 정보를 저장하는 binary tree 형태의 자료구조입니다.
글에서는 특정 구간의 합을 예시로 들었지만, 저는 이를 약간 변경하여 특정 구간의 최소값과 최대값을 담도록 각 node를 구성했습니다.
'알고리즘, 문제해결 > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 1238번] 파티 (0) | 2021.02.11 |
---|---|
[백준 12865번] 평범한 배낭 (0) | 2021.02.06 |
[백준 1655번] 가운데를 말해요 (0) | 2020.12.23 |
[백준 1107번] 리모컨 (0) | 2020.11.28 |
[백준 1774번] 우주신과의 교감 (0) | 2020.11.27 |
댓글