Boyer–Moore 과반수 투표 알고리즘: 후보 하나와 카운터로 과반 찾기, 두 번째 패스가 필요한 이유

n개의 값 중 절반보다 많이 나온 값이 있는지, 있다면 무엇인지 알고 싶다고 합시다. 투표에서 과반 득표자를 찾는 문제이고, 배열에서 “과반 원소(majority element)“를 찾는 문제이기도 합니다. 여기서 과반은 정확히 n/2보다 많다는 뜻입니다. 13표 중 7표는 과반이고, 12표 중 6표는 과반이 아닙니다.

Robert S. Boyer와 J Strother Moore는 이 문제를 값 하나와 카운터 하나로 푸는 알고리즘을 1980년에 고안했고, 논문에서는 MJRTY라고 불렀습니다. 흔히 Boyer–Moore 과반수 투표 알고리즘(majority vote algorithm)이라고 합니다. 이 글은 두 저자의 1991년 논문 “MJRTY—A Fast Majority Vote Algorithm”(Bledsoe 기념 논문집 Automated Reasoning, 105–117쪽, 저자가 공개한 PostScript 사본)과 Moore가 공개한 설명 페이지를 기준으로 씁니다. 논문 후반의 Fortran 검증 시스템 세부 내용과, 이 알고리즘을 일반화한 후속 연구의 내용은 다루지 않습니다.

흔한 방법과 그 비용

논문은 먼저 뻔한 방법을 짚습니다. 표를 한 번 훑으면서 후보마다 득표수를 따로 세는 것입니다. 후보 수가 고정되어 있으면 이 방법은 n에 비례하는 시간에 끝납니다. 후보 수가 정해져 있지 않으면 사정이 다릅니다. 누적 득표를 저장하고 찾는 비용 때문에 실행 시간이 표의 수에 대해 선형보다 나빠질 수 있고, 논문은 n²에 비례할 수도 있다고 적습니다.

값을 정렬할 수 있다면 다른 길도 있습니다. 선형 시간 선택 알고리즘으로 중앙값을 찾고, 그 중앙값이 절반보다 많은 표를 받았는지 확인하는 방법입니다. 과반 원소가 있다면 정렬했을 때 반드시 가운데를 차지하기 때문입니다(이 이유는 이 글의 설명입니다). 논문은 이때 쓰는 Rivest–Tarjan 알고리즘의 비교 횟수 상한을 n > 32일 때 5.43n − 163으로 인용합니다. 이런 선형 시간 선택은 중앙값의 중앙값(BFPRT) 글에서 다뤘습니다.

MJRTY는 비교를 많아야 2n번 합니다. 그리고 값 사이의 대소 관계가 필요 없습니다. 논문의 표현대로 “같은가”만 비교합니다.

규칙은 두 줄이다

알고리즘은 값을 앞에서부터 하나씩 보면서 현재 후보(candidate)와 카운터 한 쌍을 유지합니다. 처음에는 후보가 정해져 있지 않고 카운터는 0입니다. 원소 e를 볼 때마다 다음을 합니다.

카운터가 0이면 후보를 e로 바꾸고 카운터를 1로 둡니다.
카운터가 0이 아니면, e가 현재 후보와 같을 때 카운터를 1 늘리고 다를 때 1 줄입니다.

끝까지 보고 난 뒤 남은 후보가, 과반 원소가 있다면 바로 그 원소입니다. “있다면”이라는 조건이 이 알고리즘에서 가장 중요한 부분이고, 뒤에서 따로 다룹니다.

논문은 이 과정을 전당대회장의 몸싸움에 빗댑니다. 대의원마다 지지 후보의 이름이 적힌 팻말을 들고 있고, 서로 다른 후보를 지지하는 두 사람이 마주치면 동시에 쓰러진다고 합시다. 어떤 후보의 지지자가 나머지 전부를 합친 것보다 많다면 마지막까지 서 있는 사람은 그 후보 지지자뿐입니다. 과반이 없으면 서 있는 사람이 있더라도 그들이 지지하는 후보가 과반이라는 보장은 없습니다. 그래서 의장은 남은 후보의 팻말을, 쓰러진 사람이 든 것까지 포함해 다시 세어야 합니다.

