누적합(부분합)을 응용해서 문제 해결하기 by Kotlin

사진: Unsplash의Antoine Dautry

 

 

우리가 알고리즘 문제를 해결하다가 보면 특정 구간에 대한 변화를 줘야할 때가 있습니다. 이번 게시글에서는 부분합에 개념에 대해 알아보고 누적합을 사용해서 특정 구간에 대한 변화를 주는 방법을 알아보도록 하겠습니다.

 

 

 

 

누적합

---

누적합의 개념은 사실 단순합니다. 배열의 처음부터 각각의 원소를 모두 더한 값을 새로운 배열에 넣으면 됩니다. 

 

[1, 2, 3, 4, 5] 의 배열이 있다면 이에 대한 누적합 배열은 [0, 1, 3, 6, 10 ,15] 입니다.

 

 

이러한 개념을 이용하면 특정 구간에 대한 합도 쉽게 구할 수 있습니다.

 

만약 3부터 5를 더한 값을 구하려고 한다고 생각해 보겠습니다. 그럼 이 값은 1부터 5까지의 값에 1부터 2까지 더한 값을 뺀 값이랑 동일할 것입니다. 이를 수식을 나타내면 아래와 같습니다.

 

[i, j]의 구간합 =  C[j] - [i - 1]

 

 

2차원 배열에서의 누적합

2차원 배열에서의 누적합을 구하는 방법도 크게 다르지 않습니다. 열로 누적합을 한번 구해주고, 행으로 누적합을 한번구해주면 2차원 배열 전체의 누적합을 구할 수 있습니다.

 

 

 

 

누적합의 응용

---

그럼 여기서 문제입니다. 2차원 배열에서 여러개의 특정 구간이 주어질 때 해당 구간에 +X를 하려고 한다면 누적합을 어떻게 응용할 수 있을까요??

 

하나의 1차원 배열의 특정 구간에 + X를 하는 방법은 사실 단순합니다.

 

예를 들어, [1, 2, 4, 8, 9] 의 배열이 있고, 0번째부터 3번째 원소까지 2만큼 빼야 하는 상황이라고 가정하겠습니다. 즉, 배열을 [-1, 0, 2, 6, 9]로 만들고 싶은 상황입니다.

 

단순하게는 아래와 같이 0번째부터 3번째 원소까지 반복문을 사용해 빼줄 수 있습니다.

fun pSum(arr: IntArray = intArrayOf(1, 2, 4, 8, 9)): IntArray {
    val startIndex = 0 // 구간 시작 인덱스
    val endIndex = 3   // 구간 끝 인덱스

    for (i in startIndex..endIndex) {
        arr[i] -= 2
    }

    return arr
}

다만 이러한 방식은 여러개의 특정 구간에 주어진다면 해당 구간에 대해 계속해서 계산을 해주어야 합니다.

 

 

 

그럼 특정 구간에 대한 + X의 값을 하나로 합친다면 해당 구간에 대해 계속해서 계산을 하지않아도 될 것 같다는 생각이 듭니다.

 

바로 여기서 누적합을 사용하면 이를 구현할 수 있습니다.

 

바로 누적합을 사용해 새로운 배열을 생성하고 기존의 배열과 새로운 배열을 더해주는 방법입니다.

 

예를 들어보겠습니다. [1, 2, 4, 8, 9]의 배열을 [-1, 0, 2, 6, 9]로 만들고 싶다면 [-2, -2, -2, -2, 0] 배열을 만들어서 2개의 배열을 더해주면 됩니다.

 

[1, 2, 4, 8, 9]  + [-2, -2, -2, -2, 0] =  [-1, 0, 2, 6, 9]

 

 

그럼 누적합은 언제 사용하냐구요??

 

바로 [-2, -2, -2, -2, 0] 배열을 만들 때 사용합니다. [-2, 0, 0, 0, 2] 배열을 누적합하게 되면 앞의 배열을 만들 수 있습니다.

 

이를 수식으로 나타내면 [n, 0, 0, 0, -n]이 됩니다. 

 

2차원 배열로 나타내면 

 

[n, 0, 0, 0, -n]

[0, 0, 0, 0, 0]

[0, 0, 0, 0, 0]

[-n, 0, 0, 0, n] 이 됩니다.

 

 

이해를 돕기 위해 예시로 추가 설명드리겠습니다.

1. (1,1)부터 (2,2)까지 -4만큼 변화를 줘야 합니다. (배열의 (1,1)과 (3,3)에 -4, 배열의 (1,3)과 (3,1)에 4만큼 변화를 줍니다.)

     0    0    0    0
     0   -4    0    4
     0    0    0    0
     0    4    0   -4

2. (0,0)부터 (1,1)까지 -2만큼 변화를 줘야 합니다. (배열의 (0,0)과 (2,2)에 -2, 배열의 (0,2)과 (2,0)에 2만큼 변화를 줍니다.)

    -2    0    2    0
     0   -4    0    4
     2    0   -2    0
     0    4    0   -4

3. (2,0)부터 (2,0)까지 +100의 변화를 줘야 합니다. (배열의 (2,0)과 (3,1)에 100, 배열의 (2,1)과 (3,0)에 -100만큼 변화를 줍니다.)

    -2    0    2    0
     0   -4    0    4
    102  -100 -2    0
   -100   104  0   -4

이 배열을 이제 위에서 아래로 누적합 해주겠습니다.

-2    0    2    0
-2   -4    2    4
100  -104  0    4
 0    0    0    0

그다음 왼쪽에서 오른쪽으로 누적합 해주겠습니다.

-2   -2    0    0
-2   -6   -4    0
100  -4   -4    0
 0    0    0    0

이 배열을 원래의 배열과와 합쳐 주겠습니다.

1 2 3         -2  -2   0        -1  0  3
4 5 6    +    -2  -6  -4    =    2 -1  2
7 8 9         100 -4  -4        107 4  5

마지막 결과 배열과 같은 배열이 나왔습니다. 이 배열에서 0보다 큰 정수의 개수를 구하면 됩니다.

 

 

 

 

Reference

2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설