이 튜토리얼에서는 C++ 프로그램을 작성하여 주어진 행렬이 대각선 우세 행렬인지 아닌지 판별하는 방법을 알아보겠습니다.
대각선 우세 행렬이란?
행렬의 각 행에서, 대각선에 위치한 원소(대각 요소)의 절댓값이 같은 행에 있는 나머지 원소들(비대각 요소)의 절댓값 합보다 크거나 같으면 그 행렬을 대각선 우세 행렬이라고 부릅니다.
다음 예시를 살펴보겠습니다.
4 2 1 3 5 2 2 4 7
위 행렬은 대각선 우세 행렬입니다. 그 이유는 다음과 같습니다.
|4| ≥ |2| + |1| |5| ≥ |3| + |2| |7| ≥ |4| + |2|
즉, 모든 대각 요소가 같은 행의 비대각 요소들의 합보다 크거나 같기 때문입니다.
문제 해결 접근 방식
문제를 해결하는 단계는 다음과 같습니다.
행렬의 각 행을 순회하며 다음 작업을 수행합니다.
해당 행에서 대각 요소를 제외한 나머지 원소들의 절댓값 합을 구합니다.
구한 합을 대각 요소의 절댓값과 비교합니다.
비대각 요소의 합이 대각 요소보다 크면 해당 행렬은 대각선 우세 행렬이 아니므로 "No"를 출력하고 종료합니다.
모든 행을 통과했다면 대각선 우세 행렬이므로 "Yes"를 출력합니다.
예제 코드
위 로직을 C++ 코드로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
#define N 3
bool isDiagonallyDominantMatrix(int matrix[N][N], int n) {
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i != j) {
sum += abs(matrix[i][j]);
}
}
if (abs(matrix[i][i]) < sum) {
return false;
}
}
return true;
}
int main() {
// int matrix[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int matrix[N][N] = {{4, 2, 1}, {3, 5, 2}, {2, 4, 7}};
if (isDiagonallyDominantMatrix(matrix, 3)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Yes
시간 복잡도
행렬의 모든 원소를 한 번씩 확인하므로 시간 복잡도는 O(n²)이며, 추가적인 공간 없이 수행되므로 공간 복잡도는 O(1)입니다.
마무리
이번 튜토리얼에서는 주어진 행렬이 대각선 우세 행렬인지 판별하는 C++ 프로그램을 살펴보았습니다. 대각선 우세 행렬은 야코비 반복법(Jacobi Method)이나 가우스-자이델 방법(Gauss-Seidel Method) 같은 수치 해석 기법에서 수렴 조건으로 활용되는 중요한 개념입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.