m x n 크기의 행렬에서 특정 값을 빠르게 찾는 효율적인 알고리즘을 작성해야 한다고 가정해 봅시다. 이 행렬은 다음과 같은 중요한 특성을 가지고 있습니다.
- 각 행은 왼쪽에서 오른쪽 방향으로 오름차순 정렬되어 있습니다.
- 각 행의 첫 번째 숫자는 항상 이전 행의 마지막 정수보다 큽니다.
즉, 행렬 전체를 왼쪽 위에서 오른쪽 아래까지 순서대로 읽으면 하나의 정렬된 배열처럼 동작하는 구조입니다. 예를 들어 행렬이 다음과 같다고 해 보겠습니다.
| 1 | 3 | 5 | 7 |
| 10 | 11 | 16 | 20 |
| 23 | 30 | 34 | 50 |
| 53 | 62 | 78 | 98 |
이때 찾으려는 목표 값(target)이 16이라면, 해당 값이 행렬 안에 존재하므로 결과는 참(True), 즉 1이 됩니다.
알고리즘 접근 방식
핵심 아이디어는 이진 탐색(Binary Search)을 두 단계에 걸쳐 적용하는 것입니다. 먼저 목표 값이 속할 수 있는 행을 찾고, 그다음 해당 행 내부에서 실제 값의 위치를 탐색합니다. 이렇게 하면 전체 시간 복잡도를 O(log n + log m), 즉 O(log(mn))으로 줄일 수 있습니다.
단계별 절차
- n := 행의 개수로 설정하고, n이 0이면 false를 반환합니다. 마찬가지로 m := 열의 개수로 설정하고, m이 0이면 false를 반환합니다.
- low := 0, high := n - 1로 초기화합니다.
- low < high인 동안 다음을 반복합니다.
- mid := low + (high - low + 1) / 2 로 계산합니다.
- mat[mid][0] <= target이면 low := mid로 갱신하고, 그렇지 않으면 high := mid - 1로 갱신합니다.
- rlow := 0, rhigh := m - 1, ans := 0으로 초기화합니다.
- rlow <= rhigh인 동안 다음을 반복합니다.
- mid := rlow + (rhigh - rlow) / 2 로 계산합니다.
- mat[low][mid] == target이면 ans := 1로 설정한 뒤 루프를 종료합니다.
- matrix[low][mid] < target이면 rlow := mid + 1로 갱신합니다.
- 그 외의 경우에는 rhigh := mid - 1로 갱신합니다.
- 최종적으로 ans를 반환합니다.
C++ 구현 예제
위 알고리즘을 더 잘 이해하기 위해 다음 C++ 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
lli n,m;
n = matrix.size();
if(!n)return false;
m = matrix[0].size();
if(!m)return false;
lli low = 0, high = n-1;
while(low<high){
lli mid = low + ( high - low +1)/2;
if(matrix[mid][0]<=target)low = mid;
else high = mid -1;
}
lli rlow = 0, rhigh = m-1;
lli ans = 0;
while(rlow<=rhigh){
lli mid = rlow+(rhigh - rlow)/2;
if(matrix[low][mid] == target){
ans =1;
break;
}else if(matrix[low][mid]<target)rlow=mid+1;
else rhigh= mid-1;
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,3,5,7},{10,11,16,20},{23,30,34,50},{53,62,78,98}};
cout << ob.searchMatrix(v, 16);
}입력
[[1,3,5,7],[10,11,16,20],[23,30,34,50],[53,62,78,98]] 16
출력
1
정리
이 알고리즘은 첫 번째 이진 탐색으로 목표 값이 존재할 가능성이 있는 행을 좁히고, 두 번째 이진 탐색으로 그 행 안에서 값을 정확히 찾아냅니다. 덕분에 모든 원소를 하나씩 확인하는 O(nm) 방식보다 훨씬 효율적이며, 대규모 정렬된 행렬에서도 빠른 검색 성능을 보장합니다.