Boyer–Moore Majority Vote

우연찮게 본 Boyer-Moore majority vote 알고리즘에 대해 알아보려고 한다.

Boyer-Moore는 사람 이름이라 제외하고 Majority vote만 보면, 말 그대로 가반수 값을 찾는 알고리즘이다.

때문에 단순히 input 데이터 중 반복되는 값이 많은 것을 찾는 것이다.

그림 1. Boyer-Moore Majority Vote

그림 1을 보면 좀더 확실하게 알 수 있다. X축 밑에 그림이 각 순차적인 인덱스 별로 나오는 값이고 Y축 값은 Majority 값의 개수를 나타낸다.

그래서 맨 처음 0으로 시작하다 마지막엔 빨간색 네모가 카운트 4까지 위치하는 것을 볼 수 있다. 결과적으로 빨간색 네모가 해당 input 데이터 중 가반수를 차지한다는 의미이다.

이처럼 가반수의 값이 무엇인지 쉽게 찾을 수 있으나 문제는 반복되는 값이 별로 없다면 해당 알고리즘은 무의미하다.

예를 들어,

[1,1,1,2,2] 일 때, 가반수 값은 1이다.

[1,1,0,2,2] 일 때, 가반수 값은 1 인 것인가? 2인 것인가?

때문에 해당 알고리즘을 적용할 때 위의 문제점을 항상 고려하고 있어야 한다.

관련 코드를 보면.

for num in nums: if count == 0: candidate = num        count += (1 if num == candidate else -1)

코드는 간단하다. input 값의 첫 번째부터 차례 대로 같으면 +1, 다르면 -1을 하고 카운트가 0이면 새로운 값으로 변경한다. 그리고 처음 과정을 계속 반복한다.

해당 알고리즘의 시간 복잡도는 O(n)이다. (input 데이터를 다 훑기 때문에) 그리고 공간 복잡도는 O(1)이다.

Reference

- https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm