Post

차분 배열 & 이모스법

이 글은 제 개인적인 공부를 위해 작성한 글입니다. 틀린 내용이 있을 수 있고, 피드백은 환영합니다.

Posted
By JJM
views 5 min read
차분 배열 & 이모스법

차분 배열(Difference Array)

크기가 N인 배열 A가 있을 때 A의 구간 [l, r]에 x를 더하는 연산을 M번 수행해야 할 때, 반복문으로 매번 구간에 x를 더하는 것은 O(NM)의 시간 복잡도를 가진다.

이를 더 효율적으로 하기 위해서 구간의 시작과 끝만 표시하여 갱신을 하고, 이를 누적합하여 최종 배열을 구하는 방법이 차분 배열이다.

  1. 차분 배열 A의 L번째에 x를 더한다. (A[L] += x)
  2. 차분 배열 A의 R+1번째에 x를 뺀다. (A[R+1] -= x)
  3. 차분 배열 A의 누적합을 구한다.


N = 7인 배열의 구간 [1, 4]에 3을 더하는 연산을 해보자.

  1. [0, 0, 0, 0, 0, 0, 0] : 초기 배열
  2. [0, 3, 0, 0, 0, -3, 0] : 구간의 시작 L에 3을 더하고, 구간의 끝 R+1에 3을 뺀다.
  3. [0, 3, 3, 3, 3, 0, 0] : 이를 오른쪽으로 누적합하여 최종 배열을 구한다.


이모스법(Imos Method)

이모스법은 차분 배열의 개념을 다차원으로 확장한 방법이다. 우리는 2차원 배열에서 알아보자.

마찬가지로 크기가 N x M인 2차원 배열 A가 있을 때 A의 구간 [x1, y1]에서 [x2, y2]까지에 x를 더하는 연산을 K번 수행해야 할 때, 반복문으로 매번 구간에 x를 더하는 것은 O(NMK)의 시간 복잡도를 가진다.

이모스법은 아래와 같이 4개의 점에만 x를 더하거나 빼는 연산을 수행한다.

  1. A[x1][y1] += x
  2. A[x1][y2 + 1] -= x
  3. A[x2 + 1][y1] -= x
  4. A[x2 + 1][y2 + 1] += x

이렇게 4개의 점에만 연산을 수행한 후 배열을 가로 방향으로 한 번, 세로 방향으로 한 번 총 두 번의 누적합을 하면 최종 배열을 구할 수 있다.


예시로 N = 4, M = 5인 2차원 배열에 아래 연산 4개를 한다고 해보자.

  1. (0, 0) ~ (3, 4) 구간에 4를 빼기
  2. (2, 0) ~ (2, 3) 구간에 2를 빼기
  3. (1, 0) ~ (3, 1) 구간에 2를 더하기
  4. (0, 1) ~ (3, 3) 구간에 1을 빼기

(0, 0) ~ (3, 4) -= 4 연산을 수행하면 아래 A[4][5]처럼 배열의 인덱스를 벗어나는데 이걸 표현하기 위해 2차우너 배열 길이를 하나 늘려서 살펴보자!

  1. A[0][0] -= 4
  2. A[0][5] += 4
  3. A[4][0] += 4
  4. A[4][5] -= 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 초기 배열 : N = 4, M = 5 (인데 길이를 하나 늘림)
index 0  1  2  3  4  5
   0 -4 -1  0  0  1  4
   1  2  0 -2  0  0  0
   2 -2  0  0  0  2  0
   3  2  0  0  0 -2  0
   4  2  1  2  0 -1 -4
   
// 가로 방향 누적합 수행
index 0  1  2  3  4  5
   0 -4 -5 -5 -5 -4  0
   1  2  2  0  0  0  0
   2 -2 -2 -2 -2  0  0
   3  2  2  2  2  0  0
   4  2  3  5  5  4  0
   
// 세로 방향 누적합 수행
index 0  1  2  3  4  5
   0 -4 -5 -5 -5 -4  0
   1 -2 -3 -5 -5 -4  0
   2 -4 -5 -7 -7 -4  0
   3 -2 -3 -5 -5 -4  0
   4  0  0  0  0  0  0

누적합을 두 번 모두 진행하면 추가된 행과 열은 모두 0이 되고 최종 배열을 구할 수 있다.

연산 당 시간 복잡도는 구간에 x를 더하거나 빼는 연산이 O(1)이고, 누적합을 구하는 연산 O(NM)을 두 번 하므로 전체 시간 복잡도는 O(NM)이다.


참고

Computer Science, Algorithm
Algorithm
This post is licensed under CC BY 4.0 by the author.