티스토리 뷰

공부

Majority Vote Algorithm

전명우 2016.06.23 13:28

Majority Vote Algorithm은 사람들이 투표를 했을 때 과반의 표를 받은 대상이 있는지, 그 대상은 누구인지 최소 회수의 비교를 통해 밝혀내는 방법이다.

비교라는 것은 check(i, j) 라는 함수 호출을 통해 i번 사람과 j번 사람이 같은 대상에게 표를 던졌는지 확인하는 작업이다. 최소 회수의 비교라는 것은 check(i, j) 루틴을 최소의 회수로 부른다는 것을 의미한다.


두 가지 알고리즘을 소개할 것이다. 두 알고리즘 모두 check(i, j)를 최대 $\lfloor\frac{3}{2}N\rfloor$번 호출한다.

Algorithm 1) Boyer-Moore majority vote algorithm

1번 사람부터 $N$번 사람까지 투표한 상황이 아래와 같다고 하자.

3 1 2 2 1 1 1 1 2 1 3 2 1 1 2


이 때 그룹을 아래와 같이 나눌 수 있다.

3 1 / 2 2 1 1 / 1 1 2 1 3 2 / 1 1 2


각 그룹의 제일 왼쪽에 있는 값을 우두머리라 하자. 그룹에서 그룹의 우두머리와 같은 표 개수와 나머지 표의 수가 같아지도록 나눈다. 하지만 제일 오른쪽 그룹은 위 예제처럼 그룹의 우두머리와 같은 표 개수가 더 많을 수 있다.


그룹을 나누는데 필요한 비교 회수는 그룹의 수가 $G$라고 할 때, $(N-1) - (G-1) = N-G$ 번이다.

만약 과반의 표를 받은 사람이 있다면 그 표를 받은 대상은 제일 오른쪽 그룹의 우두머리의 표를 받은 사람일 것이다. 이를 과반 후보라고 하자.


이제 그 표가 실제로 과반의 표를 받았는지 확인해야한다. 일반적인 방법으로 과반 후보와 나머지 $N-1$개의 표와 비교해본 뒤 과반후보가 실제로 과반 표를 받았는지 확인할 수 있으나 이 때 총 비교 회수가 $2N$이 되어 비효율적이다.


이를 효율적으로 하기 위해서는 우선 제일 오른쪽 그룹을 제외하고, 나머지 그룹의 우두머리의 표와 과반 후보와 비교해본다. 만약 그룹의 우두머리의 표와 과반 후보가 같다면, 그 그룹 내에서는 추가적인 비교가 필요하지 않다. 만약 그룹의 우두머리의 표와 과반 후보가 다르다면, 그룹의 크기가 $s$라 할 때 추가적으로 $\frac{s}{2}$번의 비교를 통해 그룹 내에서 과반 후보가 받은 표의 개수를 셀 수 있다.

최악의 경우, 비교 회수는 $\frac{N}{2} + G - 1$ 번이 되어 총 비교회수 $\frac{3}{2}N - 1$번 안에 해결할 수 있다.

코드 보기

Algorithm 2) 이름 모르는 알고리즘

Algorithm 1 보다는 증명과 설명이 까다로운 알고리즘이다. 우선 인접한 사람들끼리 2인1조로 묶어 표가 같은지 비교한다. 만약 표가 다르다면 합치지 않고, 같다면 둘을 합친다. 이제 크기가 2인 그룹들을 일렬로 나열하고 여기서 인접한 그룹들끼리 2그룹1조로 묶어 표가 같은지 비교한다. 만약 같다면 둘을 합쳐 크기가 4인 그룹으로 만들고 다르다면 합치지 않는다. 이 작업을 계속 반복한다.


이 때, Algorithm 1 처럼 과반 후보를 정할 수 있다. 크기가 $2^k$인 그룹의 개수가 홀수인 가장 큰 $k$에서 일렬로 나열했을 때 제일 오른쪽에 있는 (즉, 2그룹1조로 묶이지 않은) 그룹에서 던진 표가 과반 후보가 된다.


마찬가지로 과반 후보가 실제로 과반 표를 받았는지 확인해주어야한다.

이를 효율적으로 하기 위해서 여태까지 생긴 그룹들과 과반 후보를 비교해주면 된다.


그룹의 개수가 홀수라 비교를 하지 않은 그룹의 개수를 $A$, 비교 했을 때 서로 다른 표라고 나와 합치기에 실패한 회수를 $B$라고 했을 때, 남아있는 총 그룹의 수는 $G = A + 2B$ 다. 그룹을 묶는데 사용한 비교 회수는 최대 $N - A - B$ 이다. 총 비교 회수는 $G - 1 + N - A - B = N + B - 1$인데, 여기서 $B \leq \frac{N}{2}$라는 것을 알 수 있다. 따라서 비교 회수는 최대 $\frac{3}{2}N - 1$이 된다.

코드 보기

저작자 표시
신고

'공부' 카테고리의 다른 글

Divide & Conquer Optimization  (2) 2016.06.23
Knuth Optimization - Dynamic Programming  (2) 2016.06.23
Majority Vote Algorithm  (1) 2016.06.23
Grundy Number  (0) 2014.11.13
Suffix Array와 LCP  (9) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
댓글
댓글쓰기 폼