C++ 동적 계획법으로 2D 행렬의 최대 합 사각형 찾기

문제 개요

이 튜토리얼에서는 2차원 행렬(2D Matrix)에서 원소들의 합이 최대가 되는 사각형 부분 행렬을 찾는 프로그램을 구현해 보겠습니다.

음수와 양수가 섞여 있는 행렬이 주어졌을 때, 우리의 목표는 포함된 모든 원소의 합이 가장 큰 직사각형 영역을 찾아 그 위치와 합계를 출력하는 것입니다.

접근 방식: 카데인 알고리즘의 확장

이 문제는 1차원 배열의 최대 부분 배열 합을 구하는 유명한 카데인 알고리즘(Kadane's Algorithm)을 2차원으로 확장하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

행렬의 왼쪽 열(left)과 오른쪽 열(right) 쌍을 하나씩 고정합니다.
두 열 사이에 있는 각 행의 원소 합을 임시 배열(temp)에 누적합니다.
누적된 1차원 배열에 카데인 알고리즘을 적용해 해당 열 범위에서의 최대 합을 구합니다.
모든 열 쌍에 대해 위 과정을 반복하며 전체 최댓값을 갱신합니다.

이렇게 하면 단순 무작정 탐색(O(R²×C²))보다 훨씬 빠른 O(C² × R)의 시간 복잡도로 해를 구할 수 있습니다. 여기서 R은 행의 개수, C는 열의 개수입니다.

구현 예제

#include<bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5

// 카데인 알고리즘으로 1차원 배열의 최대 합 계산
int kadane(int* arr, int* start,
int* finish, int n) {
    int sum = 0, maxSum = INT_MIN, i;
    *finish = -1;
    int local_start = 0;
    for (i = 0; i < n; ++i) {
        sum += arr[i];
        if (sum < 0) {
            sum = 0;
            local_start = i + 1;
        }
        else if (sum > maxSum) {
            maxSum = sum;
            *start = local_start;
            *finish = i;
        }
    }
    // 배열의 모든 원소가 음수인 경우 처리
    if (*finish != -1)
        return maxSum;
    maxSum = arr[0];
    *start = *finish = 0;
    // 최대 원소 탐색
    for (i = 1; i < n; i++) {
        if (arr[i] > maxSum){
            maxSum = arr[i];
            *start = *finish = i;
        }
    }
    return maxSum;
}

void findMaxSum(int M[][COL]) {
    int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
    int left, right, i;
    int temp[ROW], sum, start, finish;

    // 왼쪽 열 경계 설정
    for (left = 0; left < COL; ++left) {
        memset(temp, 0, sizeof(temp));
        // 오른쪽 열 경계 설정
        for (right = left; right < COL; ++right) {
            // 현재 열 범위의 각 행 합 누적
            for (i = 0; i < ROW; ++i)
                temp[i] += M[i][right];

            // 누적된 배열에 대해 최대 합 계산
            sum = kadane(temp, &start, &finish, ROW);

            // 전체 최댓값 갱신 및 좌표 저장
            if (sum > maxSum) {
                maxSum = sum;
                finalLeft = left;
                finalRight = right;
                finalTop = start;
                finalBottom = finish;
            }
        }
    }

    cout << "(Top, Left) (" << finalTop << ", " << finalLeft << ")" << endl;
    cout << "(Bottom, Right) (" << finalBottom << ", " << finalRight << ")" << endl;
    cout << "Max sum is: " << maxSum << endl;
}

int main() {
    int M[ROW][COL] = {
        {1, 2, -1, -4, -20},
        {-8, -3, 4, 2, 1},
        {3, 8, 10, 1, 3},
        {-4, -1, 1, 7, -6}
    };
    findMaxSum(M);
    return 0;
}

실행 결과

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
Max sum is: 29

결과 분석

위 예제에서 최대 합을 가지는 사각형은 (1,1)부터 (3,3)까지의 부분 행렬이며, 이 영역의 원소들을 모두 더하면 다음과 같이 29가 됩니다.

-3  4  2
 8 10  1
-1  1  7

특히 코드에서 주목할 점은 카데인 함수 내 마지막 부분입니다. 배열의 모든 원소가 음수일 경우 일반적인 카데인 알고리즘은 0을 반환하게 되는데, 이 경우에는 배열 내에서 가장 큰 단일 원소를 최대합으로 반환하도록 예외 처리를 해두었습니다.

복잡도 분석