2D 누적 합(Prefix Sum) 기법

 

이런게 있더라고요.

 

2D 누적 합은 이차원 배열(행렬)에서 특정 부분 영역의 합을 빠르게 계산해야 할 때 주로 사용됩니다.

 

언제 사용 할까요?

1. 특정 부분 영역의 합을 자주 계산할 때 (O(1)로 최적화)

 

기본적으로 특정 부분의 합을 구하려면 O(N*M)이 걸리지만, 누적 합 배열을 미리 만들어두면 O(1)로 구할 수 있음.

ex) 2D 배열에서 (r1, c1)부터 (r2, c2)까지의 합을 여러 번 구해야 하는 경우

 

부분 합 = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

 

2. 다차원 배열에서 특정 범위를 여러 번 업데이트해야 할 때 (차이 배열과 함께 사용)

 

특정 영역을 업데이트하는 연산이 많을 때, 차이 배열(Difference Array)과 결합하면 성능을 크게 향상시킬 수 있음.

ex) 특정 부분(r1, c1) ~ (r2, c2)에 +k 또는 -k를 여러 번 적용해야 할 때

# 시작점에 +k, 우측 끝과 하단 끝에 -k, 대각선 끝에 +k 적용
effect[r1][c1] += k
effect[r1][c2 + 1] -= k
effect[r2 + 1][c1] -= k
effect[r2 + 1][c2 + 1] += k

 

3. 이미지/그리드에서 누적된 영향을 빠르게 계산해야 할 때

 

누적 영향 분석이 필요한 경우에도 활용됨.

ex) 이미지 프로세싱, 히트맵 데이터 분석

- 어떤 좌표 (x, y)까지의 누적 밝기(명도)를 빠르게 계산할 때

- 히트맵 데이터에서 특정 영역이 얼마나 영향을 받았는지 계산

 

---

예제 문제: N×M 크기의 배열에서 여러 개의 쿼리(부분 합 계산)가 주어질 때, 빠르게 답을 구하기

def prefix_sum_2d(matrix):
    N, M = len(matrix), len(matrix[0])
    prefix = [[0] * (M + 1) for _ in range(N + 1)]

    # 누적 합 배열 만들기
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            prefix[i][j] = (matrix[i-1][j-1] +
                            prefix[i-1][j] + prefix[i][j-1] -
                            prefix[i-1][j-1])

    return prefix

def query(prefix, r1, c1, r2, c2):
    return (prefix[r2][c2] - prefix[r1-1][c2] - 
            prefix[r2][c1-1] + prefix[r1-1][c1-1])

# 테스트
matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]

prefix = prefix_sum_2d(matrix)
print(query(prefix, 1, 1, 2, 2))  # 12 (1+2+4+5)
print(query(prefix, 2, 2, 3, 3))  # 28 (5+6+8+9)

 

1. 누적합을 기록할 [N + 1][M + 1] 사이즈 배열을 만들기

2. 누적합 배열 완성하기

3. 원하는 영역에서의 누적합을 구하기 

= 부분 합 = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]

 

왜 이런 식이 되는냐

 

prefix[r2][c2]는 (0, 0)부터, (r2, c2)까지의 누적합입니다.

 

 

주어진 matrix 가 위와 같다고 했을 때

 

prefix의 결과는 위와 같습니다.

 

(r2, c2)가 (3, 3)일 경우 prefix[3][3] = 45 입니다.

이는, matrix의 (0, 0)부터 (2, 2)까지의 모든 값을 합한 값과 같습니다.

 

그런데 (1, 1)부터 (3, 3)까지의 누적합을 구하고 싶다할 때,

(3, 3)은 (0, 0)부터 시작한 누접합이기 때문에,

불필요한 부분을 제거해주어야 합니다.

 

따라서, (0, 1)부터 (0, 3)까지, (1, 0)부터 (3, 0)까지의 누적합은 제거해 주어야합니다.

이를 위해서 (0, 0)부터 (0,3)까지의 합인 (0, 3), (1, 0)부타 (3,0)까지의 합인 (1, 0)인 값을 빼주고

중복으로 제거된 (0, 0)값을 한 번 더해주는 것입니다.

 

다음에 또 봐요