[알고리즘 개념] 누적합과 구간합

누적합과 구간합

누적합(Cumulative Sum)은 배열 또는 리스트의 각 원소까지의 누적된 합을 구하는 기법이고 구간합(Range Sum) 은 배열 또는 리스트에서 특정 구간에 속하는 원소들의 합을 구하는 기법으로 이 두 기법은 주로 배열이나 리스트의 부분합을 효율적으로 계산하는 데 사용된다. 누적합과 구간합은  다음과 같은 알고리즘 문제시 사용할 수 있다.

 

1. 배열 또는 리스트에서 연속된 구간의 합을 구해야 할 때

예를 들어, 가장 큰 연속 부분 배열의 합을 구하는 문제나, 특정 조건을 만족하는 최소/최대 구간의 합을 구하는 문제 등에 사용한다.

 

2. 여러 번 반복되는 구간의 합을 구해야 할 때

예를 들어, 배열이 주어지고 배열의 일부 구간이 반복되는 경우, 각 구간의 합을 구해야 할 때 누적합과 구간합을 사용하면계산을 피하고 효율적으로 구간합을 계산할 수 있다.

 

3. 부분집합의 합을 구해야 할 때

주어진 배열에서 합이 특정 값이 되는 부분집합의 개수를 구하거나, 부분집합의 합이 주어진 값과 같은 경우를 찾아야 할 때 누적합과 구간합을 사용할 수 있다.

 

 

문제 접근방식

- 1차원 배열과 2차원 배열의 누적합과 구간합을 구하는 방식이 다른데 보통 누적합과 구간합 문제가 나오면 누적합으로 이루어진 배열이 필요하기에 문제에서 입력받은 값이 n이라면 n+1 크기의 배열(sums)을 생성한다.

 

1차원 배열의 누적합과 구간합

누적합 계산 점화식: sums[i] = sums[i-1] + arr[i] (0 ≤ i < n)
sum[i]은 배열 arr의 인덱스 0부터 i까지의 합을 나타내는 누적합이다.

 

예시) 배열 arr의 누적합을 계산하여 반환하는 함수로 각 인덱스 i에 대해 prefix_sum[i]는 배열 arr의 인덱스 0부터 i까지의 합을 나타낸다.

def calculate_prefix_sum(arr):
    n = len(arr)
    prefix_sum = [0] * n
    prefix_sum[0] = arr[0]

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

    return prefix_sum

 

2차원 배열의 누적합과 구간합

- 누적합 계산 점화식 : sums[i][j] = graph[i-1][j-1] + sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1]

sums[i][j]은 sums[i][j-1](이전 열의 누적합), sums[i-1][j] (이전 행의 누적합) 현재 열의 graph[i-1][j-1]값을 더하고 중복되는 좌표의 누적합 값 sums[i-1][j-1]을 빼는것과 같다.

 

- 구간합 계산 점화식 : total = sums[x2][y2] - (sums[x1-1][y2] + sums[x2][y1-1]) + sums[x1-1][y1-1]

total은 sums[x2][y2](0,0부터 x2,y2 좌표까지의 누적합)에서 (sums[x1-1][y2] + sums[x2][y1-1]) 시작좌표 전 행과 열까지의 누적합을 빼고 중복되어 감소된 sums[x1-1][y1-1]을 더한값과 같다.

 

예시) n,m 크기의 좌표를 입력받아 0,0 부터 n,m까지의 누적합을 sums에 입력하고 입력값 x1,y1 부터, x2,y2까지의 구간합을 구한다.

import sys

area = [list(map(int,input().split())) for _ in range(n)]
sums = [[0] * (m+1) for _ in range(n+1)]

for i in range(1,n+1):
  for j in range(1,m+1):
    sums[i][j] = area[i-1][j-1] + sums[i][j-1] + sums[i-1][j] - sums[i-1][j-1]
    
result = 0
x1,y1,x2,y2 = map(int,input().split())
result = sums[x2][y2] - (sums[x1-1][y2] + sums[x2][y1-1]) + sums[x1-1][y1-1]
print(result)