💡1차원 배열의 누적 합
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
prefix_sum = []
sum = 0
for i in arr:
sum += i
prefix_sum.append(sum)
print(prefix_sum)
- 위 1차원 배열의 누적 합 결과는 [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]가 된다.
여기서 예를 들어 3번째 항부터 5번째 항까지의 누적 합은 3 + 4 + 5 = 12가 된다. 누적 합 리스트에서 결과를 가져온다면 prefix_sum[5] - prefix_sum[2]가 된다.
💡2차원 배열의 누적 합
arr = [[1, 2, 3, 4],
[2, 3, 4, 5],
[3, 4, 5, 6],
[4, 5, 6, 7]]
sum_arr = [[0, 0, 0, 0, 0],
[0, 1, 3, 6, 10],
[0, 3, 8, 15, 24],
[0, 6, 15, 27, 42],
[0, 10, 24, 42, 64]]
- 위 2차원 배열의 누적 합 결과는 다른 분의 velog 게시글에 있는 그림을 참조했다.
2차원 배열의 누적 합을 구하는 과정을 그림을 통해서 이해하면 다음과 같다.
- 2차원 배열 누적 합을 구할 때 주의사항 : 2차원 배열의 누적합 배열을 만들 때에는 위쪽과 왼쪽 테두리에 0을 추가해준다.
- X2, Y2의 누적합을 구하고자 한다. 위치는 다음과 같다.
- 여기에서 이미 계산이 끝난 X1, Y1-1을 먼저 더한다.
- 그 다음 이미 계산이 끝난 X1-1, Y1도 더한다.
- 이렇게 계산을 하게 된다면 X1-1, Y1-1의 값이 두 번 더해지게 되므로 해당값을 한 번 빼줘야 한다.
- 구하고자 하는 값이 X2, Y2의 누적합이다. 따라서 좌표 X2, Y2의 값을 마지막으로 가져오면 해당 좌표까지의 누적합이 나오게 된다.
