C++로 주어진 행렬이 Hankel 행렬인지 판별하는 방법

Hankel 행렬이란?

정방행렬(square matrix)이 하나 주어졌을 때, 이 행렬이 Hankel 행렬인지 아닌지 판별하는 것이 우리의 과제입니다. Hankel 행렬은 왼쪽에서 오른쪽으로 거슬러 올라가는 각 반대각선(skew-diagonal) 위의 원소들이 모두 동일한 값을 갖는 정방행렬을 의미합니다.

예를 들어, 아래와 같은 5×5 행렬을 살펴보겠습니다.

위 행렬에서 왼쪽 아래 방향으로 올라가는 각 대각선을 따라 원소를 읽어 보면, 같은 대각선 위의 값들이 서로 일치하는 것을 확인할 수 있습니다. 따라서 이 행렬은 Hankel 행렬입니다.

판별 조건

주어진 행렬이 Hankel 행렬인지 확인하려면, 모든 좌표 (i, j)에 대해 mat[i][j] = a_i+j가 성립하는지 검사하면 됩니다. 여기서 a_i+j는 다음과 같이 정의할 수 있습니다.

• i + j < n인 경우 : a_i+j = mat[i+j][0]
• 그 외의 경우 : a_i+j = mat[i+j-n+1][n-1]

쉽게 말해, 행렬의 첫 번째 열과 마지막 행에 등장하는 값들을 기준으로 삼고, 전체 행렬의 모든 원소가 자신이 속한 반대각선의 기준값과 일치하는지 비교하는 방식입니다.

C++ 구현 예제

#include <iostream>
#define N 5
using namespace std;
bool isHankelMat(int mat[N][N], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i + j < n) {
                if (mat[i][j] != mat[i + j][0])
                    return false;
            } else {
                if (mat[i][j] != mat[i + j - n + 1][n - 1])
                    return false;
            }
        }
    }
    return true;
}
int main() {
    int n = 5;
    int mat[N][N] = {
        { 1, 2, 3, 4, 5},
        { 2, 3, 4, 5, 6},
        { 3, 4, 5, 6, 7},
        { 4, 5, 6, 7, 8},
        { 5, 6, 7, 8, 9}
    };
    if(isHankelMat(mat, n))
        cout << "This is Hankel Matrix";
    else
        cout << "This is not Hankel Matrix";
}

실행 결과

This is Hankel Matrix

시간 및 공간 복잡도

이 알고리즘은 n×n 크기의 행렬에 존재하는 모든 원소를 한 번씩 순회하여 검사하므로 시간 복잡도는 O(n²)입니다. 또한 별도의 추가 메모리 공간을 사용하지 않기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다.