문제 개요
이 문제에서는 n×n 크기의 정사각형 행렬이 주어집니다. 우리의 과제는 행렬 대각선에 있는 원소들 중 최솟값과 최댓값을 찾는 것입니다. 즉, 주대각선(Principal Diagonal)과 부대각선(Secondary Diagonal) 각각에 대해 가장 작은 값과 가장 큰 값을 구해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력
mat[][] = {
{3, 4, 7},
{5, 2, 1},
{1, 8, 6}
}출력
주대각선의 최솟값 = 2
주대각선의 최댓값 = 6
부대각선의 최솟값 = 1
부대각선의 최댓값 = 7
해결 방법 1: 중첩 루프 사용
가장 기본적인 해결 방법은 중첩 루프(nested loop)를 활용하는 것입니다. 주대각선의 원소를 검사할 때는 i == j 조건을, 부대각선의 원소를 검사할 때는 i + j == n - 1 조건을 사용합니다. 이 조건들을 만족하는 원소들을 순회하면서 각 대각선별로 최댓값과 최솟값을 갱신해 나가면 됩니다.
이 해결 방법의 동작을 보여주는 프로그램입니다.
예제 코드
#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
if (n == 0)
return;
int pDiagMin = mat[0][0],
pDiagMax = mat[0][0];
int sDiagMin = mat[0][n - 1 ],
sDiagMax = mat[0][n - 1];
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (i == j){
if (mat[i][j] < pDiagMin)
pDiagMin = mat[i][j];
if (mat[i][j] > pDiagMax)
pDiagMax = mat[i][j];
}
if ((i + j) == (n - 1)) {
if (mat[i][j] < sDiagMin){
sDiagMin = mat[i][j];
}
if (mat[i][j] > sDiagMax)
sDiagMax = mat[i][j];
}
}
}
cout<<(" Smallest Element of Principal Diagonal : ")<<pDiagMin;
cout<<(" Greatest Element of Principal Diagonal : ")<<pDiagMax;
cout<<(" Smallest Element of Secondary Diagonal : ")<<sDiagMin;
cout<<(" Greatest Element of Secondary Diagonal : ")<<sDiagMax;
}
int main(){
int mat[3][3] = {
{ 3, 4, 7 },
{ 0, 2, 1 },
{ 1, 7, 8 }
};
int n = sizeof(mat) / sizeof(mat[0]);
findMaxAndMinOfDiagonals(mat, n);
}
출력 결과
Smallest Element of Principal Diagonal : 2
Greatest Element of Principal Diagonal : 8
Smallest Element of Secondary Diagonal : 2
Greatest Element of Secondary Diagonal : 7
해결 방법 2: 단일 루프 사용 (더 효율적)
더 효율적인 접근 방식은 중첩 루프를 단일 루프로 줄이는 것입니다. 여기에는 간단한 수학적 성질이 활용됩니다. 주대각선의 원소는 행 인덱스와 열 인덱스가 서로 같고, 부대각선의 원소는 두 인덱스의 합이 n-1이라는 점입니다.
주대각선의 원소 = mat[i][i]
마찬가지로, 부대각선의 원소 = mat[i][n - i - 1]
이 공식을 이용하면 j에 대한 내부 루프 없이 i 하나만 반복하면서 두 대각선의 모든 원소를 한 번에 처리할 수 있습니다.
이 해결 방법의 동작을 보여주는 프로그램입니다.
예제 코드
#include<iostream>
using namespace std;
void findMaxAndMinOfDiagonals(int mat[3][3], int n){
if (n == 0)
return;
int pDiagMin = mat[0][0],
pDiagMax = mat[0][0];
int sDiagMin = mat[0][n - 1 ],
sDiagMax = mat[0][n - 1];
for (int i = 1; i < n; i++) {
if (mat[i][i] < pDiagMin)
pDiagMin = mat[i][i];
if (mat[i][i] > pDiagMax)
pDiagMax = mat[i][i];
if (mat[i][n - 1 - i] < sDiagMin)
sDiagMin = mat[i][n - 1 - i];
if (mat[i][n - 1 - i] > sDiagMax)
sDiagMax = mat[i][n - 1 - i];
}
cout<<(" Smallest Element of Principal Diagonal : ")<<pDiagMin;
cout<<(" Greatest Element of Principal Diagonal : ")<<pDiagMax;
cout<<(" Smallest Element of Secondary Diagonal : ")<<sDiagMin;
cout<<(" Greatest Element of Secondary Diagonal : ")<<sDiagMax;
}
int main(){
int mat[3][3] = {
{ 3, 4, 7 },
{ 0, 2, 1 },
{ 1, 7, 8 }
};
int n = sizeof(mat) / sizeof(mat[0]);
findMaxAndMinOfDiagonals(mat, n);
}
출력 결과
Smallest Element of Principal Diagonal : 2
Greatest Element of Principal Diagonal : 8
Smallest Element of Secondary Diagonal : 1
Greatest Element of Secondary Diagonal : 7
복잡도 비교
중첩 루프를 사용하는 첫 번째 방법의 시간 복잡도는 O(n²)인 반면, 단일 루프를 사용하는 두 번째 방법은 O(n)으로 더 효율적입니다. 두 방법 모두 추가 배열 없이 상수 개수의 변수만 사용하므로 공간 복잡도는 O(1)로 동일합니다. 따라서 실무에서는 인덱스 규칙(i == j, i + j == n - 1)을 직접 활용하는 단일 루프 방식을 권장합니다.