누적합/구간합 알고리즘 (Prefix Sum)

`누적합/구간합 알고리즘` 이란

 

배열에서 특정 구간의 합을 한 번의 계산으로 처리할 수 있는 기법이다.

 

배열이 주어지고, n만큼 연속된 구간의 합을 m번 질문한다면,

일반적으론 for(0 ~ n) * m 의 방식을 활용하여 n * m 의 속도가 나오지만,

누적합을 활용하면 매 질문당 한 번의 연산으로 m의 속도만이 필요하다.

 

일반적인 일차원 배열에서의 활용법,

이차원 배열에까지 확장한 활용법과,

누적합 활용을 위한 배열 세팅 방법까지 알아보자.

 

 

---

 

 

원리

 

다음 도형에서 색칠된 칸의 개수는 몇 개인가?

 

V

V

V

V

 

 

손으로 세어서 4칸이다.

 

 

 

그런데 만약 이런 푯말이 있다고 가정하자.

 

			처음부터 여기까지 4칸				처음부터 여기까지 8칸
				V	V	V	V

 

 

이 상황에서도 손으로 세는 것이 효율적일까?

그냥 8 - 4 하면 4칸이 나온다.

 

 

이때 8 - 4 의 의미는 무엇일까?

 

실제로 나는 " 5 ~ 8 " 범위를 세어야 하지만,

" 1 ~ 8 " 범위를 세고(+), 세지 않아야 할 " 1 ~ 4 " 의 범위를 뺀 것(-)이다.

 

둘 모두 " 처음 시작 (1) " 에서 " 현재 위치 " 까지 몇 칸인지 정보를 미리 알고 있었다는 공통점이 있다.

 

 

 

누적합이란 말 그대로
처음부터 현재 위치까지 누적된 합을 저장하고 활용하여
어떤 범위 내의 합을 물어봐도 한 번의 연산으로 답을 도출하는 방법이다.

 

 

 

 

 

이제 값이 들어 있는 배열로 이 개념을 확장해보자.

 

index	0	1	2	3	4
value	0	10	20	30	40

 

" index 2 ~ 4 까지의 합? " 은 어떻게 구할까?

 

일반적으로 20 + 30 + 40 = 90으로 일일이 계산할 수도 있다.

 

 

 

하지만 우린 지성인.

앞선 누적합 개념을 적용하여 계산해보자.

 

누적합은 처음부터 현재 위치까지 누적된 합을 활용한다고 했다.

적용을 위해 배열을 미리 세팅한다.

 

index	0	1	2	3	4
value	0	10	20	30	40
prefix sum	0	10	30	60	100

 

이제 " index 2 ~ 4 까지의 합? " 은 어떻게 구할까?

 

" index 4 " 의 누적합 100 , " index 1 (2의 한 칸 앞) " 의 누적합 10 을 이용하면

100 - 10 = 90 으로 더욱 간편하게 계산할 수 있어졌다.

 

 

 

따라서 누적합을 이용하기 위해선 두 가지 순서가 필요함을 알 수 있다.

1. 처음부터 매 index 까지의 누적합 정보를 담은 세팅
2. 구하려는 범위의 " 시작 한 칸 앞 정보 " 와 " 끝 정보 "

 

 

 

 

 

이차원 배열에선 어떨까?

다음과 같이 5x5 배열을 만들어보자.

우리가 알고 싶은 부분을 보라색 부분이라 가정한다.

 

 

우리가 보라색 부분의 합을 알기 위해선 어떤 방법이 있을까?

앞서 설명했듯, 직관적으로 단순히 보라색 부분의 원소들을 순회하며 일일이 세는 방법이 있을 것이다.

이는 단순하고 간단히 구현 가능하지만, 구해야 할 구간이 많아질 경우 비효율적인 계산 속도를 낳게 된다.

 

 

이번엔 우리가 배열 전체의 합을 알고 있다고 가정하고, 보라색 부분의 합을 도출하는 방법에 대해 살펴보자.

파랗게 칠해진 부분이 우리가 이미 알고 있는 부분이라 가정한다. (U)

 

U

 

 

 

(0, 0) 에서 시작한 최대한 큰 뭉텅이 (직사각형) 로 보라색 부분만 남기려면 어떻게 날리는 것이 좋을까?

먼저 윗 부분 (UP) 을 최대한 크게 날려보자.

 

