[알고리즘] 누적 합

💡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을 추가해준다.

---

1. X2, Y2의 누적합을 구하고자 한다. 위치는 다음과 같다.
   

---

2. 여기에서 이미 계산이 끝난 X1, Y1-1을 먼저 더한다.
   

---

3. 그 다음 이미 계산이 끝난 X1-1, Y1도 더한다.
   

---

4. 이렇게 계산을 하게 된다면 X1-1, Y1-1의 값이 두 번 더해지게 되므로 해당값을 한 번 빼줘야 한다.
   

---

5. 구하고자 하는 값이 X2, Y2의 누적합이다. 따라서 좌표 X2, Y2의 값을 마지막으로 가져오면 해당 좌표까지의 누적합이 나오게 된다.