← 전체 회차
A-029● Day 292026.06.04mediumleetcode #74neetcode150

2D 행렬 검색

#array#binary-search#matrix
↗ leetcode #74 · search-a-2d-matrix
01

문제

· problem
P.029

2D 행렬 검색

↗ leetcode #74

m × n 크기의 정수 행렬이 주어지며, 다음 두 가지 성질을 만족합니다: 각 행은 오름차순으로 정렬되어 있습니다. 각 행의 첫 번째 원소는 이전 행의 마지막 원소보다 큽니다. 정수 target이 주어질 때, target이 행렬에 존재하면 true를, 없으면 false를 반환하세요. O(log(m * n)) 시간 복잡도의 해결책을 작성해야 합니다.

제약
  • · 1 ≤ m, n ≤ 100
  • · Each row sorted in non-decreasing order
  • · First element of each row > last element of previous row
  • · -10⁴ ≤ matrix values, target ≤ 10⁴
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
3
true
example 2input → output
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
13
false
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    이 행렬을 전체적으로 정렬된 1D 배열로 볼 수 있나요?
  • ☐
    왜 O(log(m*n)) 복잡도가 요구되나요?
  • ☐
    왜 matrix[row][0]과 matrix[row][-1]을 비교하는 것이 올바른 행을 찾는 데 도움이 되나요?
  • ☐
    올바른 행을 찾은 후에는 어떻게 하나요?
  • ☐
    확실하게 하려면 모든 행을 확인해야 하나요?
  • ☐
    O(m + n) 시간 복잡도로 간단하게 구현할 수 있으면 괜찮나요?
  • ☐
    각 행을 선형 탐색하는 것이 해결책의 핵심인가요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 행렬 크기 초기화
○
ROWS, COLS = len(matrix), len(matrix[0])
○
ROWS, COLS = len(matrix[0]), len(matrix)
○
ROWS, COLS = len(matrix), len(matrix)
step 2· 행 탐색 범위 설정
○
top, bot = 0, ROWS - 1
○
top, bot = 1, ROWS - 1
○
top, bot = 0, ROWS
step 3· target과 행 경계 비교│ 중첩
○
if target > matrix[row][-1]:
○
if target > matrix[row][0]:
○
if target >= matrix[row][-1]:
step 4· 행 발견 여부 확인
○
if not (top <= bot):
○
if top == bot:
○
if top > bot:
step 5· 행 내 target 검색│ 중첩
○
if target > matrix[row][m]:
○
if target > matrix[row][l]:
○
if target >= matrix[row][m]:
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3
        ROWS, COLS = len(matrix), len(matrix[0])
4
5
        top, bot = 0, ROWS - 1
6
        while top <= bot:
7
            row = (top + bot) // 2
8
            if target > matrix[row][-1]:
9
                top = row + 1
10
            elif target < matrix[row][0]:
11
                bot = row - 1
12
            else:
13
                break
14
15
        if not (top <= bot):
16
            return False
17
        row = (top + bot) // 2
18
        l, r = 0, COLS - 1
19
        while l <= r:
20
            m = (l + r) // 2
21
            if target > matrix[row][m]:
22
                l = m + 1
23
            elif target < matrix[row][m]:
24
                r = m - 1
25
            else:
26
                return True
27
        return False
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
3
→
true
case 2
[[1,3,5,7],[10,11,16,20],[23,30,34,60]]
13
→
false
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.