[Algorithm] Boyer-Moore majority vote algorithm (보이어 무어 과반수 투표 알고리즘)

gunny·2023년 6월 5일

Boyer Moore Algorithm majority vote algorithm 보이어 무어 과반수 투표 알고리즘 보이어 무어 알고리즘

Algorithm

목록 보기

4/7

(1) Boyer-Moore majority vote algorithm (보이어-무어 과반수 투표 알고리즘)

Boyer-Moore Majority vote algorithm, 보이어 무어의 과반수 투표 알고리즘은 배열에 포함된 원소들 중 절반 이상 포함된 원소를 linear time과 constant space로 찾을 수 있는 알고리즘임

-Boyer-Moore 문자열 검색 알고리즘(string-search algorithm) 과는 다른 알고리즘임..
(ㅡㅡ.. 삽질하고 있었네 보이어 모어 문자열 검색 알고리즘 보면서 두시간 날리고 있었음 재밌다 하하하)

보이어 무어 과반수 투표 알고리즘은 스트리밍 알고리즘(Streaming algorithm)의 대표적인 예임
배열 내 과반수(절반이 넘는 수)에 해당하는 원소가 존재한다는 보장이 된다면, 결과값은 항상 과반수 원소가 된다.
그러나 네버더레스, 만약 배열 내에 과반수 만큼 등장하는 원소가 없다면 결과값으로 임의의 의미없는 값이 나오게 됨(딱 절반 만큼 등장하는 원소가 있어도 마찬가지라고 함)

=> 즉, 과반수 만큼 등장하는 원소가 있다는 보장이 없으면 결과값이 항상 과반수에 해당하는 원소라는 보장이 없다!!!!!!!!!!

과반수 후보를 가려내는 방법 중 브루트 포스(brute force) 와 map(python에서의 dictionary) 보다 시간복잡도, 공간 복잡도 면에서 유리함

(2) Boyer-Moore majority vote Algorithm 구현

이 알고리즘은 '과반수 원소가 될 수 있는 후보를 골라내는 부분' 과 '그 후보가 실제로 과반수 원소 인지 확인하는 부분' 으로 나누어진다.
처음에 과반수가 될 수 있는 후보를 저장하는 'major' 변수와, 이 'major'가 몇 번 등장했는지 알려주는 'count' 변수가 필요함
배열을 for문으로 순회하면서 배열의 원소가 major와 같으면 count 변수를 +1 해주고, 그렇지 않다면 count 변수를 -1 해줌
count 변수가 0이 되는 경우는 major 변수가 실질적으로 0번 등장했으므로, 이때는 major이라는 변수를 현재 순회하고 있는 배열의 원소로 교체하는 후보 교체가 발생함

step 1. major와 count를 0으로 초기화함
step 2. 배열의 각각 원소에 대해
if count =0, major = x, count =1
else if major=x, count =count+1
else count = count-1

step 3. major를 return

python 구현

def Boyer_moore_majority(arr):
    count, major = 0, 0
    for a in arr:
        if count==0:
            major = a
        if major==a:
            count+=1
        else:
            count-=1
            
    k = len(arr)
    m = 0
    
    for a in arr:
        if a==major:
            m+=1
    if m>k//2:
        return major, m
    else:
        return None, None

(3) Boyer-Moore majority vote 예시

보이어-무어 과반수 투표 알고리즘을 설명할 때 가장 많이 나오는 그림

총 16개의 원소가 있고, 동그라미, 네모, 별표 원소가 주어져있음. 여기서의 과반수는 9개를 가진 네모임
for 문을 돌면서 배열의 원소를 확인해서 과반수인 네모가 return 됨

but, 10개의 원소가 있을 때

동그라미, 네모, 별표 중에서 네모는 5개로 총 10개의 원소 중 과반수를 넘지 않지만 count 가 2로 네모를 리턴하게 될 수 있다.
이 상황에서 보듯이 major는 언제나 과반수 원소가 될 수 있는 '후보' 이지, 과반수 원소가 아닐 수 있다.
그래서 이 원소가 과반수 원소인지 아닌지 체크하는 major가 몇 번 등장했느냐 라는 변수 하나가 더 필요함 이를 'm'으로 나타낸다.

이후 배열의 원소들을 for문으로 확인하면서 배열의 원소가 major와 같으면 m에 +1 을 해주고, m이 배열의 길이의 절반보다 큰지 확인한다.