[Algorithm] IMOS 기법: 누적합과 차분 배열로 빠른 구간 업데이트 with Java

IMOS 기법

 

들어가며

누적합(Prefix Sum) 알고리즘에서 더 나아가 구간을 빠르게 업데이트하는 IMOS 기법에 대해 설명하는 글입니다. 누적합 알고리즘에 대해 모르는 경우 아래의 글을 먼저 읽고 오시길 바랍니다.

[Algorithm] 누적합(Prefix Sum) 알고리즘 with Java

이번 글에선 차분 배열 자료구조와 누적합 알고리즘을 합친 imos 방법에 대해 설명하겠습니다.

 

 

---

 

 

차분 배열(Difference Array)

1. 의미

차분 배열이란 배열의 특정 구간에 값을 더하거나 뺄 때, 전체를 일일이 갱신하지 않고, 값이 변하는 지점에서 변화량(Difference)만 기록하는 자료구조입니다.

 

2. 필요성

의미만 봤을 땐 차분 배열이 왜 필요한 지 감이 오지 않을테니 왜 필요한 지를 살펴보겠습니다.

길이가 10인 정수형 배열이 있다고 하겠습니다. (10번 인덱스는 무시해도 됩니다 - 아래에서 설명 예정)

길이가 10인 정수형 배열 선언

 

이제 이 배열에 연속된 특정 구간의 값들을 계속해서 변경해보겠습니다.

Query 1) 4~9에 +2

4번부터 9번 인덱스까지 2를 더한 결과

 

Query 2) 0~5에 -1

0번부터 5번 인덱스까지 1을 뺀 결과

 

Query 3) 3~6에 -2

3번부터 6번까지 2를 뺀 결과

 

위처럼 일반적으로 구간을 업데이트하는 방법은 구간에 대해 전부 연산을 적용하는 것입니다. 이때의 문제점은 업데이트의 시간복잡도가 최악의 경우 $O(n^2)$이므로 배열의 길이가 길어질수록, 쿼리의 개수가 많아질수록 급격히 성능이 떨어진다는 것입니다.

위의 예시에선 길이가 10에 쿼리가 3개 밖에 없었기 때문에 상관없지만 배열의 길이가 10만이고, 쿼리가 10만개라면 100억 번의 연산이 필요합니다.

 

따라서 구간을 여러번 업데이트할 때 더 효율적인 방법이 필요했고, 누적합 알고리즘 원리에서 역으로 고안된 차분 배열이 등장하게 되었습니다.

 

3. 차분 배열 표현법(1차원)

차분 배열의 핵심은 값이 변하는 지점에 해당 값만큼 표시만 해준다는 것입니다. 갱신할 값이 양수인지 음수인지와 관계없이 시작 인덱스에서 값을 더해주고, 종료 인덱스의 다음 지점에서 값을 빼주면 됩니다.

그럼 위에 나왔던 3개의 쿼리대로 차분 배열 자료구조에 적용해보겠습니다.

Query 1) 4~9에 +2

4번, 10번 인덱스에 표시

4번 인덱스에 +2를 하고, 마지막 인덱스의 다음 인덱스인 10번 인덱스에 -2를 합니다.

 

Query 2) 0~5에 -1

0번, 6번 인덱스에 표시

0번 인덱스에 -1를 하고, 마지막 인덱스의 다음 인덱스인 6번 인덱스에 +1을 합니다.

 

Query 3) 3~6에 -2

3번, 7번 인덱스에 표시

3번 인덱스에 -2를 하고, 마지막 인덱스의 다음 인덱스인 7번 인덱스에 +2를 합니다.

 

지금은 표현법만 다루고 이 차분 배열 자료구조를 어떻게 활용할 수 있는 지는 아래의 IMOS 방법 설명에 같이 서술하겠습니다.

10번 인덱스는 왜 필요할까?
위에서 보다시피 길이는 0부터 9까지 10인 구간에서 10 인덱스를 추가해두었습니다. 그런데 차분 배열 표현법에 의하면 원래 배열의 마지막 인덱스인 9까지 값을 업데이트 하는 경우 다음 인덱스에 마이너스 연산이 필요하므로 추가적인 길이를 확보한 것입니다.

 

4. 시간복잡도

배열의 길이가 $N$, 쿼리가 $Q$라고 할 때 기존의 시간복잡도는 $O(N^2)$이었습니다.

하지만 차분 배열을 사용하면 양 끝점만 고려하므로, 시간복잡도는 $O(N+Q)$입니다.

 

 

IMOS Method

IMOS(いもす法). 흔히 이모스라고 불리는 IMOS Method는 일본 알고리즘 커뮤니티에서 주로 사용되는 표현입니다. 특정 컴퓨터 과학자가 고안해낸 것이 아니라 누적합 알고리즘에서 자연스럽게 나타난 구간 업데이트 기법에 가깝습니다.

