문제 개요
이 문제에서는 n×n 크기의 2차원 정방행렬 mat[][]가 주어집니다. 우리의 과제는 주어진 행렬이 토플리츠(Toeplitz) 행렬인지 아닌지를 판별하는 것입니다.
토플리츠 행렬이란?
토플리츠 행렬은 왼쪽 위에서 오른쪽 아래로 향하는 모든 대각선(하강 대각선) 위의 요소 값이 서로 동일한 행렬을 말합니다. 수식으로 표현하면, 모든 유효한 i와 j에 대해 다음 조건을 만족해야 합니다.
mat[i][j] == mat[i+1][j+1]
즉, 주대각선뿐만 아니라 그 위와 아래에 평행하게 놓인 모든 대각선의 값까지 일정해야 한다는 점이 핵심입니다.
예제로 문제 이해하기
입력:
Mat[][] = {{3, 5, 1},
{4, 3, 5},
{1, 4, 3}}출력: Yes
설명:
모든 하강 대각선의 값이 일정합니다.
- 주대각선 (0,0), (1,1), (2,2) → 모두 3
- 위쪽 대각선 (0,1), (1,2) → 모두 5
- 아래쪽 대각선 (1,0), (2,1) → 모두 4
- 나머지 대각선 (0,2) → 1, (2,0) → 1
따라서 이 행렬은 토플리츠 행렬입니다.
해결 접근 방법
가장 간단한 방법은 인접한 대각선 요소들을 직접 비교하는 것입니다. 행렬의 모든 위치 (i, j)에 대해 mat[i][j]와 오른쪽 아래 대각선 요소인 mat[i+1][j+1]의 값을 비교합니다.
- 하나라도 값이 다르면 즉시 false를 반환합니다.
- 모든 비교가 통과하면 해당 행렬은 토플리츠 행렬이므로 true를 반환합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
#define N 4
bool isToeplizMatrix(int mat[N][N])
{
for(int i = 0; i < N - 1; i++)
{
for(int j = 0; j < N - 1; j++)
{
// 현재 요소와 오른쪽 아래 대각선 요소 비교
if(mat[i][j] != mat[i + 1][j + 1]){
return false;
}
}
}
return true;
}
int main(){
int mat[N][N] = { { 6, 7, 8, 9 },
{ 4, 6, 7, 8 },
{ 1, 4, 6, 7 },
{ 0, 1, 4, 6 }};
if (isToeplizMatrix(mat))
cout<<"주어진 행렬은 토플리츠 행렬입니다.";
else
cout<<"주어진 행렬은 토플리츠 행렬이 아닙니다.";
return 0;
}
출력 결과
주어진 행렬은 토플리츠 행렬입니다.
복잡도 분석
- 시간 복잡도: O(n²) — 행렬의 거의 모든 요소를 한 번씩 확인해야 합니다.
- 공간 복잡도: O(1) — 별도의 추가 메모리 없이 제자리에서 검사를 수행합니다.
마무리
토플리츠 행렬 판별은 이중 반복문으로 인접한 대각선 요소만 비교하면 되는 간단한 문제입니다. 신호 처리, 이미지 처리 등 다양한 분야에서 활용되는 행렬 구조이므로 개념과 구현 방법을 함께 기억해 두면 유용합니다.