2차원 행렬이 하나 주어져 있다고 가정해 봅시다. 우리는 주어진 행렬과 크기가 같은 새로운 행렬 res를 만들어야 하며, 각 원소는 다음 조건을 만족해야 합니다.
res[i][j] = r ≤ i 이고 c ≤ j를 만족하는 모든 matrix[r][c]의 합
즉, 각 위치 (i, j)에는 해당 셀을 기준으로 왼쪽 위 영역에 속한 모든 원소들의 누적 합이 저장됩니다. 이러한 행렬을 흔히 2차원 누적 합(prefix sum) 행렬이라고 부르며, 이미지 처리나 구간 합 계산 등 다양한 분야에서 활용됩니다.
예시
입력 행렬이 다음과 같다면,
| 8 | 2 |
| 7 | 4 |
출력 결과는 다음과 같습니다.
| 8 | 10 |
| 15 | 21 |
결과를 자세히 살펴보면, res[0][0] = 8, res[0][1] = 8 + 2 = 10, res[1][0] = 8 + 7 = 15, res[1][1] = 8 + 2 + 7 + 4 = 21입니다. 각 셀에는 자기 자신을 포함하여 왼쪽 위 영역의 모든 원소가 더해진 값이 들어가는 것을 확인할 수 있습니다.
풀이 접근 방법
이 문제는 두 단계의 누적 합 계산만으로 효율적으로 해결할 수 있습니다.
행렬이 비어 있다면 그대로 반환합니다.
R := 행렬의 행 개수, C := 행렬의 열 개수로 설정합니다.
1단계 - 세로 방향 누적: r을 1부터 R-1까지, c를 0부터 C-1까지 순회하면서 matrix[r][c]에 바로 윗행의 값 matrix[r-1][c]를 더합니다. 이 단계가 끝나면 각 셀에는 같은 열에서 맨 위부터 해당 행까지의 세로 합이 저장됩니다.
2단계 - 가로 방향 누적: r을 0부터 R-1까지, c를 1부터 C-1까지 순회하면서 matrix[r][c]에 바로 왼쪽 열의 값 matrix[r][c-1]을 더합니다. 이 단계를 거치면 각 셀에는 왼쪽 위 사각형 영역 전체의 합이 저장됩니다.
변환이 완료된 행렬을 반환합니다.
이 알고리즘의 시간 복잡도는 O(R × C)로, 행렬의 모든 원소를 한 번씩만 방문하면 됩니다. 또한 입력 행렬을 그대로 수정하여 활용하기 때문에 추가적인 메모리 사용 없이 제자리(in-place) 연산이 가능하다는 장점이 있습니다.
Python 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
def solve(matrix):
if not matrix:
return matrix
R, C = len(matrix), len(matrix[0])
for r in range(1, R):
for c in range(C):
matrix[r][c] += matrix[r - 1][c]
for r in range(R):
for c in range(1, C):
matrix[r][c] += matrix[r][c - 1]
return matrix
matrix = [
[8, 2],
[7, 4]
]
print(solve(matrix))입력
[[8, 2],[7, 4]]
출력
[[8, 10], [15, 21]]