티스토리 뷰

Algorithm/etc.

Sqrt Decomposition

kesakiyo 2016. 11. 20. 03:53

원소들을 효율적으로 관리해야할 일이 있을때 우리는 어떤 전략을 선택해야할까? 원소들을 효율적으로 관리하는 방법은 여러가지가 있다. 이번에는 그 중 하나인 Sqrt Decomposition에 대해 알아보도록 하자. Sqrt Decomposition에서 Sqrt는 Square root의 약자다. 이를 우리나라 말로 번역하자면 평방분할이라고 한다. 하지만 의미적으로 별로 와닿지 않는다고 생각하기 때문에 Sqrt Decomposition이라고 하겠다. 



연속적인 원소들을 하나의 묶음으로



Sqrt Decomposition의 기본 아이디어는 정말 간단하다. 연속적인 원소들을 하나의 묶음으로 생각하자는 것이다. 이 때 한 묶음의 크기는 보통 \(\sqrt N\)으로 잡는다.(그래서 Square root라는 이름이 붙은것 같다.)



위 그림은 원소가 9개일 때 연속한 3개씩 끊어 한 묶음으로 취급하는 예를 보여준다. 그렇다면 일차원 배열에서만 사용할 수 있는것일까? 아래 그림은 이차원 배열에서 Sqrt Decomposition를 적용한 결과를 보여준다.



또한 일차원, 이차원 배열 외에도 \(Tree\)에도 적용할 수 있는 등 그 활용범위가 상당히 다양하다.



구간의 합 구하기



Sqrt Decomposition의 이론은 위에서 설명한 것이 전부이다. 너무 간단해 어떻게 사용하는지 감이 잘 안올것이다. 그래서 구간의 합을 구하는 문제를 Sqrt Decomposition를 이용해 푸는 과정을 보여주려 한다. 구간의 합을 찾는 문제는 다음과 같다.


\(A_1,\ A_2,\ A_3,\ ...\ ,\ A_{N-1},\ A_{N}\)인 시퀀스가 있을 때 두 가지 쿼리를 처리해야 한다.

1. \(x,\ y\ (1 \le x \le y \le N)\)가 주어졌을 때 \([A_x,\ A_y]\)의 합을 구한다.

2. \(x\ (1 \le x \le N)\)와 \(val\)이 주어졌을 때 \(A_x\)의 값을 \(val\)로 갱신한다.


이 때 이 쿼리들을 완전탐색으로 해결할수도 있다. 하지만 \(N\)이 크고 쿼리의 수가 많다면 빠른시간내에 답을 낼 수 없다. 우리는 각각의 쿼리에 대해서 \(O(\sqrt N)\)에 푸는것을 목표로 하자.


이 문제는 https://www.acmicpc.net/problem/2042에서 풀어볼 수 있다.



전처리



Sqrt Decomposition는 쿼리를 수행하기 전에 전처리가 필요하다. 우선 원소들을 연속한 \(\sqrt N\)개만큼 묶은 다음 이 묶음들의 합을 미리 계산해 놓는다. 이렇게 계산된 합들은 각각의 쿼리를 \(O(\sqrt N)\)에 처리하는데 큰 도움을 준다. 전 처리는 \(O(N)\)에 할 수 있다. 

// initialize function
// sz = sqrt(n)
void init() {
  sz = sqrt(n)
  for (int i = 0 ; i < n ; ++i) {
    bucket[i / sz] += A[i];
  }
}


구간의 합을 구하는 쿼리



전처리를 했으면 이제 두 가지 쿼리를 처리해야 한다. 그 중 첫 번째 쿼리인 구간의 합을 구하는 쿼리를 처리해 보자. 합을 구하고자 하는 구간이 주어졌을 때 구간 내에 포함된 묶음들은 크게 두 가지 종류로 분류할 수 있다.


1. 구간에 완전히 포함된 묶음

2. 구간에 애매하게 걸쳐있는 묶음


1번 경우는 전처리한 묶음의 합들을 사용해 쉽게 계산이 가능하다. 하지만 2번 경우에는 전처리한 합을 이용해 계산하는것이 불가능하다. 그래서 구간에 애매하게 걸쳐있는 묶음은 구간 내 포함된 원소들을 찾아 직접 더해줘야 한다.



