파이썬 1, 2 차원 누적합과 부분합

●  배열의 일부 구간의 합을 빠르게 구하는 알고리즘

●  미리 구해놓은 누적합 공식을 통해 배열의 특정 구간의 부분합을 빠르게 구할 수 있다.

 

arr[인덱스번호] : 3[1]    1[2]   4[3]    1[4]    5[5]    9[6]   2[7]
-------------------------------------------------
prefixSum : 0[0]   3[1]   4[2]   8[3]   9[4]  14[5]  23[6]  25[7]

-------------------------------------------------
내가 만약에 배열의 3[i]번부터 6[j]번까지 알고싶다
arr 의 [3] ~ [6] : 4 + 1 + 5 + 9 = 19(우리가 원하는값) - 일일이 다 더하면 시간복잡도가 증가

누적합을 이용 부분합 구하기
prefixSum[j] = 23
prefixSum[i−1] = 4
partSum=prefixSum[j]−prefixSum[i−1] == 19

1차원 누적합

 

# 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
import sys

# 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다.
n, m = map(int, sys.stdin.readline().split())
# 둘째 줄에는 N개의 수가 주어진다.
arr = list(map(int, sys.stdin.readline().split()))
# 누적 합 배열 생성 (1-based index)4
prefixSum = [0] * (n+1)

# 누적합 구하기
for i in range(1, n+1):
    prefixSum[i] = prefixSum[i-1] + arr[i-1]

# 결과값 넣을 리스트
answer = []

# 부분합 구하는 공식
for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    result = prefixSum[j] - prefixSum[i - 1]
    answer.append(str(result))

sys.stdout.write('\n'.join(answer) + '\n') 

 

2차원 누적합

출처 https://code-angie.tistory.com/22

 

●  초록색 부분(3번)과 노란색 부분(4번), 그리고 겹치치 않은 갈색부분(5번) 을 더해주고 그리고 파란색부분(2번)은 중첩이 됬으니 한번 빼준다

 

.

출처 https://code-angie.tistory.com/22

# 누적합
n,m = map(int, input().split()) # 행 열 길이
# 배열
arr = [list(map(int, input().split())) for _ in range(n)]
# 누적합 배열 한번 초기화
prefixSum = [[0]*(m+1) for _ in range(n+1)]

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

 

●   (i,j) 에서 (x,y)까지의 부분합

출처 https://code-angie.tistory.com/22

●   빨간색(1번) 에서 초록색(3번), 노란색(4번)을 빼주고 중첩된 파란색(2번)을 더함

●   partSum = prefixSum[x][y] - prefixSum[i-1][y] - prefixSum[x][j-1] + prefixSum[i-1][j-1]

 

i,j,x,y = map(int,input().split())

# (i,j)칸에서 (x,y)칸까지 포함한 부분합
partSum = prefixSum[x][y] - prefixSum[i-1][y] - prefixSum[x][j-1] + prefixSum[i-1][j-1]
print(partSum)