논문은 그래서 알고리즘을 두 부분으로 나눕니다. 서로 다른 표를 짝지어 지우는 “짝짓기(pairing) 단계”와, 남은 후보가 실제로 절반보다 많은 표를 받았는지 세는 “세기(counting) 단계”입니다. 논문은 짝짓기를 n번의 비교로 할 수 있고, 세기 단계도 많아야 n번의 비교가 든다고 설명합니다.

예제로 따라가기

Moore의 설명 페이지와 논문이 같이 쓰는 예제는 13개짜리 수열입니다.

A A A C C B B C C C B C C

각 원소를 본 직후의 상태를 “후보:카운터”로 적으면 설명 페이지의 단계별 그림과 같습니다. 카운터가 0이면 후보가 없다는 뜻으로 ?를 씁니다.

순서	원소	상태
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

논문의 해설대로 읽으면, 4–6번째 원소(C 두 개와 B 하나)가 앞의 A 세 표를 상쇄해 카운터가 0이 되고, 7번째 B가 잠깐 앞서다가 8번째 C에 지워집니다. 이후 C가 앞서 나가 C:3으로 끝납니다. 이 수열에서 C는 13개 중 7개라서(직접 센 값입니다) 실제로 과반입니다.

마지막 카운터 3이 C의 득표수는 아니라는 점에 주의하세요. 카운터는 짝지어지지 않고 남은 C 표의 수입니다.

왜 맞는가

논문의 증명은 다음 불변식에 기댑니다. i번째 원소까지 처리한 뒤, 지금까지 본 원소는 두 무리로 나눌 수 있습니다.

후보 cand를 지지하는 k개(k는 현재 카운터)
서로 다른 값끼리 둘씩 짝지을 수 있는 나머지

이 불변식이 끝까지 유지되면 결론이 나옵니다. cand가 아닌 어떤 값 x가 n/2보다 많은 표를 받았다고 가정합시다. 둘째 무리는 서로 다른 값끼리 짝지어지므로 x는 그 무리에서 많아야 (n − k)/2표를 가집니다. 그러면 x가 n/2를 넘으려면 첫째 무리에서도 표를 받아야 하는데, 첫째 무리는 전부 cand의 표입니다. 모순이므로, 과반 원소가 있다면 그것은 cand입니다.

불변식 자체는 i에 대한 귀납법으로 보입니다. 논문의 경우 나눔을 요약하면 이렇습니다.

카운터가 0일 때 새 원소를 보면, 지금까지의 원소는 모두 짝지어진 무리에 들어 있으므로 새 원소 하나만으로 첫째 무리를 새로 만듭니다.
새 원소가 cand와 같으면 첫째 무리에 더합니다.
새 원소가 cand와 다르면 첫째 무리에서 하나를 꺼내 새 원소와 짝지어 둘째 무리로 옮깁니다.

과반이 없으면 틀린 답이 나온다

알고리즘은 과반이 없는 입력에도 후보를 하나 내놓습니다. Moore의 설명 페이지는 위 예제에서 첫 번째 C를 A로 바꿔 보라고 합니다.

A A A A C B B C C C B C C

이 수열을 같은 규칙으로 따라가면 역시 C:3으로 끝납니다. 그런데 이제 C는 13개 중 6개이고 A는 4개, B는 3개입니다(직접 센 값입니다). 과반 원소가 없는데 후보는 C입니다.

논문에는 더 짧은 예도 있습니다. A A A B B B C에서는 A와 B가 서로 상쇄되고, 마지막 C가 “부전승”으로 후보가 되어 C:1로 끝납니다. 논문은 표를 다른 순서로 처리했다면 A나 B가 이겼을 수도 있다고 덧붙입니다. 과반이 없을 때 남는 후보는 입력 순서에 달린 값이라 그 자체로는 의미가 없습니다.

두 번째 패스는 언제 생략할 수 있나

과반이 있다고 확인해야 한다면 데이터를 한 번 더 훑어 후보의 실제 개수를 세야 합니다. Moore의 설명 페이지도 이 점을 분명히 적습니다. 과반이 있다는 사실을 알고 있거나 그렇게 가정할 수 있는 경우에만 이 패스를 뺄 수 있습니다.

