Square Root Decomposition (1) 썸네일형 리스트형 169. Square Root Decomposition 적당한 분할을 통해서 시간복잡도를 최적화하는 또 다른 방법을 알아본다. 제곱근 분할법(평방 분할, Square Root Decomposition)은 큰 구간을 구간 크기의 제곱근을 기준으로 분할한 다음 연산을 빠르게 처리하는 방법이다. 여기서 큰 구간은 크게 두 가지 형태로 나타나는데, 한 가지는 수열이고 다른 한 가지는 수 자체이다. 구간의 형태에 따라 제곱근 분할법을 적용하는 방식도 다르게 나타난다. 길이가 $n$인 수열에 제곱근 분할법을 적용할 때는 보통 이것을 $\sqrt{n}$ 정도의 길이를 갖는 구간 $\sqrt{n}$개로 분할한 다음 원하는 연산을 처리하는 방식이 주로 사용되지만, 수 자체에 제곱근 분할법을 적용할 때는 수를 $\sqrt{n}$ 이하와 $\sqrt{n}$ 이상의 두 그룹으로 .. 이전 1 다음
