[Algorithm] Moore's Voting Algorithm

Moore's Voting algorithm은 어떤 배열이 있을 때 과반수 이상 나타나는 원소를 구하는 알고리즘이며 Boyer-Moore majority vote algorithm이라고도 한다.

기본 아이디어

배열 내에 과반 이상을 차지하는 값이 있다면 투표의 마지막에는 해당 원소가 최후의 승자가 될 것이라는 아이디어를 기반으로 고안되었다.

크게 2 단계로 이루어져 있는데,

1. 투표를 통해서 후보를 가려낸다. (후보와 같은 값이면 vote에 1을 더하고 아니면 1을 뺀다.)
2. 실제 해당 후보가 과반 이상 나타났는지 확인한다.

만약 무조건 과반 이상 나타나는 원소가 있다고 가정하면 2번째 단계는 건너뛰어도 된다.

예시#1

철수, 영희, 민수, 은지, 지원 5사람이 저녁 메뉴를 투표를 통해 정하기로 하였다. 과반의 표를 얻는 메뉴가 선정된다.
투표 결과는 다음과 같다.

철수	영희	민수	은지	지원
일식	일식	중식	일식	한식

위의 결과를 보면 일식이 3표로 5/2=2.5 이상을 차지하는 과반의 값이라고 볼 수 있다. 이를 해당 알고리즘을 통해서 순서대로 살펴보자.

1. 철수가 일식에 투표했다. 후보는 일식이며, vote 수는 1이다.
2. 영희가 일식에 투표했다. 후보와 같은 값이기 때문에 vote에 1을 더해 2가 된다.
3. 민수가 중식에 투표했다. 후보가 다른 값이기 때문에 vote에 1을 빼서 1이 된다.
4. 은지가 일식에 투표했다. 후보가 같은 값이기 때문에 vote에 1을 더해 2가 된다.
5. 지원이 한식에 투표했다. 후보가 다른 값이기 때문에 vote에 1을 빼서 1이 된다.

마지막에 후보로 나온 일식이 과반 이상이 나왔을 것이라고 예상한다.
실제로 과반 이상이 나왔는지 확인해보자.

일식	일식	중식	일식	한식
1	2	2	3	3

투표 순서대로 일식일 경우에 count를 1씩 더해준 결과가 위 표에 나타나있다.
최종 일식에 투표한 사람 수가 3이므로 과반(2.5)이므로 일식이 majority element라고 할 수 있다.

예시#2

이번엔 다른 예시를 들어보자.

철수	영희	민수	은지	지원
일식	한식	한식	일식	일식

이번에는 아무도 중식에 투표하지 않았다. 최종적으로 일식이 과반이지만 중간에 한식이 2표가 있다. 처음에는 일식이 후보겠지만 바로 뒤에 한식이 2번 연속으로 오면서 vote가 음수가 될 것이다. 하지만 이 알고리즘은 vote가 0이 되면 바로 후보를 교체한다.

1. 철수가 일식에 투표했다. 후보는 일식이며, vote 수는 1이다.
2. 영희가 한식에 투표했다. 후보가 다른 값이기 때문에 vote에 1을 빼서 0이 된다.
3. 민수가 한식에 투표했다. vote가 0이기 때문에 후보를 한식으로 변경하고 vote를 1로 초기화한다.
4. 은지가 일식에 투표했다. 후보가 다른 값이기 때문에 vote에 1을 빼서 0이 된다.
5. 지원이 일식에 투표했다. vote가 0이기 때문에 후보를 일식으로 변경하고 vote를 1로 초기화한다.

이번에도 마지막에 일식이 후보이고 최종 과반인지 확인해보니 3이므로 메뉴는 일식으로 결정되었다.

일식	한식	한식	일식	일식
1	1	1	2	3

코드

def moore_voting_algorithm():
    nums = [1, 1, 2, 3, 1]
    # 변수 초기화
    candidate = nums[0]
    vote = 0

    for num in nums:
        # vote가 0이면 후보를 교체한다.
        if vote == 0:
            candidate = num
            vote = 1
        else:
            # 현재 값이 후보와 같은 값이면 vote에 1을 더한다.
            if num == candidate:
                vote += 1
            # 현재 값이 후보와 다른 값이면 vote에 1을 뺀다.
            else:
                vote -= 1

    occurrences = 0
    for num in nums:
        if num == candidate:
            occurrences += 1
            
    if occurrences > len(nums)//2:
        print(f"{candidate}은 과반을 획득했습니다.")
    else:
        print("과반을 획득한 원소는 없습니다.")