행(row)의 개수 r과 열(column)의 개수 c가 같은 정사각 행렬 M[r][c]가 주어졌을 때, 이 행렬이 상부 삼각 행렬(Upper Triangular Matrix)인지 판별하는 것이 이번 글의 목표입니다.
상부 삼각 행렬이란?
상부 삼각 행렬은 주대각선(main diagonal)을 기준으로 위쪽에 위치한 원소들은 0이 아니고, 아래쪽에 위치한 모든 원소는 0인 행렬을 말합니다.
아래 그림처럼 주대각선 아래쪽에 있는 원소들(그림에서 빨간색으로 표시된 부분)이 모두 0이고, 나머지 원소들은 0이 아닌 값을 가집니다.
예제
입력: m[3][3] = { {1, 2, 3},
{0, 5, 6},
{0, 0, 9}}
출력: yes (상부 삼각 행렬)
입력: m[3][3] = { {3, 0, 1},
{6, 2, 0},
{7, 5, 3} }
출력: no (상부 삼각 행렬이 아님)첫 번째 예제에서는 주대각선 아래의 원소가 모두 0이므로 상부 삼각 행렬이지만, 두 번째 예제에서는 arr[1][0]=6, arr[2][0]=7, arr[2][1]=5처럼 아래쪽에 0이 아닌 값이 존재하므로 상부 삼각 행렬이 아닙니다.
알고리즘
시작 1단계 → 매크로를 #define size 4로 정의한다. 2단계 → 행렬이 상부 삼각 행렬인지 확인하는 함수를 선언한다. bool check(int arr[size][size]) i = 1부터 i < size까지 반복 j = 0부터 j < i까지 반복 if (arr[i][j] != 0) return false 반복문이 끝나면 return true 3단계 → main() 함수에서 4x4 크기의 2차원 배열 arr을 선언하고 초기화한다. if (check(arr))이 참이면 "상부 삼각 행렬입니다" 출력 거짓이면 "상부 삼각 행렬이 아닙니다" 출력 종료
C++ 코드 구현
#include <bits/stdc++.h>
#define size 4
using namespace std;
// 행렬이 상부 삼각 행렬인지 확인하는 함수
bool check(int arr[size][size]){
for (int i = 1; i < size; i++)
for (int j = 0; j < i; j++)
if (arr[i][j] != 0)
return false;
return true;
}
int main(){
int arr[size][size] = { { 1, 1, 3, 2 },
{ 0, 3, 3, 2 },
{ 0, 0, 2, 1 },
{ 0, 0, 0, 1 } };
if (check(arr))
cout << "상부 삼각 행렬입니다";
else
cout << "상부 삼각 행렬이 아닙니다";
return 0;
}실행 결과
상부 삼각 행렬입니다
동작 원리 및 시간 복잡도
핵심 로직은 매우 간단합니다. 바깥쪽 반복문은 행 인덱스 i를 1부터 순회하고, 안쪽 반복문은 각 행에서 주대각선보다 왼쪽에 있는 열(j < i)만 검사합니다. 만약 해당 위치의 원소가 하나라도 0이 아니라면 즉시 false를 반환하여 상부 삼각 행렬이 아님을 알립니다.
모든 아래쪽 원소가 0이라면 검사를 통과하고 true를 반환합니다. 이 알고리즘은 행렬의 절반 영역만 확인하므로 시간 복잡도는 O(n²)이며, 추가 메모리를 사용하지 않는 제자리(in-place) 검사 방식입니다.