[알고리즘] 누적 합, 구간 합 - 백준 단계별로 풀어보기 시리즈

들어가며

이번 포스팅에서 다룰 알고리즘은 누적 합 입니다. 누적 합 배열을 이용해 구간 합을 구하는 알고리즘입니다.

개인적으로는 구간 합이라고 불리는 것이 더 적절하다고 생각합니다. 아이디어 자체는 간단하지만 한번씩 예상치 못한 곳에서 사용되는 것 같습니다.

---

구간 합

누적 합 배열을 이용하여 상수 시간만에 구간의 합을 구하는 알고리즘입니다.

 

구간 합을 구하는 과정은 일반적으로 다음과 같습니다.

1. 누적 합 배열을 만든다. 

2. 두 지점의 차를 통해 구간 합을 구한다.

 

1차원 구간 합

$ y $를 누적합 배열, $ x $를 원소라고 하자.

 

누적 합 배열을 만드는 방법

$ y[i] = y[i-1] + x[i] $

 

구간 합을 구하는 방법

$ [a, b] $ 구간에 대해서, $ y[b] - y[a-1] $

 

2차원 구간 합 

1차원 누적 합이 나타내는 것이 선이였다면, 2차원 누적 합이 나타내는 것은 면적입니다.

 

누적 합 배열을 만드는 방법

$ y[i][j] = y[i-1][j] + y[i][j-1] - y[i-1][j-1] + x[i][j] $

 

구간 합을 구하는 방법

$ [ (a_1, b_1), (a_2, b_2) ] $ 구간에 대해서, $ y[a_2][b_2] - y[a_2][b_1-1] - y[a_1-1][b_2] + y[a_1-1][b_1-1] $

 

다차원 누적 합

위 점화식을 확장하여 다차원 배열의 누적 합 또한 구할 수 있습니다.

---

구현

구간 합을 구할 때 따로 예외 처리가 필요하지 않도록 누적 합 배열의 인덱스는 1부터 시작하는 것을 추천드립니다.

 

1차원 구간 합

arr = [1 for _ in range(10)] 
sumArr = [0 for _ in range(len(arr)+1)] # 선의 길이

for i in range(1, len(sumArr)):
    sumArr[i] += sumArr[i-1] + arr[i-1]

print(sumArr[10] - sumArr[0])

10

 

2차원 구간 합

arr = [[1 for _ in range(10)] for _ in range(10)]
sumArr = [[0 for _ in range(len(arr)+1)] for _ in range(len(arr)+1)] # 면적의 넓이

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

print(sumArr[10][10] - sumArr[0][0])

100