#34 누적 합(Prefix Sum) - 2차원

 누적 합은 2차원 배열에서도 1차원에서와 거의 동일하게 활용 가능하다.  이번에는 2차원 배열에서의

누적 합의 성질과 이를 활용하여 풀 수 있는 문제들을 알아본다.

 

1. 2차원 배열의 누적합 구하기

 1차원 배열에서는 단순히 이전 인덱스의 값을 더해주면 끝이었지만 2차원 배열에서 누적합을 구하려면 각 행의

누적 합과 각 열의 누적 합을 구하는 두 단계를 거쳐야한다.  예시로 2차원 배열 하나의 누적 합을 구해보자.

 

① 먼저 각 행의 누적합을 구한다.

 

② 다음으로 각 열에 대한 누적 합을 구한다.

 

③ 2차원 행렬에서의 누적합 배열이 완성된다.  ①과 ②의 순선느 서로 뒤바뀌더라도 문제가 없다.

 

 

2. 2차원 누적 합의 성질

 2차원 배열에서의 부분 합을 구하거나 여러 구간에 대한 증감 적용을 한꺼번에 처리하는 데

활용할 수 있는 성질들을 가지고있다. 

 

누적합 S(r, c)는 2차원 배열 A에 대해 다음과 같은 성질을 가진다.

① S(r, c) = sum([A[i][j] for i in range(r) for j in range(c)]) 

② S(0, 0) = A[0][0]

③ S(r, c) = S(r-1, c) + A[r][c]

④ sum([A[i][j] for i in range(r1, r2+1) for j in range(c1, c2+1)]) = S(r2, c2) + S(r1-1, c1-1) - S(r1, c2-1) - S(c1-1, r2)

② 번 성질이 성립하는 이유

1차원 배열에서의 누적 합과 조금 다르지만 거의 유사한 성질을 가진 것을 알 수 있다.

 

 

3. 2차원 배열의 합

N*M 크기의 2차원 배열이 주어졌을때 K 개의 특정 구간에 대한 부분 합을 구하는 문제.  단순히 매번 반복문을 돌려 합을 구할 경우 O(NMK)의 시간복잡도를 보인다.  하지만 누적합의 4번 성질을 이용하면 O(NM+K)만에 해결할 수 있다.

문제를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol2167():
    # 행렬의 크기 n, m
    n, m = map(int, input().split())
    
    # 주어진 행렬 seq
    # 누적 합의 성질 4번을 사용할 때, 0번 인덱스의 이전 인덱스를 참조할 경우를 대비해 
    # 행/열의 끝에 0을 추가
    seq = [[*map(int, input().split()), 0] for _ in range(n)]
    seq.append([0] * m)
    seq.append([0] * m)
    
    # 2차원 배열의 누적합 배열을 구한다
    for i in range(n):
        for j in range(m):
            # 현재 위치의 누적합을 구하기 전에 같은 열의 다음 행의 값에 
            # 현재위치의 값을 더해주는 것으로 열에 대한 누적합을 동시에 계산해나갈 수 있다.
            seq[i + 1][j] += seq[i][j]
            seq[i][j] += seq[i][j - 1]

	# 정답 리스트
    answer = []
    
    # 누적 합의 성질 4번을 사용하여 부분 합을 구하고 정답 리스트에 저장
    for _ in range(int(input())):
        i, j, x, y = map(int, input().split())
        answer.append(seq[x-1][y-1] + seq[i - 2][j - 2] - seq[x-1][j - 2] - seq[i - 2][y-1])

    # 출력 형식에 맞춰 정답 리스트 반환
    return '\n'.join(map(str, answer))

 

 

4.