문제 개요
정수 요소로 이루어진 2차원 배열(행렬)이 주어졌을 때, 행렬에서 부분 행렬(submatrix)을 추출하여 그 합이 최소가 되는 값을 구하는 것이 이번 문제의 목표입니다.
입출력 예시
입력 − int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
출력 − 주어진 2D 배열의 최소 합 부분 행렬: -9
설명 − 4행 4열, 크기 4x4의 2차원 배열이 주어졌습니다. 이 행렬에서 부분 행렬을 추출했을 때 최소 합이 -9가 되는 경우를 찾으면 됩니다.
입력 − int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3} }
출력 − 주어진 2D 배열의 최소 합 부분 행렬: -3
설명 − 3행 3열, 크기 3x3의 2차원 배열이 주어졌습니다. 주어진 행렬의 두 번째 행을 선택하면 최소 합 -3을 얻을 수 있으며, 이때 부분 행렬의 크기는 1행 3열, 즉 1x3입니다.
알고리즘 접근 방식
이 문제는 1차원 배열에서 최소 합 연속 구간을 찾는 카다네 알고리즘(Kadane's Algorithm)을 2차원으로 확장하여 해결합니다. 왼쪽 열부터 시작해 오른쪽으로 열 범위를 하나씩 넓혀 가며 각 열 범위에 대한 행별 누적 합을 계산하고, 카다네 알고리즘으로 그중 최소 합을 구하는 방식입니다.
정수 2차원 배열을 입력받아 처리를 위해 Minimum_Matrix(matrix) 함수로 전달합니다.
Minimum_Matrix(matrix) 함수 내부에서는 다음 과정을 수행합니다.
임시 변수 int result = INT_MAX, int arr[row], int total, int first, int end를 선언합니다.
temp를 0부터 column 미만까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 배열 요소를 0으로 초기화합니다. 이어서 temp_2를 temp부터 column 미만까지 반복하는 FOR 루프를 시작하고, 그 안에서 다시 i를 0부터 row 미만까지 반복하며 arr[i] = arr[i] + matrix[i][temp_2]로 갱신합니다.
total을 Algo_Kad(arr, &first, &end, row) 함수의 반환값으로 설정합니다.
total이 result보다 작으면 result를 total로 갱신합니다.
최종 결과로 result를 출력합니다.
Algo_Kad(int* arr, int* first, int* end, int max_size) 함수 내부에서는 다음 과정을 수행합니다.
임시 변수 int total = 0, int result = INT_MAX, int temp = 0, *end = -1을 선언합니다.
i를 0부터 max_size 미만까지 반복하며 total을 total + arr[i]로 갱신합니다.
total이 0보다 크면 total을 0으로, temp를 i + 1로 설정합니다.
그렇지 않고 total이 result보다 작으면 result를 total로, *first를 temp로, *end를 i로 설정합니다.
*end가 -1이 아니면 result를 반환합니다.
result를 arr[0]으로, *first를 0으로, *end를 0으로 설정합니다.
i를 1부터 max_size 미만까지 반복하며, arr[i]가 result보다 작으면 result를 arr[i]로, *first를 i로, *end를 i로 설정합니다.
result를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define row 4
#define column 4
int Algo_Kad(int* arr, int* first, int* end, int max_size)
{
int total = 0;
int result = INT_MAX;
int temp = 0;
*end = -1;
for(int i = 0; i < max_size; ++i)
{
total = total + arr[i];
if(total > 0)
{
total = 0;
temp = i + 1;
}
else if(total < result)
{
result = total;
*first = temp;
*end = i;
}
}
if(*end != -1)
{
return result;
}
result = arr[0];
*first = 0;
*end = 0;
for(int i = 1; i < max_size; i++)
{
if(arr[i] < result)
{
result = arr[i];
*first = i;
*end = i;
}
}
return result;
}
void Minimum_Matrix(int matrix[][column])
{
int result = INT_MAX;
int arr[row];
int total;
int first;
int end;
for(int temp = 0; temp < column; ++temp)
{
memset(arr, 0, sizeof(arr));
for(int temp_2 = temp; temp_2 < column; ++temp_2)
{
for(int i = 0; i < row; ++i)
{
arr[i] = arr[i] + matrix[i][temp_2];
}
total = Algo_Kad(arr, &first, &end, row);
if(total < result)
{
result = total;
}
}
}
cout<<"Minimum sum submatrix in a given 2D array is: "<<result;
}
int main()
{
int matrix[row][column] = {{2, 3, -1, 5},
{-2, 9, -1, 6},
{ 5, 6, 9, -9},
{ -6, 1, 1, 1} };
Minimum_Matrix(matrix);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Minimum sum submatrix in a given 2D array is: -9
시간 복잡도
열 범위를 선택하는 이중 루프가 O(column²)의 비용을 가지고, 각 단계마다 카다네 알고리즘이 O(row)의 시간에 동작하므로 전체 시간 복잡도는 O(row × column²)입니다. 이는 모든 가능한 부분 행렬을 일일이 탐색하는 완전 탐색 방식보다 훨씬 효율적입니다.