728x90 Segment Tree2 BOJ - 10868번, 최솟값 문제 Segment Tree를 이용한 풀이 이번 문제는 주어진 N개의 정수들에 대해 M번의 구간 최솟값을 묻는 질의에 올바른 답을 반환하는 알고리즘을 구현하는 것이 목표입니다. 물론, 구간의 최솟값을 확인하기 위해 linear한 탐색 방식을 취할 수 있겠지만, 이렇게 하는 경우 - worst case 100,000(N의 최댓값) x 100,000(M의 최댓값) = 10^12번의 연산 위와 같이 연산의 횟수가 너무 커서 시간 초과를 결과로 받게 될 것입니다. 따라서 지난번에 정리한 세그먼트 트리의 개념을 구간 합을 구하는 대신 최솟값을 구할 수 있도록 변형해서 이번 문제를 풀이하는 방식을 채택해 봤습니다. https://kkkdh.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%E.. 2023. 1. 18. 세그먼트 트리 (Segment Tree) 개념 정리 지난번에 문제풀이를 하면서, 세그먼트 트리를 활용할 일이 있어 오랜만에 개념을 공부했는데 기억이 잘 나지 않아서 한 번 정리해보려 합니다. 세그먼트 트리 (Segment Tree)의 정의! 우선 위키백과에서는 세그먼트 트리를 다음과 같이 정의하고 있습니다. In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. A segment tree for a set I of .. 2022. 11. 16. 이전 1 다음 728x90
