문제 개요
하나의 행렬이 주어졌을 때, 서로 다른 두 행에 속한 요소들의 합 사이의 최대 차이를 구하는 것이 이 글에서 다룰 문제입니다. i개의 행과 j개의 열로 이루어진 행렬 M[i][j]가 있고, 각 행을 R0부터 Ri-1까지라고 부르겠습니다. 이때 차이는 (Ry의 요소 합) − (Rx의 요소 합)으로 계산하며, 항상 x < y인 조합만 고려합니다.
예제로 이해하기
입력 1
M[4][4] = {
{ 1, 2, 0, 5 },
{ 0, 1, 1, 0 },
{ 7, 2, 3, 2 },
{ 1, 2, 4, 1 }
};
출력
Maximum difference here is : 12
설명 − 세 번째 행(R2)의 요소 합이 14로 가장 크고, 두 번째 행(R1)의 요소 합이 2로 가장 작습니다. 따라서 최대 차이는 14 − 2 = 12입니다.
입력 2
M[4][4] = {
{ 0, 2, 0, 5 },
{ 0, 1, 4, 0 },
{ 1, 2, 3, 2 },
{ 2, 2, 6, 0 }
};
출력
Maximum difference here is : 5
설명 − 네 번째 행(R3)의 요소 합이 10으로 가장 크고, 두 번째 행(R1)의 요소 합이 5로 가장 작습니다. 따라서 최대 차이는 10 − 5 = 5입니다.
풀이 접근 방법
- 행렬의 행 개수와 열 개수를 입력받습니다. 단, 두 행을 비교하려면 행은 최소 2개 이상이어야 합니다.
rowmaxd()함수에 행렬과 행 개수, 열 개수를 전달하고, 행 합들 사이의 최대 차이를 반환받습니다.- 먼저 행렬 M[row][col]의 각 행별 요소 합을 RSum[i] 배열에 저장합니다. RSum 배열의 크기는 행렬의 행 개수와 같습니다.
- 최대 차이 MD는 RSum[1] − RSum[0]으로 초기화합니다. RSum[0]은 0번째 행의 전체 합, RSum[1]은 1번째 행의 전체 합입니다.
- 동시에 RSum[0]이 배열에서 가장 작은 값이라고 가정하고 MIN 변수에 저장해 둡니다.
- for 루프로 RSum의 모든 원소를 순회하면서 RSum[i] − MIN > MD인지 검사하고, 조건을 만족하면 MD를 갱신합니다. 또한 현재 값이 MIN보다 작으면 MIN 역시 갱신합니다.
이 방식은 각 행의 합을 한 번씩만 지나가므로 시간 복잡도는 O(row × col)이며, 행 합을 저장하는 데 필요한 추가 공간은 O(row)입니다.
C 코드 예시
#include<stdio.h>
#define MAX 100
// 두 행 요소 합의 최대 차이를 계산하는 함수
// (앞선 행의 합을 뒤의 행의 합에서 뺀 값 중 최댓값 반환)
int rowmaxd(int M[][MAX], int row, int col){
// 각 행의 요소 합을 저장할 배열
int RSum[row];
for(int i=0;i<row;i++){
int sum=0;
for(int j=0;j<col;j++)
sum+=M[i][j];
RSum[i]=sum;
}
// RSum[j]-RSum[i] (i<j) 조건에서 두 값의 최대 차이 계산
int MD=RSum[1]-RSum[0];
int MIN=RSum[0];
for(int i=1;i<row;i++){
// 현재 차이가 MD보다 크면 MD 갱신
if(RSum[i]-MIN>MD)
MD=RSum[i]-MIN;
// 현재 값이 MIN보다 작으면 MIN 갱신
if(RSum[i]<MIN)
MIN=RSum[i];
}
return MD;
}
// 드라이버 프로그램
int main(){
int r = 5, c = 4;
int mat[][MAX] = {
{-1, 2, 3, 4},
{6, 3, 0, 1},
{-1, 7, 8, -3},
{3, 5, 1, 4},
{2, 1, 1, 0}};
printf("Maximum difference of sum of elements in two rows in a matrix: %d", rowmaxd(mat, r, c));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Maximum difference of sum of elements in two rows in a matrix: 5