피드로 돌아가기
Dev.toBackend
원문 읽기
O(N*M log(NM))에서 O(log(Max)*N log M)로의 시간 복잡도 최적화
Median in a Row Wise Sorted Matrix | Binary Search on Answer
AI 요약
Context
Row-wise Sorted Matrix에서 Median을 찾기 위해 모든 요소를 추출하여 정렬하는 Brute Force 방식의 높은 시간 및 공간 복잡도 발생. 행 단위 정렬 상태라는 기하학적 특성을 활용하지 못하는 구조적 한계 존재.
Technical Solution
- Index 탐색이 아닌 Value 범위를 대상으로 하는 Binary Search on Answer 기법 도입
- 특정 값(mid) 이하의 요소 개수가 단조 증가하는 Monotonic 특성을 이용한 탐색 범위 축소
- 각 행에 대해 Upper Bound Binary Search를 수행하여 mid 이하 요소 개수를 O(log M)으로 산출
- 전체 행 N개에 대해 반복 수행하여 총 O(N log M)의 시간으로 mid의 적절성 검증
- 계산된 Count 값과 Median 위치(N*M/2)를 비교하여 search range를 좌우로 조정하는 반복 구조 설계
Impact
- Time Complexity: O(N * M * log(N * M)) → O(log(MaxValue) * N * log M)로 개선
- Space Complexity: O(N * M) → O(1)로 최적화
실천 포인트
1. 정렬된 구조에서 K번째 요소나 Median 탐색 필요 시 Binary Search on Answer 적용 검토
2. 검색 대상이 Index가 아닌 Value 범위이며, 조건 함수가 Monotonic한지 확인
3. 전체 데이터를 메모리에 올리는 대신 Row-level Binary Search를 통한 공간 복잡도 최적화 고려