문제 개요
정수로 구성된 2차원 행렬이 주어졌을 때, 원소들의 합이 최대가 되는 직사각형(경우에 따라 정사각형) 부분 행렬을 찾는 것이 목표입니다.
이 알고리즘의 핵심 아이디어는 왼쪽 열과 오른쪽 열을 고정하는 것에서 출발합니다. 두 열을 고정한 상태에서 각 행마다 왼쪽 열부터 오른쪽 열까지의 원소 합을 계산하여 임시 배열(temp)에 저장합니다. 그다음 이 1차원 배열에 카데인 알고리즘(Kadane's Algorithm)을 적용하면 최대 합을 가지는 연속 구간, 즉 위쪽 행(top)과 아래쪽 행(bottom)의 위치를 구할 수 있습니다. 고정해 둔 좌우 열과 카데인 알고리즘이 찾아낸 상하 행이 만나면 최대 합 직사각형이 완성됩니다.
입력 및 출력
입력:
정수 행렬
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6
출력:
부분 행렬의 좌상단 좌표, 우하단 좌표, 그리고 부분 행렬의 총합
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29
알고리즘
kadaneAlgorithm(array, start, end, n)
입력: 각 행의 합이 담긴 배열, 시작·끝 위치를 저장할 참조 변수, 원소 개수 n
출력: 최대 합과 함께 시작·끝 위치를 결정
시작
sum := 0, maxSum := -∞
end := -1
tempStart := 0
배열의 각 원소 i에 대해 반복
sum := sum + array[i]
만약 sum < 0 이면
sum := 0
tempStart := i + 1
아니고 sum > maxSum 이면
maxSum := sum
start := tempStart
end := i
반복 끝
만약 end ≠ -1 이면
maxSum 반환
// 배열의 모든 원소가 음수인 경우 처리
maxSum := array[0], start := 0, end := 0
배열의 1번째부터 n-1번째 원소 i에 대해 반복
만약 array[i] > maxSum 이면
maxSum := array[i]
start := i, end := i
반복 끝
maxSum 반환
끝
maxSumRect(Matrix)
입력: 주어진 행렬
출력: 직사각형의 최대 합
시작
maxSum := -∞
행렬의 행 수와 같은 크기의 임시 배열 temp 정의
left := 0 부터 열의 개수까지 반복
temp 배열을 0으로 초기화
right := left 부터 열의 개수 - 1 까지 반복
각 행 i에 대해
temp[i] := matrix[i][right]
sum := kadaneAlgorithm(temp, start, end, 행의 개수)
만약 sum > maxSum 이면
maxSum := sum
endLeft := left
endRight := right
endTop := start
endBottom := end
반복 끝
반복 끝
좌상단·우하단 좌표와 maxSum 출력
끝
C++ 구현 예제
#include<iostream>
#define ROW 4
#define COL 5
using namespace std;
int M[ROW][COL] = {
{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}
};
// 최대 합과 시작·끝 위치를 찾는 카데인 알고리즘
int kadaneAlgo(int arr[], int &start, int &end, int n) {
int sum = 0, maxSum = INT_MIN;
end = -1; // 처음에는 선택된 위치가 없음
int tempStart = 0; // 0부터 시작
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum < 0) { // 누적 합이 음수가 되면 버리고 새로 시작
sum = 0;
tempStart = i+1;
}else if (sum > maxSum) { // 최대 합 갱신 시 시작·끝 인덱스 업데이트
maxSum = sum;
start = tempStart;
end = i;
}
}
if (end != -1)
return maxSum;
// 배열의 모든 원소가 음수인 경우: 가장 큰 단일 원소 선택
maxSum = arr[0];
start = end = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > maxSum) {
maxSum = arr[i];
start = end = i;
}
}
return maxSum;
}
void maxSumRect() {
int maxSum = INT_MIN, endLeft, endRight, endTop, endBottom;
int left, right;
int temp[ROW], sum, start, end;
for (left = 0; left < COL; left++) {
for(int i = 0; i<ROW; i++) // temp를 0으로 초기화
temp[i] = 0;
for (right = left; right < COL; ++right) {
for (int i = 0; i < ROW; ++i) // 각 행마다 열 구간의 합을 누적
temp[i] += M[i][right];
sum = kadaneAlgo(temp, start, end, ROW); // (top,left)~(bottom,right) 직사각형의 합 계산
if (sum > maxSum) { // 최대값 갱신 시 네 꼭짓점 좌표 저장
maxSum = sum;
endLeft = left;
endRight = right;
endTop = start;
endBottom = end;
}
}
}
cout << "(Top, Left) ("<<endTop<<", "<<endLeft<<")"<<endl;
cout << "(Bottom, Right) ("<<endBottom<<", "<<endRight<<")"<<endl;
cout << "The max sum is: "<< maxSum;
}
int main() {
maxSumRect();
}
실행 결과
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29
시간 복잡도
왼쪽 열과 오른쪽 열의 모든 조합을 살펴보는 데 O(C²)의 시간이 걸리며, 각 조합마다 카데인 알고리즘이 O(R) 시간에 동작합니다. 따라서 전체 시간 복잡도는 O(R × C²)입니다(단, R은 행의 수, C는 열의 수). 모든 가능한 직사각형을 일일이 더해 보는 브루트 포스 방식(O(R²C²))보다 훨씬 효율적이라는 점이 이 알고리즘의 큰 장점입니다.
또한 카데인 알고리즘 내부에는 배열의 모든 원소가 음수인 경우를 처리하는 로직이 포함되어 있어, 그런 입력에서도 가장 큰 단일 원소를 올바르게 반환합니다.