Square Root Decomposition (2) 썸네일형 리스트형 170. Mo's Algorithm 이번에는 제곱근 분할법을 수열에 적용하는 방법을 알아보자. 모스 알고리즘(Mo's Algorithm)은 제곱근 분할법을 이용하여 세그먼트 트리 등의 자료 구조로 처리하기 어려운 쿼리를 처리하는 방법이다. 제곱근 분할법을 수 자체에 적용할 때는 제곱근 이하와 이상, 두 부분을 따로 다루었는데 제곱근 분할법을 길이가 $n$인 수열에 적용하면 $\sqrt{n}$ 정도의 길이를 갖는 $\sqrt{n}$개의 구간을 기준으로 접근하게 된다는 차이점이 있다는 것은 제곱근 분할법을 수에 적용하는 방법을 소개할 때도 언급했다. 그러면 모스 알고리즘의 작동 방법을 알아보자. 여기서 $\sqrt{n}$은 전부 근삿값이며 적당히 가까운 정수를 사용하면 된다. 또한 처리하는 쿼리들은 구간 $[l, r]$로 나타낼 수 있으며 한.. 169. Square Root Decomposition 적당한 분할을 통해서 시간복잡도를 최적화하는 또 다른 방법을 알아본다. 제곱근 분할법(평방 분할, Square Root Decomposition)은 큰 구간을 구간 크기의 제곱근을 기준으로 분할한 다음 연산을 빠르게 처리하는 방법이다. 여기서 큰 구간은 크게 두 가지 형태로 나타나는데, 한 가지는 수열이고 다른 한 가지는 수 자체이다. 구간의 형태에 따라 제곱근 분할법을 적용하는 방식도 다르게 나타난다. 길이가 $n$인 수열에 제곱근 분할법을 적용할 때는 보통 이것을 $\sqrt{n}$ 정도의 길이를 갖는 구간 $\sqrt{n}$개로 분할한 다음 원하는 연산을 처리하는 방식이 주로 사용되지만, 수 자체에 제곱근 분할법을 적용할 때는 수를 $\sqrt{n}$ 이하와 $\sqrt{n}$ 이상의 두 그룹으로 .. 이전 1 다음
