C++에서 주어진 행렬의 모든 부분행렬에 대한 최대 트레이스(Trace) 구하기

이 문제에서는 2차원 배열 arr[][]가 주어지며, C++을 사용해 주어진 행렬에서 만들 수 있는 모든 부분행렬(sub-matrix) 중 최대 트레이스(trace)를 구하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

트레이스(trace)란 행렬의 주대각선(main diagonal) 요소들의 합을 의미합니다. 즉, 원본 행렬에서 추출할 수 있는 모든 정사각형 부분행렬의 트레이스 값을 계산한 뒤, 그중 가장 큰 값을 찾아야 합니다.

예제를 통해 문제를 자세히 살펴보겠습니다.

입력

arr[][] = {{-2, 5, 3},
{1, 6, 2},
{4, 3, 9}}

출력

15

설명

두 번째·세 번째 행과 두 번째·세 번째 열로 이루어진 부분행렬을 살펴보면,

{6, 2}
{3, 9}

이 부분행렬의 트레이스는 6 + 9 = 15로, 만들 수 있는 모든 부분행렬의 트레이스 중 가장 큰 값입니다.

해결 접근 방법

핵심 아이디어는 간단합니다. 임의의 정사각형 부분행렬의 주대각선은 반드시 원본 행렬의 대각선 방향에 놓인 연속된 구간에 해당한다는 점입니다.

따라서 행렬의 모든 위치 (i, j)를 시작점으로 삼아 오른쪽 아래 대각선 방향으로 요소를 하나씩 누적하며 부분합을 계산하고, 그 과정에서 나온 최댓값을 계속 갱신하면 됩니다. 이는 1차원 배열에서 최대 부분배열 합(max subarray sum)을 구하는 카데인(Kadane) 알고리즘과 유사한 방식이며, 시간 복잡도는 O(N×M), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

위 해결 방법의 동작을 보여주는 C++ 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;
#define row 3
#define col 3

int CalcMaxTraceSubMat(int mat[row][col]){
    int maxtraceSum = 0, r, c, traceSum;
    for (int i = 0; i < row; i++){
        for (int j = 0; j < col; j++){
            r = i, c = j, traceSum = 0;
            while (r < row && c < col){
                traceSum += mat[r][c];
                r++;
                c++;
                maxtraceSum = max(traceSum, maxtraceSum);
            }
        }
    }
    return maxtraceSum;
}
int main() {
    int mat[row][col] = { {-2, 5, 3},
                       {1, 6, 2},
                       {4, 3, 9} };

    cout<<"The maximum trace possible for any submatrix is "<<CalcMaxTraceSubMat(mat);
    return 0;
}

출력

The maximum trace possible for any submatrix is 15

코드 동작 방식

위 코드는 행렬의 모든 칸 (i, j)를 시작점으로 설정한 뒤, 해당 위치에서 주대각선 방향(오른쪽 아래)으로 이동하면서 요소를 하나씩 더합니다. 매 단계마다 현재 누적합(traceSum)을 기존 최댓값(maxtraceSum)과 비교하여 더 큰 값으로 갱신하고, 모든 시작점에 대한 탐색이 끝나면 최종 최댓값을 반환합니다.

예를 들어 시작점 (1, 1)에서는 누적합이 6 → 6 + 9 = 15로 증가하며, 이 값이 전체 결과가 됩니다.