파이썬(Python)으로 주어진 행렬이 토플리츠 행렬(Toeplitz Matrix)인지 확인하는 방법

행렬 M이 주어졌을 때, 이 행렬이 토플리츠 행렬(Toeplitz Matrix)인지 판별하는 프로그램을 만들어 보겠습니다. 토플리츠 행렬이란 왼쪽에서 오른쪽 아래로 내려가는 모든 대각선(주대각선 방향)의 값이 서로 같은 행렬을 말합니다.

토플리츠 행렬의 조건

예를 들어 다음과 같은 입력 행렬이 있다고 가정해 봅시다.

이 행렬을 살펴보면 왼쪽 위에서 오른쪽 아래로 향하는 각 대각선의 값이 모두 동일합니다. 따라서 이 행렬은 토플리츠 행렬이며, 출력 결과는 True가 됩니다.

해결 접근 방법

이 문제는 간단한 반복문 비교만으로 해결할 수 있습니다. 핵심 아이디어는 현재 위치의 값과 바로 오른쪽 아래 대각선 위치의 값을 비교하는 것입니다.

• 마지막 행을 제외한 각 행 i에 대해 반복합니다.
• 마지막 열을 제외한 각 열 j에 대해 반복합니다.
• matrix[i][j]와 matrix[i+1][j+1]의 값이 다르면 즉시 False를 반환합니다.
• 모든 비교를 통과하면 True를 반환합니다.

행렬의 경계(마지막 행과 마지막 열)는 비교 대상이 되는 오른쪽 아래 요소가 없으므로 반복 범위에서 제외한다는 점에 유의하세요.

구현 예제

class Solution:
    def solve(self, matrix):
        for i in range(len(matrix)-1):
            for j in range(len(matrix[0])-1):
                if matrix[i][j] != matrix[i+1][j+1]:
                    return False
        return True

ob = Solution()
matrix = [[7, 2, 6], [3, 7, 2], [5, 3, 7]]
print(ob.solve(matrix))

입력

[[7, 2, 6],
[3, 7, 2],
[5, 3, 7]]

출력

True

시간 복잡도 분석

이 알고리즘은 행렬의 모든 인접 대각선 요소 쌍을 한 번씩만 비교하므로, 시간 복잡도는 O(m × n)(m은 행의 개수, n은 열의 개수)입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.

정리

토플리츠 행렬 판별은 이중 반복문을 활용한 단순 비교로 해결할 수 있는 대표적인 행렬 문제입니다. 현재 요소와 오른쪽 아래 요소만 일치하면 되기 때문에 구현이 직관적이며, 실무에서도 신호 처리나 이미지 연산 분야에서 자주 등장하는 개념이니 꼭 기억해 두시기 바랍니다.