논문이 드는 예는 SIFT 항공기 제어 시스템입니다. 중복 프로세서와 소프트웨어 투표로 신뢰성을 얻는 시스템인데, 개별 프로세서의 고장률이 충분히 낮아서 한 비행 동안 정상 프로세서의 과반이 매 투표에 합의한다고 가정할 수 있다고 합니다. 이렇게 과반을 가정할 수 있으면 세기 단계를 없앨 수 있고, 논문은 그러면 표를 모아 두었다가 일괄 처리하는 대신 실시간으로 처리할 수도 있다고 적습니다.

그 외에 논문의 Fortran 구현에는 작은 개선이 하나 들어 있습니다.

짝짓기 단계가 끝났을 때 카운터가 0이면 과반이 없다고 바로 답합니다.
카운터 k가 n/2보다 크면 세기 단계 없이 cand를 과반으로 발표합니다. cand의 표가 적어도 k개 있기 때문입니다.

논문은 같은 검사를 첫 루프에서 카운터를 늘릴 때마다 하면 두 번째 패스를 피하는 경우가 생기지만, 그게 실행 시간을 줄이는지는 표의 분포에 달렸다고 말합니다. 그리고 첫 단계를 고쳐서 두 번째 단계를 아예 없애는 방법은 찾지 못했다고 밝힙니다.

Python으로 옮긴 예

아래는 논문의 Fortran 서브루틴과 같은 순서로 동작하도록 이 글에서 옮긴 코드입니다. Fortran 버전이 BOOLE과 CAND 두 값으로 결과를 돌려주듯, 과반 여부와 후보를 함께 반환합니다. 후보를 None으로 표시하지 않고 따로 플래그를 둔 이유는 None 자체가 입력값일 수 있기 때문입니다.

def majority(xs):
    """(과반 원소가 있는지, 그 원소)를 반환한다. xs는 두 번 읽는다."""
    n = len(xs)
    cand, k = None, 0
    # 짝짓기 단계
    for x in xs:
        if k == 0:
            cand, k = x, 1
        elif x == cand:
            k += 1
        else:
            k -= 1
    if k == 0:
        return False, None
    if k > n // 2:
        return True, cand
    # 세기 단계: 후보가 실제로 절반보다 많은지 센다
    count = 0
    for x in xs:
        if x == cand:
            count += 1
            if count > n // 2:
                return True, cand
    return False, None


print(majority(list("AAACCBBCCCBCC")))  # (True, 'C')
print(majority(list("AAAACBBCCCBCC")))  # (False, None)
print(majority(list("AAABBBC")))        # (False, None)

count > n // 2는 정수 범위에서 “n/2보다 크다”와 같은 조건입니다. n이 홀수 13이면 n // 2는 6이고, 7 이상이어야 통과합니다. 세기 단계에서 카운트가 n/2를 넘자마자 끝내는 것도 논문의 Fortran 코드와 같습니다.

몇 가지를 덧붙입니다. 모두 이 코드에 대한 이 글의 설명입니다.

데이터를 두 번 읽고, 시작할 때 len(xs)를 부릅니다. 그래서 이 함수에는 리스트처럼 길이를 알 수 있고 여러 번 순회할 수 있는 컬렉션을 넘겨야 합니다. 한 번만 소비할 수 있는 이터레이터나 스트림은 과반이 보장되더라도 len()에서 바로 실패합니다.
== 비교만 씁니다. 정렬할 수 없는 값이나 해시할 수 없는 값에도 그대로 쓸 수 있습니다. 대신 ==가 일관되게 동작해야 합니다. 같은 두 값을 비교했을 때 결과가 매번 다르거나, 어떤 값이 자기 자신과 같지 않다고 나오면 위의 증명이 기대는 “같은 표끼리 무리를 이룬다”는 전제가 깨집니다.
입력 외에 쓰는 추가 공간은 O(1)입니다. 후보와 카운터, n, count, 반복 변수처럼 입력 크기와 상관없이 정해진 개수의 변수만 씁니다.

비용과 접근 방식

논문 기준으로 정리하면 이렇습니다.

