C#으로 행·열 단위 정렬 행렬에서 효율적으로 검색하는 방법

정렬된 행렬 검색 문제란?

가장 단순한 해결 방법은 입력 행렬에 저장된 모든 요소를 처음부터 끝까지 훑어보며 주어진 키를 찾는 것입니다. 그러나 이러한 선형 검색 방식은 행렬의 크기가 M×N일 때 O(MN)의 시간이 걸려 상당히 비효율적입니다.

핵심 아이디어: 1차원 배열처럼 바라보기

행과 열 단위로 오름차순 정렬된 행렬은 하나의 정렬된 1차원 배열로 볼 수 있습니다. 모든 행을 위에서 아래 순서대로 이어 붙이면 전체가 오름차순으로 정렬된 1차원 배열이 되기 때문입니다.

예를 들어 다음 3×4 행렬은,

{ 1,  2,  3,  4 }
{ 5,  6,  7,  8 }
{ 9, 10, 11, 12 }

아래와 같은 정렬된 1차원 배열과 동일하게 취급할 수 있습니다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

이렇게 하면 시간 복잡도 O(log(MN))의 이진 탐색(Binary Search) 알고리즘을 그대로 적용할 수 있습니다.

1차원 인덱스 → 2차원 좌표 변환

1차원상의 중간 인덱스 mid를 실제 행렬 좌표로 바꿀 때는 다음 공식을 사용합니다.

• 행(row) = mid ÷ 열 개수
• 열(column) = mid % 열 개수

C# 구현 예제

아래 코드는 2차원 배열과 검색할 키 값을 입력받아, 키를 찾으면 true, 찾지 못하면 false를 반환하는 SearchRowwiseColumnWiseMatrix 함수를 구현한 예제입니다.

public class Matrix {
    public bool SearchRowwiseColumnWiseMatrix(int[] mat, int searchElement) {
        int col = getMatrixColSize(mat);
        int start = 0;
        int last = mat.Length - 1;
        while (start <= last) {
            int mid = start + (last - start) / 2;
            int mid_element = mat[mid / col, mid % col];
            if (searchElement == mid_element) {
                return true;
            } else if (searchElement < mid_element) {
                last = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        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, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
    Console.WriteLine(m.SearchRowwiseColumnWiseMatrix(mat, 11));
}

실행 결과

TRUE

복잡도 정리

• 선형 검색(전체 요소 스캔): O(M×N)
• 이진 탐색(본문 방식): O(log(M×N))

행렬이 행·열 기준으로 정렬되어 있다는 조건만 만족한다면, 행렬을 1차원 배열로 펴서 이진 탐색을 수행하는 것이 가장 효율적인 선택입니다.