정방행렬(스퀘어 행렬) M[r][c]가 주어졌다고 가정해 보겠습니다. 여기서 'r'은 행(row)의 개수, 'c'는 열(column)의 개수를 의미하며 r = c 조건을 만족합니다. 이 글에서는 이러한 행렬 M이 하삼각 행렬(Lower Triangular Matrix)인지 판별하는 C++ 프로그램을 소개합니다.
하삼각 행렬이란?
하삼각 행렬은 주대각선(main diagonal)을 기준으로 아래쪽에 있는 요소들(주대각선 요소 포함)은 0이 아니고, 주대각선 위쪽의 모든 요소는 0으로만 채워진 행렬을 말합니다.
아래 그림과 같습니다.
위 그림에서 빨간색으로 강조된 요소들은 주대각선 위쪽에 위치하여 모두 0이며, 나머지 요소들은 0이 아닌 값을 가집니다.
예시
입력: m[3][3] = { {1, 0, 0},
{2, 3, 0},
{4, 5, 6}}
출력: yes
입력: m[3][3] = { {3, 0, 1},
{6, 2, 0},
{7, 5, 3} }
출력: no
첫 번째 예시에서는 주대각선 위쪽의 모든 요소가 0이므로 하삼각 행렬이지만, 두 번째 예시에서는 m[0][2]의 값이 1로 0이 아니므로 하삼각 행렬이 아닙니다.
알고리즘
시작
1단계 -> 매크로 정의: #define size 4
2단계 -> 행렬이 하삼각 행렬인지 검사하는 함수 선언
bool check(int arr[size][size])
i = 0부터 i < size까지 i를 1씩 증가시키며 반복
j = i + 1부터 j < size까지 j를 1씩 증가시키며 반복
if (arr[i][j] != 0)
return false
내부 반복문 종료
외부 반복문 종료
return true
3단계 -> main() 함수에서
배열 선언: int arr[size][size] = { { 1, 0, 0, 0 },
{ 2, 3, 0, 0 },
{ 4, 5, 6, 0 },
{ 7, 8, 9, 10 } }
if (check(arr))이 참이면
"하삼각 행렬입니다" 출력
거짓이면
"하삼각 행렬이 아닙니다" 출력
종료
C++ 구현 예제
#include <bits/stdc++.h>
#define size 4
using namespace std;
// 행렬이 하삼각 행렬인지 확인하는 함수
bool check(int arr[size][size]){
for (int i = 0; i < size; i++)
for (int j = i + 1; j < size; j++)
if (arr[i][j] != 0)
return false;
return true;
}
int main(){
int arr[size][size] = { { 1, 0, 0, 0 },
{ 2, 3, 0, 0 },
{ 4, 5, 6, 0 },
{ 7, 8, 9, 10 } };
if (check(arr))
cout << "하삼각 행렬입니다";
else
cout << "하삼각 행렬이 아닙니다";
return 0;
}
동작 원리
핵심 로직은 매우 간단합니다. 2차원 배열에서 행 인덱스 i보다 열 인덱스 j가 큰 위치, 즉 arr[i][j](i < j)는 주대각선 위쪽 영역에 해당합니다. 따라서 이중 반복문을 사용해 모든 i < j 위치의 값을 검사하고, 하나라도 0이 아니면 즉시 false를 반환합니다. 모든 검사를 통과하면 true를 반환하여 해당 행렬이 하삼각 행렬임을 알려줍니다.
이 알고리즘의 시간 복잡도는 O(n²)이며, 추가 메모리를 거의 사용하지 않는 O(1)의 공간 복잡도를 가진다는 장점이 있습니다.
실행 결과
하삼각 행렬입니다
이처럼 주대각선 위쪽 요소만 검사하면 되기 때문에 행렬 전체를 순회하는 것보다 더 효율적으로 하삼각 행렬 여부를 판별할 수 있습니다.