행렬을 구성하는 정수 요소의 2차원 배열이 제공됩니다. 작업은 그렇게 형성된 행렬에서 부분행렬을 가져와서 최소합의 개수를 계산하는 것입니다.
이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -
안에 - int 행렬[크기][크기] ={ {2, 3, -1, 5}, {-2, 9, -1, 6}, { 5, 6, 9, -9}, { -6, 1, 1, 1} }
아웃 - 주어진 2D 배열의 최소 합 부분행렬은 -9
입니다.설명 - 크기가 4x4인 2차원 배열, 즉 4행과 4열이 주어집니다. 이제, 우리는 최소 부분이 -9가 되도록 주어진 행렬에서 부분 행렬을 찾을 것입니다.
안 - 정수 행렬[행][열] ={ {4, 1, 3}, {-1, -1, -1}, { 6, 2, 3}}
아웃 - 주어진 2D 배열의 최소 합 부분행렬은 -3
입니다.설명 - 크기가 3x3인 2차원 배열, 즉 3행과 3열이 제공됩니다. 이제, 우리는 주어진 행렬에서 최소 부분이 -3이 되도록 부분 행렬을 찾을 것입니다. 이것은 주어진 행렬의 두 번째 행에서 달성되고 부분 행렬은 크기가 1x3, 즉 1행과 3열이 됩니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -
-
정수 2차원 배열을 입력하고 추가 처리를 위해 데이터를 Minimum_Matrix(matrix) 함수에 전달합니다.
-
Minimum_Matrix(matrix)
함수 내부-
임시 변수를 int result =INT_MAX, int arr[row], int total, int first 및 int end로 선언합니다.
-
int에서 temp로 열보다 작은 temp까지 루프 FOR를 시작합니다. 루프 내에서 배열 요소를 0으로 설정합니다. int에서 열보다 작은 temp_2까지 temp_2에서 다른 루프 FOR를 시작합니다. 루프 내에서 int i에서 0까지 i가 row보다 작을 때까지 다른 루프를 시작하고 arr[i]를 ar[i] + matrix[i][temo_2]로 설정합니다.
-
Algo_Kad(arr, &first, &end, row)
함수에 대한 호출로 합계를 설정합니다. -
총계가 결과보다 작으면 확인 후 결과를 총계로 설정
-
결과를 최종 출력으로 인쇄합니다.
-
-
함수 내부 int Algo_Kad(int* arr, int* first, int* end, int max_size)
-
임시 변수를 int total은 0, int result는 INT_MAX, int temp는 0 및 *end =-1
로 선언합니다. -
i에서 max_size보다 작아질 때까지 FOR 루프를 시작합니다. 루프 내에서 total을 total + arr[i]로 설정합니다.
-
IF total이 0보다 큰지 확인한 다음 total을 0으로, temp를 i + 1로 설정합니다.
-
ELSE IF, 결과보다 적은 합계를 확인한 다음 결과를 합계로 설정하고 *먼저 임시로, *종료는 i
-
이제 IF *end가 -1과 같지 않은지 확인한 다음 결과를 반환합니다.
-
결과를 arr[0], *first를 0으로, *end를 0으로 설정
-
i에서 max_size보다 작아질 때까지 FOR 루프를 시작합니다. 루프 내에서 IF arr[i]가 결과보다 작은지 확인한 다음 결과를 arr[i]로 설정하고 *first는 i로, *end는 i
로 설정합니다. -
결과를 반환합니다.
-
예시
#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