피드로 돌아가기
Dev.toBackend
원문 읽기
Boyer-Moore 알고리즘을 통한 Space Complexity O(n)에서 O(1)로의 최적화
Leetcode 150 | Day 4: Majority Element - Naive vs. Optimized
AI 요약
Context
배열 내 n/2 초과 빈도를 가진 Majority Element를 탐색하는 문제임. 빈도 측정용 Map을 사용하는 Naive 방식은 데이터 규모 증가에 따라 메모리 사용량이 선형적으로 증가하는 한계점이 존재함.
Technical Solution
- Frequency Map 기반의 2단계 순회 구조를 단일 패스(Single Pass) 구조로 변경
- Boyer-Moore Majority Vote 알고리즘을 도입하여 상태 기반의 후보군 추적 방식 채택
- candidate와 count라는 두 개의 변수만으로 최다 빈도 요소의 생존 여부를 결정하는 로직 설계
- 서로 다른 요소가 나타날 때마다 count를 감소시켜 서로를 상쇄시키는 상쇄 메커니즘 적용
- Majority Element가 반드시 존재한다는 전제 조건을 활용하여 추가 검증 단계 제거
- 추가 자료구조 없이 변수 업데이트만으로 처리하는 Constant Space 설계 구현
실천 포인트
1. 데이터셋의 규모가 메모리 한계를 초과할 가능성이 있는지 검토
2. 해시 맵 기반의 빈도 분석 전, 상쇄(Cancellation)나 포인터 기반의 최적화 알고리즘 적용 가능성 확인
3. 문제 정의에 포함된 전제 조건(Guarantee)이 알고리즘 복잡도를 낮출 수 있는 핵심 단서인지 분석