SQRT Decomposition

알고리즘/자료구조 2015. 9. 5. 20:39 Posted by 아는 개발자

만약 알고리즘 문제에서 해당 배열의 특정 구간(L, R)에서 최소값을 구하라는 문제가 나왔다면 가장 일반적으로 생각 할 수 있는 방법은 L, R 구간을 모두 탐색해보는 방법일 것이다.


하지만 테스트 케이스의 개수가 많고 배열의 크기가 크다면 시간이 오래 걸릴 것이다. 여기서 사용 할 수 있는 방법이 sqrt decomposition이다.




크기 N인 배열을 sqrt(N)으로 쪼개서 최소값을 저장하는 배열(sqrt 배열)을 미리 만들어 둔 후


주어진 구간의 최소값 찾을 때는 구간 내에 포함된 sqrt배열에 해당하는 최소값과 그 이외의 부분들의 값을 비교해서 해결 할 수 있다


현재는 최소값을 구하는데 사용했는데 이것 말고도 다양한 정보를 저장하는데 사용 할 수 있을 것 같다

'알고리즘 > 자료구조' 카테고리의 다른 글

Count sort  (0) 2016.07.23
Segment Tree  (0) 2015.09.07
SQRT Decomposition  (0) 2015.09.05
LIS를 O(nlogn)시간 내에 해결하는 방법  (0) 2015.08.27
c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
인덱스 트리  (0) 2015.07.07