2차원 배열의 부분합

Number of Submatrices That Sum to Target

• 해당글은 discussion에 있는 설명 글을 번역했음을 알립니다.

    row = len(matrix[0])
        columns = len(matrix)

        for r in matrix:
            for x in range(row - 1):
                r[x+1] += r[x] #각 row에 대한 누적합

        res = 0

        for start in range(row):
            for end in range(start,row):

                count = collections.defaultdict(int)
                current = 0
                count[0] = 1
                for column in range(columns):
                    current += matrix[column][end] - (matrix[column][start - 1] if start > 0 else 0)
                    res += count[current - target]
                    count[current] += 1

다음 코드를 보고 한 번에 이해를 안되는 사람들을 위해 설명을 하려한다.

1. 각 행를 먼저 더한다.

        for r in matrix:
            for x in range(row - 1):
                r[x+1] += r[x] #각 row에 대한 구간합

이중반복문으로 나중에 쓸 각 행의 구간합을 미리 구해놓는다.

2. 두 열 사이의 모든 가능한 범위에 대해 모든 행에 대해 이 두 열 사이의 값의 합을 더하여 이 두 열 사이에 형성 될 수있는 부분 행렬의 구간합의 합계를 누적한다.

for start in range(row):
            for end in range(start,row):

                count = collections.defaultdict(int)
                current = 0
                count[0] = 1
                for column in range(columns):
                    current += matrix[column][end] - (matrix[column][start - 1] if start > 0 else 0)
                    res += count[current - target]
                    count[current] += 1

이 삼중 반복문에서 무슨일이 일어 나는지 알아보기 위해 i=1,j=3이라고 가정해보자.
그리고 크게 두가지 부분으로 나누어서 볼 것이다.

count = collections.defaultdict(int)
                count[0] = 1

• 이 딕셔너리의 key는 우리가 볼 수 있는 유니크한 값이 된다.
• 이 딕셔너리의 value는 우리가 보았던 유니크한 값의 등장 횟수다.
• 비어있는 submatrix는 자동적으로 합이 0이된다.

for column in range(columns):
                    current += matrix[column][end] - (matrix[column][start - 1] if start > 0 else 0)
                    res += count[current - target]
                    count[current] += 1

다음으로 우리가 실제로 첫 번째 행부터 matrix[0][1...3], matrix[1][1...3] ... matrix[m-1][1...3] 로우별로 각 구간합을 더한다. res에 값을 구하는 방법은 구간합을 이용한 Subarray Sum Equals K 이 문제와 똑같다. 여기서 따로 설명하진 않겠다.