비교 횟수: 짝짓기 n번, 세기 많아야 n번, 합쳐 많아야 2n번입니다. 확률이나 평균이 아니라 모든 입력에 대한 상한입니다.
비교 종류: 같은지 다른지만 봅니다. 값에 순서가 없어도 됩니다.
접근 순서: 배열 원소를 앞에서부터 차례로 읽습니다. 논문은 그래서 표가 너무 많아 자기 테이프에서 읽어야 할 때도 효율적으로 쓸 수 있고, 첫 단계 뒤에 테이프를 한 번 되감으면 된다고 설명합니다.

출판에 얽힌 사연

논문 말미의 “Postscript 1991” 절은 이 알고리즘의 출판 과정을 직접 설명합니다. 알고리즘은 1980년, 두 저자가 SRI International에 있을 때 고안되었습니다. 고장 허용(fault tolerance)을 연구하던 동료가 Boyer–Moore 정리 증명기의 논리 안에서 리스트의 과반 원소를 우아하게 정의해 달라고 요청했고, 그 답이 이 알고리즘의 재귀적 표현이었다고 합니다. 1980년 말에 Fortran 버전을 쓰고 정확성을 기계적으로 증명했으며, 1981년 2월에 논문을 써서 투고했습니다.

1981년 두 저자는 텍사스 대학교로 옮겼습니다. 논문이 인용한 Jay Misra의 개인 서신(1990)에 따르면, Misra는 이 알고리즘 발표를 듣고 n/k번보다 많이 나오는 원소를 찾도록 일반화하는 방법을 고민했고, 이후 David Gries와 함께 1982년 “Finding Repeated Elements”(Science of Computer Programming 2권)를 발표했습니다. 이 논문은 Boyer와 Moore의 기술 보고서를 “투고 중”으로 인용했습니다.

정작 Boyer와 Moore의 논문은 Fortran과 기계 검증에 무게를 둔다는 이유로 거듭 거절되었고, 알고리즘 중심으로 다시 쓴 판은 Misra와 Gries의 논문에 이미 포함된 내용이라는 이유로 거절되었습니다. 결국 원래 논문은 1991년 Woody Bledsoe 기념 논문집에 실렸습니다. 저자들은 새 알고리즘이 기계로 검사한 정확성 증명과 함께 처음 발표된 사례라는 점에서 이 논문을 형식 검증과 자동 추론 분야의 작은 이정표로 여긴다고 적었습니다.

쓰기 전에 확인할 것

과반의 뜻: 정확히 n/2보다 많아야 합니다. 절반과 같은 경우는 과반이 아닙니다.
두 번째 패스: 과반이 보장되지 않은 입력이라면 후보의 개수를 다시 세야 합니다. 첫 패스의 결과만으로는 과반이 없는 입력에서도 후보가 나옵니다.
카운터의 의미: 마지막 카운터는 후보의 득표수가 아니라 상쇄되고 남은 표의 수입니다.
비교: 같음 비교만 쓰므로 순서가 없는 값에도 쓸 수 있지만, 그 비교가 일관되어야 합니다.
적용 범위: 이 알고리즘은 절반보다 많은 원소 하나만 다룹니다. n/k번보다 많은 원소를 찾는 문제는 위의 Misra–Gries 논문이 다루며, 이 글의 범위 밖입니다.

참고 자료

모두 2026-10-18에 확인했습니다.

J Strother Moore, A Linear Time Majority Vote Algorithm — 1980년 고안, 예제 수열, 1991년 논문의 서지 정보
J Strother Moore, MJRTY 단계별 예제 — 후보·카운터 규칙, 단계별 상태, 과반이 없는 반례, 확인용 두 번째 패스
R. S. Boyer, J S. Moore, “MJRTY—A Fast Majority Vote Algorithm” (1991, PostScript) — 비교 횟수 상한, 전당대회 비유, 정확성 증명, 예제, Fortran 구현과 개선, SIFT 사례, 출판 경위

순서	원소	상태
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

순서	원소	상태
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3

순서	원소	상태
1	A	A:1
2	A	A:2
3	A	A:3
4	C	A:2
5	C	A:1
6	B	?:0
7	B	B:1
8	C	?:0
9	C	C:1
10	C	C:2
11	B	C:1
12	C	C:2
13	C	C:3