U - UP

 

 

 

이번엔 왼쪽 (LEFT) 을 날려야한다.

이때 (0, 0) 에서 시작한 큰 뭉텅이이므로 6칸 (11, 12, 16, 17, 21, 22) 만을 날릴 수는 없다.

그렇다면 어쩔 수 없이 첫 번째 날린 부분과 겹치도록 날려야 할 것이다.

 

U - UP - LEFT

 

 

 

이렇게 되면 빨간색 부분은 두 번을 날린 것으로, 올바른 값이 아니다.

따라서 겹치는 빨간색 부분 (UNION) 만을 더해주어야 하는데,

마침 빨간색 부분은 (0, 0) 에서 시작하는 뭉텅이다.

 

U - UP - LEFT + UNION

 

이렇게 되면 파란색만의 합을 구할 수 있다.

이런 방식은 벤다이어그램 등의 연산에서 자주 보던 방식으로,

전체에서 두 그룹을 빼고 겹치는 부분만을 다시 더해주는 익숙한 연산법이다.

 

 

---

 

 

적용

 

똑같이 5x5 배열을 만들고, 각 땅의 값은 모두 1이라 가정한다.

 

 

전체의 합이나, 날리는 부분이나, 겹치는 부분이나 모두 (0, 0) 에서 시작하므로,

미리 배열을 순회하여 [ (0, 0) ~ (자기 자신의 위치) ] 까지의 총 합을 미리 세팅한다.

 

예시의 경우에는 모든 땅이 1의 값을 가지므로

[ 현재 위치까지 몇 개의 1이 있는가 ( = 몇 칸인가 ) ] 를 세팅하면 되겠다.

 

 

예시의 경우 초록색 직사각형에서 오른쪽 아래 끝 8의 경우,

(0, 0) 부터 8칸을 소유하므로 8칸의 모든 값 (1) 의 합으로 8이 됨을 알 수 있다.

 

 

이렇게 값을 세팅한 후 위의 예시를 그대로 적용해보자.

먼저 전체 합은 가장 우측 하단의 값인 25가 된다.

 

25

 

 

 

이제 위쪽 뭉텅이를 날려보자.

위쪽 뭉텅이의 합은 뭉텅이의 최우측 하단인 10이 된다.

 

25 - 10

 

 

 

이제 왼쪽 뭉텅이도 날려보자.

왼쪽 뭉텅의 합 역시 가장 우측 하단인 10이 된다.

 

25 - 10 - 10

 

 

 

이제 두 번 빼졌던 빨간색 부분의 값을 더해주어야 한다.

두 번 날렸던 부분의 합은 최우측 하단인 4가 된다.

 

25 - 10 - 10 + 4

 

 

그럼 결국 파란색 땅의 합 (9칸) 는 25 - 10 - 10 + 4 = 9 로 도출 가능하며,

단순 4칸에 접근하는 것으로 올바른 범위의 합을 구할 수 있게 됐다.

 

 

---

 

 

알고리즘

 

이제 직접 코드를 작성할 때의 유의점을 살펴보자.

 

일차원 배열의 경우 0 ~ i 까지의 누적합을 for 문을 통해 저장하면 되기에 간단하다.

이차원 배열의 경우를 살펴보자.

 

 

 

먼저 각 칸의 누적합을 구해야 한다.

이는 전체 원소 순회를 2번 하여 그림과 같이 세팅할 수 있으며,

어느 방향을 먼저하든 같은 결과가 나온다.

 

 

 

 

이제 계산을 위해 필요한 index를 알아보자.

윗 예시에서 필요한 index는 다음과 같은 4칸이었다.

 

 

 

 

이 4칸을 시작점, 끝점 index을 기준하여 표현하면 다음과 같다.

 

 

 

즉, 우리에게 시작점과 끝점의 좌표가 주어진다면 다음과 같은 연산으로 필요한 4칸의 index를 구할 수 있다.

 

 

 

따라서, (start_i, start_j) 부터 (end_i, end_j) 까지의 범위를 구하는 방법은

 

앞선 누적합 세팅을 완료한 배열을 sum[][] 에 저장 후

sum[end_i][end_j] - sum[start_i - 1][end_j] - sum[end_i][start_j -1] + sum[start_i - 1][start_j - 1] 의 값이 된다.