C++로 행렬(Matrix)에서 최대 합을 가진 열 찾는 방법

M × N 크기의 행렬(matrix)이 주어졌다고 가정해 봅시다. 우리의 목표는 요소들의 합계가 가장 큰 열(column)을 찾는 것입니다. 이 프로그램에서는 특별히 복잡한 기법을 사용하지 않고, 배열을 열 단위로 순회하며 각 열의 합계를 구한 뒤, 그 합이 최댓값일 경우 합계와 함께 해당 열의 인덱스를 출력하는 방식으로 문제를 해결합니다.

알고리즘

프로그램의 동작 과정은 다음과 같습니다.
1. 각 열마다 colSum() 함수를 호출하여 해당 열의 모든 요소 합계를 계산합니다.
2. 계산된 합계를 현재까지의 최댓값(maxSum)과 비교합니다.
3. 합계가 더 크면 최댓값과 열 인덱스를 새로 갱신합니다.
4. 모든 열에 대한 반복이 끝나면 최대 합을 가진 열의 인덱스와 합계를 출력합니다.

예제 코드

#include<iostream>
#define M 5
#define N 5
using namespace std;
int colSum(int colIndex, int mat[M][N]){
    int sum = 0;
    for(int i = 0; i<M; i++){
        sum += mat[i][colIndex];
    }
    return sum;
}
void maxColumnSum(int mat[M][N]) {
    int index = -1;
    int maxSum = INT_MIN;
    for (int i = 0; i < N; i++) {
        int sum = colSum(i, mat);
        if (sum > maxSum) {
            maxSum = sum;
            index = i;
        }
    }
    cout << "Index: " << index << ", Column Sum: " << maxSum;
}
int main() {
    int mat[M][N] = {
        { 1, 2, 3, 4, 5 },
        { 5, 3, 1, 4, 2 },
        { 5, 6, 7, 8, 9 },
        { 0, 6, 3, 4, 12 },
        { 9, 7, 12, 4, 3 },
    };
    maxColumnSum(mat);
}

출력 결과

Index: 4, Column Sum: 31

코드 설명

colSum() 함수

colSum() 함수는 열 인덱스(colIndex)를 매개변수로 받아, 해당 열의 첫 번째 행부터 마지막 행까지 모든 요소를 더한 값을 반환합니다.

maxColumnSum() 함수

maxColumnSum() 함수는 0번 열부터 N-1번 열까지 차례대로 colSum()을 호출하며 각 열의 합계를 구합니다. 최댓값 변수(maxSum)는 INT_MIN으로 초기화되어 있으므로, 행렬의 모든 요소가 음수인 경우에도 올바르게 동작합니다. 각 열의 합계가 기존 최댓값보다 크면 maxSum과 index를 갱신하고, 모든 열을 확인한 후 최종 결과를 화면에 출력합니다.

시간 및 공간 복잡도

하나의 열 합계를 구하는 데 O(M)의 시간이 걸리고, 총 N개의 열을 검사하므로 전체 시간 복잡도는 O(M × N)입니다. 추가적인 메모리를 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다.