Boyer–Moore Majority Voting: 왜 작동하고, 왜 실패하며, 실제로 어디에 속하는가

Source: Dev.to

번역할 텍스트를 제공해 주시면, 해당 내용을 한국어로 번역해 드리겠습니다.

소개

Boyer–Moore 다수 투표 알고리즘은 종종 영리한 트릭으로 소개됩니다:

O(1) 공간에서 다수 요소를 찾는다.

그 진술은 기술적으로는 맞지만 실제로는 오해를 불러일으킬 수 있습니다. 이 글에서는 제가 따라온 추론 과정을 문서화합니다—신뢰할 수 있는 정확한 카운팅 접근법에서부터 정확한 답이 아닌 신뢰 기반 우위 신호까지. 탐구는 LeetCode 문제로 시작했으며 시스템 설계 질문으로 발전했습니다.

다수 원소 기본

주어진 원소들의 시퀀스에서 다수 원소는 ⌊n/2⌋ 번보다 더 많이 나타납니다.

• 중요한 제약 조건
  • 다수 원소가 존재할 수도 있고 존재하지 않을 수도 있습니다.
  • 다수 원소가 존재한다면, 그것은 유일합니다.

정확한 카운팅 (HashMap)

• 시간: O(n)
• 공간: O(k) 여기서 k는 서로 다른 요소의 개수입니다.

정확한 카운트는 카운트를 적절한 구조(시간 버킷, 필터 가능한 필드 버킷)와 함께 저장하면 임의의 필터링(시간 범위, 태그, 속성)을 허용합니다. 추가 검증 단계가 필요 없지만, 후보의 카디널리티가 커짐에 따라 메모리 사용량이 증가합니다—이는 큰 또는 알 수 없는 도메인을 가진 스트리밍 시스템에서 무제한 요구사항이 될 수 있습니다.

Boyer–Moore 다수 투표

알고리즘

1. candidate와 counter를 유지한다.
2. 각 원소에 대해:
   • counter가 0이면, candidate를 현재 원소로 설정한다.
   • 현재 원소가 candidate와 같으면, counter를 증가시킨다.
   • 그렇지 않으면, counter를 감소시킨다.
3. 첫 번째 탐색이 끝난 후, 두 번째 탐색에서 후보의 등장 횟수를 세어 검증한다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)

다수 원소가 존재한다면, Boyer–Moore는 최종 후보로 그것을 반환한다. 그러나 이 알고리즘은 다음을 보장하지 않는다:

• 다수가 존재한다는 것.
• 검증 없이 반환된 후보가 실제 다수라는 것.

검증 (두 번째 탐색)

count = 0
for each element:
    if element == candidate:
        count += 1
if count > n/2:
    return candidate   // 실제 다수
else:
    return None        // 다수 없음

이 검증 단계가 없으면 알고리즘이 잘못된 다수를 반환할 수 있으며, 정확성이 보장되지 않는다.

왜 그냥 HashMap을 사용하지 않을까?

두 번째 순회와 영구 데이터가 어쨌든 필요하다면, 명백한 반론은 다음과 같습니다:

왜 그냥 HashMap을 사용하지 않나요?

이 반론은 타당합니다. 알고리즘을 선택하기 전에, 도구가 아니라 문제 영역을 설명하는 것이 도움이 됩니다.

Boyer–Moore가 빛나는 도메인

시스템이 다음과 같은 경우를 고려합니다:

• 연속적인 이벤트 스트림
• 높은 카디널리티 식별자
• 잠재적으로 무한한 입력
• 고정된 메모리 예산

전형적인 예시:

• 모니터링 및 알림 파이프라인
• 이벤트 수집 레이어
• 악용 또는 이상 탐지 시스템
• 로드‑셰딩 및 백‑프레셔 메커니즘

이러한 상황에서 목표는 정확한 카운트를 계산하는 것이 아니라 다음과 같은 질문에 답하는 경우가 많습니다:

“시스템을 현재 지배하고 있는 것이 있나요?”

시간 창(예: 시간 단위)마다 수백만 개의 이벤트가 처리되고, 이벤트 유형은 무한히 다양합니다. 메모리 사용량은 안정적으로 유지되어야 합니다.

HashMaps는 카디널리티가 폭발하기 전까지는 문제를 완벽히 해결합니다. Boyer–Moore는 상수 공간 때문에 매력적이지만, 후보를 매 창마다 단순히 내보내면 잡음이 많고 오탐이 발생해 알림 피로도가 높아집니다.

카운터를 신뢰 신호로 해석하기

핵심 통찰은 counter가 빈도가 아니라 지배 마진이라는 점입니다—즉, 후보가 얼마나 강하게 취소에 저항했는지를 나타냅니다. 정확한 카운트가 없어도 이 정보는 의미가 있습니다.

신호 구성

• 무작위 데이터 → 신뢰도는 0에 가깝다.
• 지배적인 데이터 → 신뢰도가 증가한다.
• 후보가 자주 바뀜 → 신뢰도가 낮다.
• 후보가 지속됨 → 신뢰도가 높아진다.
• 카운터가 진동 → 잡음.
• 카운터가 증가 → 지배가 부상하고 있다.

결정은 존속성과 성장에 기반하며, 단순 존재 여부에 기반하지 않습니다.

적합한 적용 분야

• 스트리밍 알림 시스템
• 백‑프레셔 탐지
• 이상 또는 악용 신호
• 메모리 제한이 있는 수집 경로

부적합한 적용 분야

• 보고서 작성
• 히스토리 분석
• 컴플라이언스 또는 청구

---

Source: (원본 링크는 그대로 유지)

Misra–Gries와의 관계

Boyer–Moore는 k = 2인 Misra–Gries 알고리즘의 특수한 경우로 볼 수 있습니다. Misra–Gries는 이 아이디어를 일반화합니다:

• 여러 후보를 추적합니다.
• 여전히 메모리를 제한합니다.
• 정밀도와 범위 사이의 트레이드오프를 합니다.

Misra–Gries를 탐구하는 것은 더 깊은 조사에 자연스러운 다음 단계입니다.

탐구의 기원

조사는 LeetCode 문제에서 시작되었습니다:

Majority Element II

문제를 푸는 것은 쉬웠지만, 알고리즘이 의미를 갖는 부분을 이해하는 것은 쉽지 않았습니다.

요약

• Boyer–Moore는 정확한 카운팅 알고리즘이 아니다.
• 이것은 제한된 메모리 우세 신호이다.
• 이렇게 사용하면 정당화될 수 있다.
• 다른 용도로 사용하면 오해를 불러일으킨다.

그 구분이 바로 이 게시물의 전체 요점이다.