C#으로 행별 증가 행렬에서 효율적으로 검색하는 방법

이 문제의 가장 기본적인 해결 방법은 입력 행렬에 저장된 모든 요소를 처음부터 끝까지 훑어보며 주어진 키를 찾는 것입니다. 이러한 선형 탐색(linear search) 방식은 행렬의 크기가 MxN일 때 O(MN)의 시간 복잡도를 가지므로, 행렬이 클수록 매우 비효율적입니다.

행별로 증가하는 행렬의 특성을 활용하면 훨씬 빠른 탐색이 가능합니다. 핵심 아이디어는 행렬의 오른쪽 상단(top-right)에서 탐색을 시작하는 것입니다. 찾으려는 값이 현재 위치의 값보다 크면 행(row)을 한 칸 증가시키고, 반대로 작으면 열(column)을 한 칸 감소시킵니다. 이 과정을 반복하면 매 단계마다 한 행 또는 한 열 전체를 탐색 대상에서 제외할 수 있어, 시간 복잡도를 O(M+N)까지 줄일 수 있습니다.

알고리즘 동작 원리

예를 들어 다음과 같은 3x4 행렬에서 11을 찾는다고 가정해 보겠습니다.

1   7   10  19
2   8   11  20
3   9   12  21

오른쪽 상단의 19에서 시작하면, 11은 19보다 작으므로 열을 왼쪽으로 이동합니다. 다음 값인 10보다 11이 크므로 행을 아래로 이동하고, 이후 11을 만나면 탐색에 성공하게 됩니다.

아래 코드는 2차원 배열과 검색 키를 입력으로 받아, 검색 성공 여부에 따라 true 또는 false를 반환하는 SearchRowwiseIncrementedMatrix 함수를 구현한 예제입니다.

코드

public class Matrix{
    public bool SearchRowwiseIncrementedMatrix(int[] mat, int searchElement){
        int row = getMatrixRowSize(mat);
        int col = getMatrixColSize(mat) - 1;
        int r = 0;

        while (col >= 0 && r < row){
            if (mat[r, col] == searchElement){
                return true;
            }
            else if (searchElement < mat[r, col]){
                col--;
            }
            else{
                r++;
            }
        }
        return false;
    }

    private int getMatrixRowSize(int[] mat){
        return mat.GetLength(0);
    }
    private int getMatrixColSize(int[] mat){
        return mat.GetLength(1);
    }
}

static void Main(string[] args){
    Matrix m = new Matrix();
    int[] mat = new int[3, 4] { { 1, 7, 10, 19 }, { 2, 8, 11, 20 }, { 3, 9, 12, 21 } };
    Console.WriteLine(m.SearchRowwiseIncrementedMatrix(mat, 11));
}

실행 결과

TRUE

이처럼 행렬의 정렬 특성을 활용한 탐색 기법은 선형 탐색 대비 성능을 크게 향상시킬 수 있으며, 특히 큰 규모의 정렬된 행렬 데이터를 다룰 때 유용하게 활용됩니다.