과연 이렇게 구하는 방법이 완전탐색으로 구하는 것보다 더 빠른 시간을 보장할 수 있을까? 1번에 포함된 묶음은 최대 몇개가 있을지 생각해보자. 우리는 한 묶음을 \(\sqrt N\)개의 연속된 원소들로 정의를 했다. 그렇기 때문에 묶음의 개수는 \(\sqrt N\)개를 넘을 수 없다. 따라서 구간에 완전히 포함된 묶음은 최대 \(\sqrt N\)개가 될 것이다. 2번의 경우는 확인해야 하는 원소들의 개수가 한 묶음 전체가 될 수도 있다. 그래서 2번의 경우에 해당하는 묶음의 수가 중요하다. 하지만 잘 생각해 보면 구간에 애매하게 걸쳐있는 묶음이 발생하는 곳은 구간의 양 끝에서만 존재한다는 것을 알 수 있다. 결국 2번의 경우에 해당하는 묶음은 최대 2개까지 존재할 수 있다.


따라서 구간의 합을 \(O(\sqrt N)\)의 시간에 구할 수 있다.

// query function
long long query(int lo, int hi) {
  long long ret = 0;
  
  // 2번 경우를 처리해 주는 부분
  // 구간의 왼쪽에 애매하게 걸쳐있는 묶음의 원소들을 모두 더해준다
  while (lo % sz != 0 && lo <= hi) {
    ret += A[lo++];
  }
  
  // 구간의 오른쪽에 애매하게 걸쳐있는 묶음의 원소들을 모두 더해준다
  while ((hi + 1) % sz != 0 && lo <= hi) {
    ret += A[hi--];
  }
  
  // 1번 경우를 처리해 주는 부분
  // 구간 내 완벽하게 포함된 묶음들의 합을 더해준다
  while (lo <= hi) {
    ret += bucket[lo / sz];
    lo += sz;
  }
  
  return ret;
}


특정 원소의 값을 갱신



이제 남은 쿼리는 특정 원소의 값을 갱신하는 쿼리다. 구간의 합을 구하는 쿼리보다 특정 원소를 갱신하는 쿼리는 비교적 많이 쉽다. 해당 원소가 속해있는 묶음의 합에 바뀐 값의 차이만큼 더해주고 실제 원소의 값을 변경시켜주면 끝난다. 이 작업은 모두 상수시간에 가능하며 시간복잡도는 \(O(1)\)이다.

// update function
void update(int pos, long long val) {
  // 원래 원소의 값과 갱신해야 하는 값의 차이를 계산
  long long diff = val - A[pos];
  
  // 기존 원소를 새로운 값으로 대체
  A[pos] = val;
  
  // 기존 원소가 속해있는 묶음에 갱신으로 인해 생기는 차이만큼의 값을 더해준다
  bucket[pos / sz] += diff;
}


결론



자, 이제 우리가 원하는 모든 작업을 어떻게 구현해야 하는지 알아봤다. Sqrt Decomposition을 이용해 구간의 합을 구하는 문제를 풀기 위해서 다음과 같은 세 가지 작업을 필요로 했다.


1. 전처리 : \(O(N)\)

2. 구간의 합을 구하는 쿼리 : \(O(\sqrt N)\)

3. 특정 값을 갱신 : \(O(1)\)


만약 쿼리의 수가 \(Q\)개라면 우리는 \(O(N+Q\sqrt N)\)의 시간에 문제를 해결할 수 있을 것이다. 물론 세그먼트 트리를 사용하면 \(O(N+QlogN)\)이라는 훌륭한 시간에 문제를 해결할 수 있다. 하지만 우리는 Sqrt Decomposition의 사용방법을 배웠기 때문에 Sqrt Decomposition으로 문제를 한번 풀어보도록 하자. Sqrt Decomposition로 풀 수 있는 문제는 대부분 세그먼트 트리로도 해결이 가능하지만 간혹 Sqrt Decomposition로 푸는것이 훨씬 간단하고 쉬울때가 있다. 이는 나중에 다뤄보도록 하자.



전체 코드





'Algorithm > etc.' 카테고리의 다른 글

MO's algorithm  (4) 2016.11.21
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함