[자료구조 및 알고리즘] 누적합

누적합

---

누적합은 리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구해 구간의 합을 구하는 방법이다. 이를테면 매출을 매일 기록해둔 카페 주인이 주말 매출과 주중 매출을 알고 싶어한다. 월요일을 일주일의 시작이라고 가정하고 예시를 살펴보자.

 

카페 수익

월	화	수	목	금	토	일
1	2	3	4	5	6	7

 

화요일부터 금요일까지의 수익은 2,3,4,5의 합인 14이다. 또 수요일부터 일요일까지의 매출의 합은 3,4,5,6,7의 합인 25가 된다. 데이터가 적으면 빠르게 구할 수 있지만, 데이터가 많아질수록 합을 구하는 시간이 오래 걸린다. 이때 누적합을 이용하면 빠르게 구할 수 있다.

 

화요일부터 금요일까지의 매출은 2,3,4,5를 다 더해주는 것이 아니라, 금요일까지의 누적합에서 월요일까지의 누적합을 빼주면 구할 수 있다. 같은 방법으로 수요일부터 일요일까지의 매출은 일요일까지의 누적합에서 화요일까지의 누적합을 빼주면 구할 수 있다.

 

누적합 만들기

arr = [1,2,3,4,5,6,7]
sum_arr = [0]*(len(arr)+1) # 인덱스 숫자 맞춰주기

for i in range(1, len(arr)+1):
  sum_arr[i] = sum_arr[i-1] + arr[i-1]
 
print(sum_arr) # [0,1,3,6,10,15,21,28]

원소들을 하나씩 더해주면서 누적합을 만들어주면 된다.

 

누적합 구하기

def getsum(i,j):
  return sum_arr[j] - sum_arr[i-1]

누적합을 구해둔 리스트를 1부터 저장한 이유가 여기서 나온다. 0부터 시작하면 sum_arr[-1]을 따로 신경써줘야하기 때문이다. 파이썬에서 list[-1]은 가장 뒤에 있는 원소를 불러오므로 잘못된 값을 구할 여지가 있다. 따라서 1부터 누적합을 저장해 따로 구분해줄 필요없이 편리하게 구하는 방법이 이전부터 선호되었다고 한다.

 

sum[i-1]인 이유는, 그 전날까지의 합을 빼주어야 구하고자 하는 날이 포함되기 때문이다.

 

2차원 배열에서의 누적합

 

2차원 배열에서의 누적합 또한 복잡하지만 만들 수 있다.

1	2	3	4	5
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5
1	2	3	4	5

위와 같은 2차원 배열에서 누적합을 구하는 과정을 살펴보자.

 

1

3

6

10

15

첫 번째 줄은 1차원 리스트의 누적합과 같은 방식으로 쉽게 구할 수 있다. 두 번째 줄부터 조금 복잡할 수 있다. 사실, 처음에는 2행 1열에 15+1이 들어간다고 생각했는데 그게 아니었다.

 

1	3	6	10	15
1+1 = 2	2+3-1+2 = 6

 두 번째 열 첫 번째 숫자 1은 첫 번째 열의 숫자 1에 그냥 더해주면 된다. 2행 2열의 경우는 1+2+2+1을 구하는 곳이다. 직접 다 더해도 되지만 데이터가 커질수록 구하는 시간이 길어질 것이다. 이때, 2차원 배열에서도 누적합을 이용하면 합을 구할 수 있다. 2행 2열의 경우는 (2행 1열까지의 합 + 1행 2열까지의 합 - 중복되는 부분 + 원래 있던 원소의 값)을 해주면 누적합을 구할 수 있다. 이를 일반화하면 아래와 같이 나타낼 수 있다.

for i in range(1, n+1):
  for j in range(1,n+1):
    sum_arr[i][j] += arr[i][j]
    sum_arr += sum_arr[i-1][j]
    sum_arr += sum_arr[i][j-1]
    sum_arr -= sum_arr[i-1][j-1]

 

2차원 배열에서의 구간 합 알고리즘

 

누적합을 이용해 구간합을 구하는 방법은 아래와 같다. 네모 박스 친 곳의 구간 합을 누적합을 이용해 구하는 과정이다.

https://wikidocs.net/206305

이 배열에서의 누적합은 아래와 같다.

https://wikidocs.net/206305

(4,3)의 42는 (1,1)부터 (4,3)까지의 누적합이므로, 위에 박스에서의 구간합을 구하려면 따로 작업을 해주어야 한다.

https://wikidocs.net/206305

(4,3)의 값인 42에서 (4,1)에 위치한 10, (2,3)에 위치한 15를 빼주고 중복해서 빠진 (2,1)의 값인 3을 더해주면 된다. 이를 일반화하면, (x1,y1)에서 (x2,y2)까지의 누적합을 구하는 식은 다음과 같다.

sum_arr[x2][y2] - sum_arr[x1-1][y2] - sum_arr[x2][y1-1] + sum_arr[x1-1][y1-1]

 

(1,1)부터 (x,y)까지 누적합을 시간 내에 구할 수 있으면 구간 합은 O(1)로 처리할 수 있다.

 

위 그림으로 이해하기 어려우면 아래 그림이 도움이 될 수 있을 거 같다.

https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java

 

참고자료

https://wikidocs.net/206305

 

https://nahwasa.com/entry/%EB%88%84%EC%A0%81-%ED%95%A9prefix-sum-2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9prefix-sum-of-matrix-with-java