차분 배열은 단순히 값의 변화량을 기록하는 표현 방법(=자료구조)인데, 이 차분 배열에 누적합 알고리즘을 적용해 실제 값을 복원하는 과정을 통틀어서 이모스 방법이라고 부릅니다.

 

 

1차원 배열에서 IMOS Method 사용

구간 업데이트가 모두 끝난 후의 결과와 차분 배열의 누적합 배열을 구한 것의 결과는 동일합니다. 고차원에서 적용 가능하지만 일반적인 PS에선 1~2차원을 다루기 때문에 이번 글에서는 2차원까지만 설명하겠습니다. 2차원 차분 배열은 글의 가장 하단에 있습니다.

 

1차원 배열은 앞선 예제를 다시 가져와서 확인해보겠습니다.

 

우선 구간 업데이트를 했을 때의 결과는 아래와 같았습니다.

구간 업데이트를 했을 때의 결과

 

그리고 차분 배열의 결과를 다시 가져와서 누적합을 구해보겠습니다. 누적합을 구하는 원리는 같기 때문에 계산 과정 생략하고 결과만 가져왔습니다.

차분 배열을 누적합한 결과

 

두 표를 비교해보면 결과가 같은 것을 알 수 있습니다.

배열의 값이 0일 때만 가능할까?
그렇지 않습니다. 차분 배열을 누적합한 결과에 배열의 초기값들을 전부 더하면 됩니다.

 

 

IMOS 알고리즘 자바 구현 코드

1. 차분 배열 만들기

int[] dif = new int[n+1];

StringTokenizer st;
for(int i = 0; i < q; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    int s = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    dif[s] += k;
    dif[e+1] -= k;
}

• 반복문 내의 q는 구간을 업데이트하는 쿼리의 개수입니다.
• s는 시작점, e는 끝점이고, k는 업데이트할 값입니다.
• dif[s] += k에 의해 시작점에 +k를 표시
• dif[e+1] -= k;에 의해 끝점에 -k를 표시

 

2. 누적합 적용

for(int i = 1; i <= n; i++) {
    dif[i] += dif[i-1];
}

• dif의 길이가 $n+1$이므로 1부터 n까지 누적합 계산

 

3. 전체 코드

배열의 크기와 구간을 업데이트하는 쿼리의 개수를 입력 받아 차분 배열을 만들고, 누적합을 구해서 기존의 배열 값과 더하는 코드입니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        int[] matrix = new int[n];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++) {
            matrix[i] = Integer.parseInt(st.nextToken());
        }

        int[] dif = new int[n+1];

        for(int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            dif[s] += k;
            dif[e+1] -= k;
        }

        for(int i = 1; i <= n; i++) {
            dif[i] += dif[i-1];
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(dif[i]+matrix[i]).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}

• n: 정방행렬의 크기를 의미
• q: 쿼리의 개수
• matrix: 기존의 배열 값
• dif: 차분 배열

 

2차원 차분 배열 만들기

2차원의 경우도 원리만 이해하면 단순합니다. 차분 배열을 구한 뒤에 누적합을 구하고, 기존 배열의 원소가 존재한다면 각각 원소에 더해주면 됩니다.

게시글 최상단의 링크에 2차원 배열의 누적합을 구하는 방법을 자세히 적어두었습니다. 따라서 여기선 2차원 차분 배열을 구하는 방법만 설명하겠습니다.

 

(x1, y1)에서 (x2, y2) 범위에 있는 직사각형 영역에 값을 k만큼 업데이트하는 경우 딱 4군데의 점만 변경하면 됩니다.

1. $dif[x1][y1] \to +k$
2. $dif[x2+1][y1] \to -k$
3. $dif[x1][y2+1] \to -k$
4. $dif[x2+1][y2+1] \to +k$

그림을 통한 예시로 확인하겠습니다.

크기가 5*5인 배열에서 (1, 2) ~ (4, 3) 범위에 있는 직사각형 영역에 값을 k만큼 업데이트 한다면 아래와 같습니다.

2차원 차분 배열 예시

이렇게 모든 쿼리에 대해 적용한 뒤 2차원 누적합을 계산한 것이 바로 구간 업데이트를 모두 적용한 결과입니다.

 

 

.

.

.

 

 

마치며

백준에서 IMOS를 연습하기 좋은 문제를 몇개 가져왔습니다.

• 19951번 태상이의 훈련소 생활: https://www.acmicpc.net/problem/19951
• 28018번 시간이 겹칠까?: https://www.acmicpc.net/problem/28018
• 25826번 2차원 배열 $\cdots$ 단일 합: https://www.acmicpc.net/problem/19951

 

궁금한 점이나 피드백은 댓글로 부탁드립니다.

긴 글 읽어주셔서 감사합니다. 😊