Boyer-Moore 과반수 투표 알고리즘
General / Algorithms

Boyer-Moore 과반수 투표 알고리즘

Boyer-Moore 과반수 투표 알고리즘(majority vote algorithm)[1]은 배열에 포함된 원소들 중 절반 이상 포함된 원소를 linear time 과 constant space 로 찾을 수 있는 알고리즘이다.

참고로 Boyer–Moore 문자열 검색 알고리즘(string-search algorithm)과는 다르므로 헷갈리지 말자.

보이어 무어 과반수 투표 알고리즘은 스트리밍 알고리즘(streaming algorithm)의 대표적인 예다.

만약 배열 내 과반수(절반이 넘는 수)에 해당하는 원소가 존재한다는 보장이 된다면, 결과값은 항상 과반수 원소가 된다.

주의할 점은, 만약 배열 내에 과반수 만큼 등장하는 원소가 없다면 결과값으로 임의의 의미없는 값이 나오게 된다(딱 절반 만큼 등장하는 원소가 있더라도 마찬가지다)

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

동작 방식

  • major 와 count 를 0 으로 초기화 한다.
  • 배열의 각각의 원소 x에 대해
    • if count = 0, major = x, count = 1 대입
    • else if major = x, count = count + 1
    • else, count = count - 1
  • major 를 반환
    • 만약 딱 절반 만큼 존재하는 원소

위의 로직을 그림으로 나타내면 다음과 같다.

출처: https://en.wikipedia.org/wiki/File:Boyer-Moore_MJRTY.svg

X축에 있는 도형이 배열에 있는 원소이고, Y축에 있는 숫자가 count 값이며, 꺾은선 그래프 위에 있는 도형이 현재 major 변수에 들어있는 원소다.

증명

우선, 과반수 원소가 있을 때 위 로직대로 수행하면 결과값이 항상 과반수 원소가 된다는 것을 증명해보겠다.

뭔가 직관적으로 당연한것 같으면서도 애매한 분들을 위해 쉬운 비유를 하나 들어보겠다.

하나의 성을 차지하기 위해 여러 나라가 전투를 벌인다. 여러 나라에서 온 병사들은 일렬로 줄을 서 있고, 한 명씩 차례대로 성을 향해서 돌진한다.

만약 성에 아무도 없다면 바로 성을 함락하여 성의 주인이 된다. 성에 누군가가 있다면 2가지 케이스로 나뉜다.

성에 있는 사람이 나와 같은 나라 사람이면 성에 합류하고, 다른 나라 사람이면 싸워서 성에 있는 병사 한 명과 동반 자살(?)한다.

즉, 성에 있는 사람 수를 1만큼 감소시키는 동시에 자기 자신 또한 사라진다.

어떤 나라가 성을 함락하는 순간 다른 모든 나라는 같은 팀이나 다름없다. 왜냐하면 모두 성을 향해서만 공격하기 때문에 성을 함락한 나라의 병사 숫자가 집중적으로 감소하기 때문이다.

모든 병사가 돌진한 뒤에도 성에 병사가 남아있다면 그 병사의 나라가 최종적으로 성의 주인이 된다. 만약 성에 아무도 남지 않는다면 마지막으로 성을 소유했던 나라가 성의 주인이 된다.

결국 위의 동작 방식에서 얘기한 major 변수가 성이고, count 변수가 성에 있는 병사의 수이며, 배열의 각 원소는 병사, 원소의 값 x는 각 병사가 속한 나라이다.

그리고 결과값이 나타내는 것은 최종적으로 성의 주인이 되는 나라이다.

만약 병사의 숫자가 과반수에 해당하는 나라가 있다면 이 나라에게 최악의 경우는 처음부터 성을 함락하여 다른 모든 나라가 동맹을 맺어 성을 향해 돌진하게 되는 상황이다.

하지만 어차피 과반수 나라는 적어도 최후의 1인은 살아남아 성의 주인으로 남을 것이다.

만약 다른 나라가 성을 함락한 적이 있다면, 오히려 이득이다. 과반수가 아닌 다른 나라끼리 싸워서 자신들의 병사들을 비축시킬 수도 있기 때문이다.

그렇기 때문에 과반에 해당하는 원소가 있을 경우, 앞서 언급한 로직대로 수행하면 무조건 결과값으로 세팅되는 것이다.

하지만 과반에 해당하는 나라가 없다면 어떤 나라가 먼저 성을 함락하느냐에 따라 성의 최종 주인이 달라지게 되므로, 앞선 로직의 결과값은 의미가 없다.

다음으로, 과반수 원소가 없을 때 정확히 절반 만큼 존재하는 원소가 있으면 결과값이 해당 원소가 될 듯한 느낌도 드는데, 아니라는 것을 반례를 들어 증명하겠다.

만약 주어진 배열이 [1, 1, 1, 2, 3, 3] 이라면 결과값이 1이 되지만, 같은 구성에 순서만 바꾼 [2, 1, 1, 3, 3, 1] 이라면 결과값이 3이 된다.

소스 코드

알고리즘의 로직 자체가 단순하기 때문에 소스코드 또한 굉장히 간단하다.

다음은 C++ 로 보이어 무어 과반수 투표 알고리즘을 구현한 코드이다.

int findMajority(vector<int>& arr) {
    int count = 0;
    int major = 0;
    for (int num : arr) {
        if (count == 0) major = num;
        if (major == num) count++;
        else count--;
    }
    return major;
}

예제

LeetCode 1157. Online Majority Element In Subarray
풀이

  1. https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm ↩︎

#

Comments

×