C++로 행렬에서 합이 가장 큰 행 찾기

이 문제에서는 N×N 크기의 행렬 mat[][]이 주어지며, 우리의 목표는 행렬에서 요소의 합이 가장 큰 행을 찾는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력

mat[][] = {
    8, 4, 1, 9
    3, 5, 7, 9
    2, 4, 6, 8
    1, 2, 3, 4
}

출력

Row 2, sum 24

설명

Row 1: sum = 8+4+1+9 = 22
Row 2: sum = 3+5+7+9 = 24
Row 3: sum = 2+4+6+8 = 20
Row 4: sum = 1+2+3+4 = 10

각 행의 합을 계산해 보면 2번째 행의 합이 24로 가장 크므로, 정답은 2번째 행입니다.

풀이 접근 방법

이 문제를 해결하는 가장 간단한 방법은 각 행의 요소들을 모두 더한 뒤, 지금까지 계산한 최대 합과 비교하며 기록을 유지하는 것입니다. 모든 행을 순회하고 나면 최대 합을 가진 행의 인덱스와 합계 값을 반환하면 됩니다.

알고리즘의 동작 순서를 정리하면 다음과 같습니다.

알고리즘 단계

1. 최대 합을 저장할 변수 maxSum을 -1로, 해당 행의 인덱스를 저장할 변수 maxSumRow를 0으로 초기화합니다.
2. 행렬의 각 행에 대해 해당 행의 모든 열 요소를 순회하며 합계 sum을 계산합니다.
3. 현재 행의 합이 maxSum보다 크면 maxSum과 maxSumRow를 갱신합니다.
4. 모든 행의 순회가 끝나면 maxSumRow와 maxSum을 출력합니다.

이 솔루션의 동작을 보여주는 프로그램입니다.

예제 코드

#include <iostream>
using namespace std;
#define R 4
#define C 4
void findMax1Row(int mat[R][C]) {
    int maxSumRow = 0, maxSum = -1;
    int i, index;
    for (i = 0; i < R; i++) {
        int sum = 0;
        for(int j = 0; j < C; j++){
            sum += mat[i][j];
        }
        if(sum > maxSum){
            maxSum = sum;
            maxSumRow = i;
        }
    }
    cout<<"Row : "<<(maxSumRow+1)<<" has the maximum sum which is "<<maxSum;
}
int main() {
    int mat[R][C] = {
        {8, 4, 1, 9},
        {3, 5, 7, 9},
        {2, 4, 6, 8},
        {1, 2, 3, 4}
    };
    findMax1Row(mat);
    return 0;
}

실행 결과

Row : 2 has the maximum sum which is 24

복잡도 분석

이 솔루션은 행렬의 모든 요소를 한 번씩만 방문하므로, 시간 복잡도는 O(N²)이며, 추가적인 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.