과반수 원소 알고리즘

Majority Element / Majority Vote Algorithm

주어진 리스트에서 과반수를 차지하는 원소의 존재성 판정과, 존재 시 과반수 원소를 구하는 알고리즘.

A[] = { 1, 3, 1, 1, 2}

리스트 A에서 과반수 원소는 1이다. 

 

정렬하면 슥삭 풀리는 문제이지만 O(N) 시간복잡도에 가능한 알고리즘이 존재한다.

 

O(N) Solution

내가 소개할 것 : Pair 매칭 알고리즘. 

*기존 길이 $n$ 리스트 A로부터 길이 $[n/2]$ 리스트 B를 만든다.

 

N이 짝수일 때 : 

앞에서부터 차례대로 2개씩 묶는다. 

각각의 pair (x,y)에 대해 x==y면 하나만 남기고, x!=y면 둘 다 제거한다.

A[]={1,3,1,1,2,1} 을 예시로 들자면 (1,3) => (), (1,1)=>(1), (2,1)=>()이다. B[]={1}이 된다.

 

N이 홀수일 때 : 

마지막 원소가 과반수 원소인지 검사한다. 맞다면 알고리즘 종료. 아니라면 그 원소를 제거하고 N이 짝수인 경우로 넘어간다.

 

리스트의 원소의 개수가 1이 될 때까지 위 시행을 반복한다. 마지막으로 남은 원소가 과반수 원소라면 알고리즘 종류. 아니라

 

꽤 신박한 방법이다.  정당성과 시간 복잡도의 핵심적인 증명을 해보겠다.

 

원소의 개수가 N이며, 과반수 원소가 존재하는 리스트 A를 생각하자.

정당성

Claim : 원소 X가 A의 과반수 원소라면 X는 A를 변형한 B의 과반수 원소다.

일반성을 잃지 않고 N이 짝수라 가정하자. A의 인접한 원소끼리 묶어 만든 pair의 개수는 N/2이다

과반수 원소를 X, X의 개수를 d라 하자. pair 중 X만으로 이루어진 것들의 개수를 c라 하자.

같은 원소로 이루어진 pair은 B에서 한 원소만 남으므로, B에 있는 X의 개수는 c이다.

 

X 중 X만으로 이루어진 pair에 속하지 않는 것들의 개수는 무엇일까? d - c*2가 될것이다. 이 X들은 전부 자신과 다른 수와 pair을 이루고 있다.

이제 남은 pair들을 살펴보자. pair 중에서 X가 속하지 않은 pair의 개수는 N/2 - c - (d-c*2)가 된다.

 

이 사실들을 종합해보면,

B의 원소의 개수는 pair 중 같은 원소로 이루어진 것들의 수 이므로 

(X가 속한 같은 원소 pair의 수) + (X가 속하지 않은 같은 원소 pair의 수)이다.

(X가 속하지 않은 같은 원소 pair의 수) <= (X가 속하지 않은 pair의 수)이므로

 

(B의 원소의 개수) <= (X가 속한 같은 원소 pair의 수) + (X가 속하지 않은 pair의 수) = c +N/2 - c - (d-c*2)

이때 X는 과반수 원소이므로 d>N/2이다.

즉 N/2 - d < 0

(B의 원소의 개수) < 2*c이다.

위에서 B에 있는 X의 개수가 c라고 했으므로 

(B의 원소의 개수) /2 < (B에 있는 X의 개수) 가 되어 X는 B의 과반수 원소이다.

 

고로 Claim이 증명되었다. 리스트 변형을 반복하여도 과반수 원소는 변하지 않는다.

 

시간복잡도

시행을 한 번 할 때마다 리스트의 길이가 절반 이상 감소한다.

한 시행 당 원소 검사 횟수는 O(리스트의 길이)이다.

 

즉 총 시간 복잡도는 O(N + N/2 + N/4 + N/8 + ... ) = O(2*N) = O(N)이다.

 

이 사실은 T(N) = T(N/2) + N에서 마스터 정리로 엄밀하게 증명할 수 있다.

 

T(n) = a * T(n/b) + f(n) ; h(n) = n^log_b(a)

여기서 a = 1, b = 2, f(n) = n, h(n) = n^log2(1) = 1이다.

 

f(n)이 h(n)이 압도하므로 T(n) = O(f(n)) = O(n)이다.

 

(만약 h(n)이 f(n)을 압도한다면 T(n) = O(h(n)), lim n -> inf {f(n) / h(n)} = 1이라면 T(n) = O(f(n)log n)이다. )

 

 

그 외 다양한 알고리즘

https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations

 

인상적인 O(N) 알고리즘들.

*과반수 원소가 존재하는 리스트에서 적용.

nth_element(n/2) => n/2번째 작은 수는 무조건 과반수 원소다.

보이어-무어 과반수 투표 알고리즘 => 한 번의 스캔으로 과반수 원소를 결정한다.

비트 알고리즘: 1<<0 부터 1LL<<31까지 쭉 훑으면서 해당 bit가 리스트의 각 element와 &연산을 했을 때 0이 아니라면 count를 해준다. 과반 이상의 원소에 대하여 이 bit가 해당이 된다면 ans에 |= 연산을 한다.  모든 loop가 끝났을 때 ans에 답이 저장되어 있다.

어떤 bit에 대하여 이 bit이 과반수 원소에 포함되어 있다면 과반에 해당이 되고, 포함되어 있지 않다면 과반에 해당하지 않을 것이므로 이 알고리즘이 성립한다.