보이어–무어 과반수 투표 계산기
수열에서 절반을 넘게 나오는 원소를 카운터 한 칸만으로 찾는 과정을 걸음마다 보여줍니다. 후보가 실제로 과반인지 확인하는 두 번째 훑기와, 1/k을 넘는 것을 모두 찾는 미스라–그리스까지 함께 다룹니다.
공백이나 쉼표로 나눠 적습니다. 숫자가 아니어도 됩니다. 400개까지.
과반 원소
가
9개 가운데 6개로 절반(5개 이상)을 넘습니다.
한 번 훑는 동안의 후보와 카운터
| 자리 | 들어온 값 | 한 일 | 후보 | 카운터 |
|---|---|---|---|---|
| 1 | 가 | 카운터가 0이라 새 후보로 | 가 | 1 |
| 2 | 나 | 후보와 달라 −1 | 가 | 0 |
| 3 | 가 | 카운터가 0이라 새 후보로 | 가 | 1 |
| 4 | 가 | 후보와 같아 +1 | 가 | 2 |
| 5 | 다 | 후보와 달라 −1 | 가 | 1 |
| 6 | 가 | 후보와 같아 +1 | 가 | 2 |
| 7 | 나 | 후보와 달라 −1 | 가 | 1 |
| 8 | 가 | 후보와 같아 +1 | 가 | 2 |
| 9 | 가 | 후보와 같아 +1 | 가 | 3 |
쓰는 메모리는 후보 한 칸과 카운터 한 칸뿐입니다. 수열이 아무리 길어져도 늘지 않아서, 수열 전체를 담아 둘 수 없는 스트림에서도 돌릴 수 있습니다.
실제 개수 (정답지)
전체의 1/k을 넘게 나오는 원소를 모두 찾습니다. 카운터는 k−1개만 씁니다. 2~10.
카운터에 남은 후보
| 원소 | 카운터 | 실제 개수 | 1/3 초과 |
|---|---|---|---|
| 가 | 5 | 6 | 넘음 |
| 나 | 1 | 2 | 아님 |
카운터에 남은 값은 실제 개수보다 작거나 같습니다. 깎인 만큼 모자란 것이라, 실제 개수와의 차이는 「모든 카운터를 깎은 횟수」(1번)를 넘지 않습니다.
사용 방법
- 1수열을 공백이나 쉼표로 나눠 적습니다.
- 2한 번 훑는 동안 후보와 카운터가 어떻게 바뀌는지 표에서 확인합니다.
- 3남은 후보가 실제로 과반인지 두 번째 훑기 결과와 견줍니다.
- 4과반이 없는 예제를 넣어 후보가 그대로 답이 되지 않는 것을 봅니다.
- 5k를 바꿔 전체의 1/k을 넘는 원소를 모두 찾아 봅니다.
자주 묻는 질문
수열을 한 번 훑으면서 절반을 넘게 나오는 원소를 찾는 방법입니다. 후보 한 칸과 카운터 한 칸만 쓰므로 입력이 아무리 길어도 메모리가 늘지 않습니다. 카운터가 0이면 지금 값을 후보로 삼고, 후보와 같으면 1을 더하고, 다르면 1을 뺍니다.
서로 다른 두 원소를 한 쌍씩 지워 나가는 것과 같기 때문입니다. 절반을 넘는 원소는 나머지 전부와 짝을 지어도 반드시 남습니다. 카운터를 1 빼는 걸음이 곧 한 쌍을 지우는 것이고, 그래서 마지막에 남는 후보가 과반 원소가 됩니다.
아닙니다. 과반 원소가 아예 없어도 알고리즘은 무언가를 뱉습니다. 예를 들어 1, 2, 3을 넣으면 3이 후보로 남지만 3은 한 번밖에 나오지 않습니다. 그래서 두 번째로 훑어 후보의 실제 개수를 세어 확인하는 절차까지가 알고리즘이며, 이 검증을 빼먹은 구현이 흔합니다.
아닙니다. 과반은 절반 초과입니다. 4개 가운데 2개는 과반이 아니고 3개부터가 과반입니다. 이 도구는 「과반 기준」에 필요한 최소 개수를 함께 보여 주므로 경계에서 헷갈릴 일이 없습니다.
카운터를 k−1개로 늘려 전체의 1/k을 넘게 나오는 원소를 모두 찾는 일반화입니다. k를 2로 두면 카운터가 하나뿐이라 보이어–무어와 정확히 같아집니다. 여기서도 후보가 곧 답은 아니지만, 1/k을 넘는 원소는 반드시 후보 안에 들어 있어 놓치는 일이 없습니다.
쓸 수 없습니다. 가장 많이 나온 것을 알려면 결국 전부 세어야 하고 원소 종류만큼 메모리가 듭니다. 이 알고리즘이 답할 수 있는 것은 「절반을 넘는 것이 있는가」라는 좁은 물음이며, 그 대신 메모리가 상수라는 것이 값어치입니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이뤄지고, 입력한 수열은 이 기기에만 남습니다.
알아두면 좋은 점
- 정답지는 전수 계수입니다. 무작위 수열 3,000개에서 실제로 과반인 원소가 있으면 알고리즘이 반드시 그것을 후보로 남기는 것, 없으면 과반이 아니라고 판정하는 것을 확인했습니다.
- 과반이 없을 때 후보가 아무 의미 없는 값이라는 것을 말로만 적지 않고 [1, 2, 3]을 검사로 박아 두었습니다. 정확히 절반인 경우([가, 가, 나, 나])도 과반이 아닌 것으로 검사합니다.
- 미스라–그리스는 k = 2에서 보이어–무어와 같은 답을 내는 것을 무작위 500개 짝에서 대조했습니다.
- 1/k을 넘는 원소가 반드시 후보에 들어 있는 것(거짓 음성 없음)과, 후보를 다시 세어 걸러낸 결과가 전수 계수와 정확히 같은 것을 무작위 3,000개 수열에서 확인했습니다.
- 카운터에 남은 값이 실제 개수보다 크지 않고, 모자란 만큼이 「모든 카운터를 깎은 횟수」를 넘지 않는다는 오차 한계도 검사합니다. 깎기 횟수가 n/k을 넘지 않는 것도 함께 봅니다.
- 입력은 숫자로 한정하지 않습니다. 알고리즘이 「같은가」만 보기 때문이고, 투표·로그 집계처럼 이름표를 세는 쓰임이 더 자연스럽습니다.
- 수열은 400개까지, k는 10까지 다룹니다. 걸음 표는 60개까지만 그립니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.