알고리즘
-
알고리즘: RMQ알고리즘 2024. 3. 25. 21:03
RMQ(Range Minimum Query): (query란 단어의 뜻은 문의하다, 질문하다) 참고자료 숫자가 n개 있는 배열이 하나 있고, 해결해야 하는 (l,r)의 쿼리가 q개 들어오는 상황 기준 1. Brute Force q(l,r)일 때 l부터 r까지 전부 훑어서 RMQ를 찾음. 전처리: x 시간 복잡도: O(n) 업데이트: O(n) 직관적이고 쉬움, 배열의 값을 업데이트하는 것이 자유로움. 2. 미리 전부 전처리 전처리로 테이블을 미리 만들어 놓고 테이블에서 가져옴 전처리: O(n^2) 시간복잡도: O(1) 업데이트: O(n^2) 시간복잡도가 낮으나 전처리가 길고, 배열의 값을 하나만 바꿔도 테이블을 O(n^2)을 들여 만들어야 함 3. Sqrt Decomposition root(n)개로 n을 ..