Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 행렬(2D 배열)의 접두사 합(Prefix Sum) 계산 방법

문제 개요

이 문제에서는 정수 값으로 이루어진 2차원 배열 mat[][]이 주어지며, 우리의 과제는 이 배열의 접두사 합(Prefix Sum) 행렬을 출력하는 것입니다.

접두사 합 행렬이란?

접두사 합 행렬에서 각 원소는 해당 위치를 기준으로 위쪽과 왼쪽에 있는 모든 원소들의 합을 의미합니다. 즉, 다음과 같이 정의할 수 있습니다.

prefixSum[i][j] = mat[i][j] + mat[i-1][j] + ... + mat[0][j] + mat[i][j-1] + ... + mat[i][0]

예시로 이해하기

구체적인 예시를 통해 문제를 살펴보겠습니다.

입력: arr = [
    [4   6   1]
    [5   7   2]
    [3   8   9]
]
출력: [
    [4   10   11]
    [9   22   25]
    [12  33   45]
]

위 예시에서 첫 번째 행의 두 번째 원소인 10은 같은 행의 앞 원소 4와 현재 원소 6을 더한 값이며, 마지막 원소 45는 행렬 전체 원소의 총합이 됩니다.

해결 방법

단순한 접근 방식

가장 직관적인 해결책은 (i, j) 위치까지의 모든 원소를 순회하면서 값을 더하는 것입니다. 하지만 이 방법은 중복 계산이 많아 시스템에 상당한 부담을 주며, 시간 복잡도가 비효율적입니다.

효율적인 접근 방식: 공식 활용

더 효과적인 방법은 이미 계산된 접두사 합 값을 재활용하는 공식을 사용하는 것입니다. (i, j) 위치의 원소를 구하는 일반 공식은 다음과 같습니다.

prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + a[i][j]

여기서 prefixSum[i-1][j-1]을 빼주는 이유는 위쪽 항과 왼쪽 항을 더할 때 대각선 방향의 값이 중복으로 포함되기 때문입니다.

특수 경우 처리

행렬의 경계에 있는 원소들은 일반 공식을 그대로 적용할 수 없으므로, 아래와 같은 특수 규칙으로 처리해야 합니다.

i = j = 0 인 경우:  prefixSum[i][j] = a[i][j]
i = 0, j > 0 인 경우:  prefixSum[i][j] = prefixSum[i][j-1] + a[i][j]
i > 0, j = 0 인 경우:  prefixSum[i][j] = prefixSum[i-1][j] + a[i][j]
  • (0, 0) 위치: 기준점이므로 원래 배열의 값 그대로 사용합니다.
  • 첫 번째 행: 왼쪽 원소의 접두사 합에 현재 값을 더합니다.
  • 첫 번째 열: 위쪽 원소의 접두사 합에 현재 값을 더합니다.

C++ 구현 코드

위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.

#include <iostream>
using namespace std;
#define R 3
#define C 3

void printPrefixSum(int a[][C]) {
    int prefixSum[R][C];
    
    // (0,0) 원소 초기화
    prefixSum[0][0] = a[0][0];
    
    // 첫 번째 행 계산
    for (int i = 1; i < C; i++)
        prefixSum[0][i] = prefixSum[0][i - 1] + a[0][i];
    
    // 첫 번째 열 계산
    for (int i = 1; i < R; i++)
        prefixSum[i][0] = prefixSum[i - 1][0] + a[i][0];
    
    // 나머지 원소는 공식으로 계산
    for (int i = 1; i < R; i++) {
        for (int j = 1; j < C; j++)
            prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1]
                            - prefixSum[i-1][j-1] + a[i][j];
    }
    
    // 결과 출력
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++)
            cout << prefixSum[i][j] << "\t";
        cout << endl;
    }
}

int main() {
    int mat[R][C] = {
        { 1, 2, 3},
        { 4, 5, 6},
        { 7, 8, 9}
    };
    
    cout << "접두사 합 행렬:\n";
    printPrefixSum(mat);
    
    return 0;
}

실행 결과

접두사 합 행렬:
1   3   6
5   12  21
12  27  45

시간 복잡도 분석

이 알고리즘은 행렬의 모든 원소를 한 번씩만 방문하면 되므로 시간 복잡도는 O(R × C)입니다. 단순히 매번 처음부터 합을 구하는 브루트포스 방식(O((R × C)²))에 비해 훨씬 효율적이며, 특히 행렬의 크기가 커질수록 그 차이가 크게 벌어집니다.

마무리

접두사 합 행렬은 이미지 처리, 구간 합 질의 응답 등 다양한 분야에서 활용되는 중요한 개념입니다. 이전에 계산한 결과를 재활용하는 동적 프로그래밍(DP) 사고방식을 익히는 좋은 예제이므로, 위 코드를 직접 구현해 보면서 원리를 확실히 이해해 보시기 바랍니다.