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

과반수 찾기 알고리즘:

n크기의 배열이 주어지고 그 안에는 n/2보다 많이 중복되는 수 x가 존재한다면,

그 수를 찾는 알고리즘이다.

입력: 

• 정수의 배열 A[n]을 입력으로 받는다
• ex: {1, 1, 2, 5, 3, 5, 1, 3}

출력:

• A[n]에서 n/2번 이상 나오는 원소가 있다면 그 원소를 출력한다.

Brute Force:

• 각 원소마다 자기 뒤에 나오는 횟수를 세어본다.
• worst case: O(n2)

---

Sorting Method:

예시: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2

• 배열을 정렬함 (시간복잡도 = O(n log n))
• 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3
• 하나씩 읽고 바로 직전 원소와 같다면 count해서 n/2보다 큰 경우 return. (시간복잡도 = O(n))

맨 마지막 원소가 답인 경우 worst case.

---

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

예시: 3 1 2 2 1 1 1 1 2 1 3 2 1 1 1 2

동작:

1. 앞에서부터 배열을 읽는다.
2. 맨 처음 나온 원소의 수를 카운트하고 카운트 한 수 만큼 다른 수가 나오면 멈추고 그룹을 나눈다. (같은 수가 나오면 count++)
3. A[n] = 3 1 /2 2 1 1 1 1 2 1 3 2 1 1 1 2
4. 멈춘 지점에서부터 다시 2번을 시행한다.
5. A[n] = 3 1 /2 2 1 1 /1 1 2 1 3 2 1 1 1 2
6. A[n] = 3 1 /2 2 1 1 /1 1 2 1 3 2/ 1 1 1 2
7. 마지막 그룹에서 맨 앞의 수가 과반수이다. (x = 1)

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

• 그래프로 이렇게 표현할 수도 있다.
• 원, 원, 네모, 원, 네모, 별, /별, 네모, /네모, 네모, 원, 네모, 네모, 별, 네모, 네모 

증명:

• *N개의 원소 중에 과반수인 원소가 x라고 할 때.
• 첫번째 원소는 x 이거나 x가 아님.

If 첫번째 원소가 x라면?

• 만약 첫번째 원소가 x라면, 그 그룹에서 x가 나온 횟수만큼 다른 원소들이 그룹에 포함된다.
• 같은 횟수만큼 x와 다른 원소가 제거되므로, 남은 원소 중 과반수 이상이 x이다.

If 첫번째 원소가 x가 아니라면?

• x가 아닌 다른 원소 y가 첫번째 원소라고 하자.
• x가 가장 많이 제거되는 경우는 yyyyxxxx… 같은 경우인데, 이 경우에도 여전히 남은 원소 중 과반수 이상이 x이고 다른 경우에도 마찬가지이다.

---