목록2023/04/12 (1)

HJW's IT Blog

Algorithm: RMQ(Range Minimum Query)

RMQ란 배열에서 일부 구간을 선택하여 그 구간에서의 최소값을 찾는 알고리즘이다. RMQ를 해결함에 있어서 여러 방법이 존제하는데 살펴보자. Brute-force Method 이 방법은 가장 단순한 방법으로 해당 구간 내에 모든 원소를 비교하는 방법이다. 각 쿼리가 주어질때마다 해당 구간에서 최소값을 찾기 위해 O(n) 시간이 소요된다 이 방법은 구현이 간단하고 쿼리가 적은 경우에는 유용할 수 있지만 보통은 그렇지 않다 전처리: O(n^2), 질의: O(1) 가능한 a, b 모두에 대해 미리 답을 다른 배열 B[a][b]에 미리 답을 저장해 두는 방법이다. 값이 변하지만 않는다면 유용하지만 그렇지 못할경우 비효율적 전처리: O(n), 질의 O(sqrt(n)) 이 방법은 square root decompo..
알고리즘 2023. 4. 12. 16:40
이전 Prev 1 Next 다음