누적합은 구간의 합을 빠르게 구하는 방법입니다.
1차원 배열에서의 누적합
아래와 같은 1차원 배열이 있습니다.
A = [4, -2, 1, 5, -3]
위의 배열에서 인덱스 1번부터 3번까지의 합을 구하고자 합니다.
그럼 -2 + 1 + 5 = 4를 계산해야하니 시간복잡도는 O(N)입니다.
그런데 배열이 크고, 구간합을 자주 계산하게 된다면 시간이 오래 걸리기 때문에,
이럴 때 사용하는 것이 누적합니다.
누적합은 말그대로 누적해서 더하는 것입니다. 아래처럼요.
S[n+1] = sum(0, n) 인덱스 0번부터 n번의 합 ( 계산의 편의를 위해 s[0]번은 비워둠 )
S = [0, 4, 2, 3, 8, 5]
일단 누적합을 계산해두고나면, 구간합을 아주 빠르게 구할 수 있습니다.
위의 예시처럼 인덱스 1번부터 3번까지의 합을 구한다면,
S[4] - S[2 - 1] = 8 - 4 = 4
위처럼 한번의 뺼셈으로 어떤 구간합이든 계산할 수 있습니다. 따라서 시간복잡도는 O(1)입니다.
2차원 배열에서의 누적합
이런 방식은 2차원 배열에도 적용할 수 있습니다.
아래와 같은 2차원 배열이 있습니다.
A =
[1, 5, 3]
[2, 0, 9]
[1, 8, 6]
마찬가지로 누적합을 구해줍니다.
S[i + 1, j + 1] = A[0,0]부터 A[i, j]까지의 합 (편의상 첫줄은 비워둠)
아래와 같은 방법으로 빠르게 구간합을 구할 수 있습니다.
S[i + 1, j + 1] = A[i + j] + S[i, j + 1] + S[i + 1, j] - S[i, j]
S =
[0, 0, 0, 0]
[0, 1, 6, 9]
[0, 3, 8, 20]
[0, 4, 17, 35]
(1, 1)부터 (2, 2)까지의 구간합을 구한다면, 아래와 같이 계산하면 됩니다.
[0, 0, 0, 0]
[0, (+1), 6, (-9)]
[0, 3, 8, 20]
[0, (-4), 17, (+35)]
구간합 = S[2 + 1, 2 + 1] - S[1, 2 + 1] - S[2 + 1, 1] + S[1, 1]
일반화하면
Sum(y1, x1, y2, x2) = S[y2 + 1, x2 + 1] - S[y1, x2 + 1] - S[y2 + 1, x1] + S[y1, x1]
(단, y1 < y2 , x1 < x2)
마찬가지로 누적합 배열을 만드는데에 O(N * M)이 소요되고, 구간합을 구하는데 O(1)이 소요됩니다.
다른 적용 방법 (구간 증가 / 감소)
누적합은 구간의 증가나 감소에도 적용될 수 있습니다. 예들 들어 아래와 같은 배열이 있습니다.
A = [4, -2, 1, 5, -3]
S[1]~S[3]에 5씩 더 한다고 했을 때, 일일히 더하면 O(N)이 소요되지만,
아래와 같이 표현할 수도 있습니다.
temp[0, 5, 0, 0, -5, 0] (계산의 편의를 위해 마지막에 0을 추가했습니다.)
이를 누적합하면,
temp[0, 5, 5, 5, 0, 0]
가 되고, A배열에 더 하면 됩니다. 마찬가지로 구간 증가/감소 표시에 O(1)이 소요되고,
마지막 구간합시 O(N)이 소요됩니다.
구간 증가/감소가 잦을 때 사용하면 되겠습니다.
같은 방법으로 2차원 배열에 적용할 수 있습니다.
참조
'Computer Science > Algorithm' 카테고리의 다른 글
| [알고리즘] Kruskal 알고리즘 (feat. Union-Find) (0) | 2023.01.16 |
|---|---|
| [알고리즘] 위상 정렬 (0) | 2023.01.15 |
| [알고리즘] 벨만 포드 알고리즘 (Bellman-Ford) (0) | 2023.01.13 |
| [알고리즘] BFS와 다익스트라 알고리즘 (0) | 2023.01.13 |
| [알고리즘] 행렬의 제곱 (백준 2099, The game of death)(feat. 인접행렬, 인접리스트) (0) | 2022.12.20 |