시간 제한이 긴 문제를 찾다가 보이어-무어 다수결 투표 알고리즘 (Boyer-Moore Majority Voting Algorithm) 이라는 것을 찾았다.
보이어-무어 알고리즘 (Boyer-Moore String Search Algorithm)과는 다른 알고리즘입니다.
- 보이어-무어 다수결 투표 알고리즘: 배열 내 과반수 원소 찾기 -한 번순회하면서 다수 원소 검토
- 보이어-무어 알고리즘: 텍스트 내 패턴 검색- 건너뛰기를 통한 효율적 패턴매칭
https://www.acmicpc.net/problem/1270
전쟁 - 땅따먹기
| 시간 제한 | 10 초 | 메모리 제한 | 512 MB |
문제
드디어 전쟁은 전면전이 시작되었고, 서로 땅을 따먹기 시작했다.
현재 여러 지역은 한창 전쟁이 벌어지고 있는 상황인데, 어느 지역은 거의 전쟁이 마무리 단계로 가고 있다.
하지만 당신은 군대를 보낼 때 적군을 혼란시키기 위해서 우리 나라의 군대라는걸 표시하지 않고, 군대의 번호로 표시했다.
어느 땅에서 한 번호의 군대의 병사가 절반을 초과한다면 그 땅은 그 번호의 군대의 지배하에 놓이게 된다.
이때, 각 땅들을 지배한 군대의 번호를 출력하여라. 만약, 아직 전쟁이 한창중인 땅이라면 "SYJKGW"을 쌍 따옴표 없이 출력한다.
입력
첫째 줄에는 땅의 개수 n(n<=200)이 주어진다. 그리고 두 번째 줄에서 n+1번째 줄에는 제일 처음에 숫자 Ti(i번째 땅의 병사수, Ti<=100,000)와, Ti개의 숫자 (각각 병사의 군대 번호)가 주어진다. i번째 땅의 j번째 병사 번호 Nij가 주어진다. ( |Nij| <= 2^31 )
출력
첫째 줄에는 각각의 땅의 상태를 순서대로 출력한다. 만약 땅이 지배가 되어있다면 그 지배한 병사의 번호를 출력하고, 아니라면 "SYJKGW"을 쌍 따옴표 없이 출력한다.
예제 입력 1
4
10 1 2 3 1 2 3 1 2 3 1
5 1 1 1 2 2
6 10 10 2 10 10 2
6 1 1 1 2 2 2예제 출력 1
SYJKGW
1
10
SYJKGW처음 생각한 단순한 코드다. 충분히 빠르다고 생각했지만 문제는 메모리 초과였다.
import os
from collections import Counter
i=iter(os.read(0,os.fstat(0).st_size).split())
t=int(next(i))
res=[b'']*t
for j in range(t):
n=int(next(i))
h=n>>1
x,c=Counter((next(i) for _ in range(n))).most_common(1)[0]
res[j]=x if c>h else b'SYJKGW'
os.write(1,b'\n'.join(res))1. 보이어-무어 다수결 투표란?
보이어-무어 다수결 투표(Boyer-Moore Majority Vote) 알고리즘은 배열 내에서 절반을 초과하여 등장하는 원소, 즉 과반수 원소를 효율적으로 찾아내는 알고리즘이다. 이 알고리즘은 선형 시간복잡도 $O(n)$에 $O(1)$의 추가 공간만 사용하여 효율적으로 과반수 원소를 판별할 수 있다. 이러한 특징 덕분에 큰 데이터셋에서도 높은 성능을 발휘하며, 분산 처리가 어려운 상황에서도 유용하게 쓰일 수 있다.
이 알고리즘의 핵심 아이디어는 다음과 같다: 같은 숫자를 만나면 count를 증가, 다른 숫자를 만나면 count를 감소시키며, count가 0이 되는 순간 새로운 후보를 선택한다. 결국 가장 많이 등장하는 원소가 남게 되어 과반수 원소를 쉽게 찾아낼 수 있게 된다.
2. 문제 소개
보이어-무어 다수결 투표 알고리즘을 사용하여 다음과 같은 문제를 해결해 보겠다:
"전쟁 - 땅따먹기" 문제는 여러 지역에서 서로 다른 군대가 전투를 벌이고 있으며, 한 지역에서 절반을 초과하는 병사를 가진 군대가 그 땅을 지배하게 된다는 조건을 만족하는 지배 군대를 찾는 것이다. 만약 절반을 초과하는 병사가 없다면 해당 땅은 아직 전쟁 중으로 판단된다.
문제의 입력과 출력 형식
- 입력: 첫 번째 줄에 땅의 개수 $n$이 주어진다. 그 다음 각 땅에 대한 병사들의 정보가 주어진다. 병사의 번호가 주어지며, 동일 번호는 같은 군대를 의미한다.
- 출력: 각 땅에 대해 지배 군대의 번호를 출력하며, 절반을 초과하는 군대가 없다면 "SYJKGW"를 출력한다.
3. 보이어-무어 다수결 투표 알고리즘이 필요한 이유
이 문제에서는 각 땅의 병사 수가 최대 100,000이며, 전체 땅의 개수 $n$이 최대 200이다. 또 $|Nij| <= 2^{31}$다. 따라서 모든 땅에 대해 단순히 각 군대의 수를 세는 방식으로 과반수 군대를 찾으려면 $O(n \times T)$의 시간복잡도를 가지게 되어 비효율적이다. 이 문제를 효율적으로 해결하기 위해서는 보이어-무어 다수결 투표 알고리즘을 적용하여 각 땅마다 과반수 군대 후보를 빠르게 찾는 것이 중요하다.
시간 복잡도 분석
입력 크기
- $n$: 땅의 개수 ($n \leq 200$)
- $T_i$: $i$번째 땅의 병사 수 ($T_i \leq 100,000$)
단계별 분석
- 각 땅에 대한 순회: $O(n)$
- 각 땅에서의 병사 수 계산:
- 최대 $T_i$명 병사 처리
- 군대 번호 카운트: 해시맵 사용 시 각 병사당 $O(1)$
- 각 땅마다 $O(T_i)$ 소요
총 시간 복잡도
$O(n \cdot \max(T_i))$ = $O(n \cdot 100,000)$ = $O(2 \cdot 10^7)$
공간 복잡도 분석
필요한 저장 공간
- 입력 데이터 저장: $O(n + \max(T_i))$
- 카운팅을 위한 추가 공간: 각 땅마다 $O(T_i)$, 재사용 가능
총 공간 복잡도
$O(n + \max(T_i))$ = $O(200 + 100,000)$ = $O(100,000)$
결론
- 시간 복잡도: $O(n \cdot \max(T_i))$
공간 복잡도: $O(n + \max(T_i))$
4. 보이어-무어 알고리즘 구현과 해설
다음은 주어진 문제를 해결하기 위한 보이어-무어 다수결 투표 알고리즘을 활용한 코드와 그 해설이다:
def s():
import os
n, *r = os.read(0, os.fstat(0).st_size).splitlines()
n = int(n)
result = [b''] * n
for i in range(n):
m, *soldiers = map(int, r[i].split())
able, count = None, 0
for soldier in soldiers:
if count == 0:
able = soldier
count = 1
elif able == soldier:
count += 1
else:
count -= 1
if soldiers.count(able) > m >> 1:
result[i] = str(able).encode()
else:
result[i] = b"SYJKGW"
os.write(1, b"\n".join(result) + b"\n")
s()
5. 코드 해설
- 입력 처리 및 초기화
os.read()와os.fstat()를 사용하여 입력을 처리함으로써 빠르게 데이터를 읽는다. 이는 큰 입력 데이터를 처리하는 데 유리하다.- 땅의 개수 nn을 읽어오고, 결과를 저장할 리스트
result를 초기화한다.
n, *r = os.read(0, os.fstat(0).st_size).splitlines() n = int(n) result = [b''] * n- 보이어-무어 알고리즘 적용
m과 각 병사의 번호를 읽어들여soldiers리스트로 저장한다.able과count를 초기화하고, 각 병사를 순회하며 보이어-무어 다수결 투표 알고리즘을 적용한다.count가 0이 될 때 새로운 후보를 설정하고, 이후 같은 후보가 나올 때마다count를 증가, 다른 후보가 나오면count를 감소시킨다.
m, *soldiers = map(int, r[i].split()) able, count = None, 0 for soldier in soldiers: if count == 0: able = soldier count = 1 elif able == soldier: count += 1 else: count -= 1- 과반수 여부 확인
- 후보
able이 실제로 과반수를 초과하는지 확인하기 위해soldiers.count(able)를 사용하여 빈도를 확인한다. - 과반수를 초과할 경우 해당 후보를 결과 리스트에 추가하고, 그렇지 않으면 "SYJKGW"를 추가한다.
- 후보
if soldiers.count(able) > m >> 1: result[i] = str(able).encode() else: result[i] = b"SYJKGW"- 출력 처리
os.write()를 사용하여 결과를 출력함으로써 빠른 출력이 가능하도록 최적화하였다.
os.write(1, b"\n".join(result) + b"\n")
5. 보이어-무어 알고리즘의 동작 과정 (표 설명)
아래는 보이어-무어 다수결 투표 알고리즘의 동작 과정을 설명하는 표이다. 각 단계에서 candidate와 count가 어떻게 변화하는지 병사 번호의 리스트 [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]를 예시로 들어보자.
| 단계 | 병사 번호 | 현재 후보 (candidate) |
카운트 (count) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 2 | 1 | 0 |
| 3 | 3 | 3 | 1 |
| 4 | 1 | 3 | 0 |
| 5 | 2 | 2 | 1 |
| 6 | 3 | 2 | 0 |
| 7 | 1 | 1 | 1 |
| 8 | 2 | 1 | 0 |
| 9 | 3 | 3 | 1 |
| 10 | 1 | 3 | 0 |
이와 같이 각 단계에서 count가 0이 되면 새로운 후보를 설정하게 된다. 최종적으로 가장 많이 등장하는 원소가 남게 되지만, 과반수 여부는 별도의 확인 과정이 필요하다.
보이어-무어 다수결 알고리즘이 과반수 상황에만 적용되는 이유를 구체적으로 설명하기 위해, 예시를 통해 단계별로 과정을 보겠다. 과반수가 아닌 경우에서는 다수를 정확히 찾지 못하는 과정을 확인할 수 있다.
다음과 같은 배열을 예시로 사용하겠다.
예제 배열: [1, 2, 3, 1, 2, 1, 2, 1]
여기서 1이 4번, 2도 3번 등장하며, 둘 다 과반수가 아니지만, 1이 2보다 많이 등장하는 경우다. 즉, 1이 다수지만 과반수는 아닌 상황을 살펴보자.
단계별 과정
| 단계 | 현재 요소 | 후보 | 카운트 | 설명 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 첫 번째 요소를 후보로 설정하고 카운트를 1로 시작. |
| 2 | 2 | 1 | 0 | 두 번째 요소가 후보와 다름. 카운트를 1 줄여 0이 되면 후보를 제거함. |
| 3 | 3 | 3 | 1 | 카운트가 0이므로 현재 요소(3)를 새로운 후보로 설정하고 카운트를 1로 설정. |
| 4 | 1 | 3 | 0 | 네 번째 요소가 후보와 다름. 카운트를 1 줄여 0이 되면 후보를 제거함. |
| 5 | 2 | 2 | 1 | 카운트가 0이므로 현재 요소(2)를 새로운 후보로 설정하고 카운트를 1로 설정. |
| 6 | 1 | 2 | 0 | 여섯 번째 요소가 후보와 다름. 카운트를 1 줄여 0이 되면 후보를 제거함. |
| 7 | 2 | 2 | 1 | 카운트가 0이므로 현재 요소(2)를 새로운 후보로 설정하고 카운트를 1로 설정. |
| 8 | 1 | 2 | 0 | 여덟 번째 요소가 후보와 다름. 카운트를 1 줄여 0이 되면 후보를 제거함. |
결과
이 과정을 통해 최종적으로 후보가 0이 되며 아무것도 남지 않는다. 따라서 보이어-무어 다수결 알고리즘은 다수가 있음에도 불구하고 과반수가 아니라면 다수를 정확히 찾지 못할 수 있다.
이 예제에서 1이 4번으로 가장 많이 등장했지만 과반수가 아니므로 최종적으로 다수 후보를 찾지 못하는 결과를 낳게 된다.
6. 결론
보이어-무어 다수결 투표 알고리즘은 이와 같은 과반수 판별 문제를 효율적으로 해결할 수 있는 강력한 도구이다. 위 문제와 같이 여러 지역에서 병사들의 지배 여부를 판별해야 하는 상황에서, 이 알고리즘을 사용하면 선형 시간 내에 후보를 찾아낼 수 있으며, 추가적인 공간도 거의 사용하지 않기 때문에 매우 효율적이다. 특히, 데이터의 크기가 커질수록 이 알고리즘의 중요성이 부각되며, 실전에서도 여러 가지 응용 문제에 적용할 수 있는 유용한 알고리즘임을 알 수 있다.
https://lighter.tistory.com/22
보이어-무어 다수결 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)
최근에 배우게 된 보이어-무어 다수결 투표 알고리즘에 대해 글을 써보고자 한다. 보이어-무어 다수결 투표 알고리즘이란? K명의 후보들이 N명에게 투표받을 때, 과반수 이상인 후보가 나오는
lighter.tistory.com
위키피디아 번역
아래는 위키피디아 내용의 번역임.
Boyer-Moore 다수 투표 알고리즘
Boyer-Moore 다수 투표 알고리즘은 선형 시간 복잡도와 상수 메모리만을 사용해 시퀀스 내에서 과반수 요소를 찾는 알고리즘이다. 이 알고리즘은 Robert S. Boyer와 J Strother Moore가 1981년에 발표하였으며, 스트리밍 알고리즘의 전형적인 예로 언급된다.
기본적으로, 이 알고리즘은 과반수 요소가 존재할 경우 해당 요소를 찾아낸다. 과반수 요소란 입력 요소의 절반을 초과하여 반복되는 요소를 의미한다. 이 알고리즘은 추가적으로 데이터를 한 번 더 탐색하여 첫 번째 탐색에서 찾은 요소가 실제로 과반수인지 확인할 수도 있다.
설명
이 알고리즘은 로컬 변수로 저장된 요소와 카운터를 유지하며, 카운터는 초기값이 0이다. 시퀀스의 요소들을 하나씩 처리하며, 각 요소 \( x \)에 대해 다음의 과정이 진행된다:
- 카운터 \( c \)가 0이면, 현재 요소 \( x \)를 저장된 요소 \( m \)으로 할당하고 카운터를 1로 설정.
- 그렇지 않으면, \( x \)와 저장된 요소 \( m \)을 비교하여 같으면 카운터를 증가, 다르면 카운터를 감소시킴.
요소 m과 카운터 c를 초기화 (c = 0)
각 요소 x에 대해 다음 수행:
c가 0이면, m = x, c = 1로 설정
그렇지 않으면, m과 x가 같으면 c를 1 증가, 다르면 c를 1 감소
최종적으로 m 반환만약 입력 시퀀스에 과반수가 존재하지 않더라도 알고리즘은 시퀀스 내 요소 중 하나를 반환한다. 실제로 과반수인지 확인하기 위해선 두 번째 탐색이 필요할 수 있다.
분석
알고리즘은 하나의 요소와 카운터만을 저장하므로 필요 메모리 공간은 상수 \( O(1) \)이다. 알고리즘은 입력 시퀀스의 각 요소에 대해 상수 연산만 수행하므로 입력 길이 \( n \)에 대해 선형 시간 \( O(n) \)이 걸린다.
정확성
입력에 과반수 요소 \( x \)가 존재한다고 가정할 때, 알고리즘은 최종적으로 \( x \)를 반환해야 한다. Boyer와 Moore는 이 점을 수학적으로 증명하였으며, 입력의 길이 \( n \)에 따라 특정 파티션을 구성해 과반수 요소가 \( m \)임을 보였다.
추가로 이 알고리즘이 스트리밍 알고리즘임을 이해하고 다음과 같이 코드를 수정해서 큰 효과를 얻을 수 있었다.
def s():
import sys
n = int(sys.stdin.readline())
result = []
for i in sys.stdin:
m,*soldiers = i.split()
m=int(m)
able, count = None, 0
for soldier in soldiers:
if count == 0:
able = soldier
count = 1
elif able == soldier:
count += 1
else:
count -= 1
if soldiers.count(able) > m >> 1:
result.append(able)
else:
result.append("SYJKGW")
sys.stdout.write("\n".join(result) + "\n")
s()
스트리밍 알고리즘: 스트리밍 알고리즘은 데이터 스트림을 실시간으로 처리하는 알고리즘이다. 데이터가 매우 크거나 빠르게 유입되어 전체를 저장하거나 분석하기 어려운 경우에 사용된다. 일반적으로 메모리 사용을 최소화하면서 데이터를 요약하거나 특정 정보를 추출하는 데 중점을 둔다. 대표적인 예로는 평균 계산, 빈도수 추정, 혹은 가장 많이 등장하는 항목을 찾는 문제 등이 있다.
def s():
n = int(input())
major=''
for i in range(n):
m,*s = input().split()
h=int(m)/2
d={}
mx = 0
for i in s:
d[i]=d.get(i,0)+1
if mx<d[i]:
mx=d[i]
major=i
print(major if mx>h else "SYJKGW")
s()파이썬 코드 중 가장 느린 것이 26172ms였는데 조금 코드를 정리하니 9316ms가 나왔고, 함수로 감싸니까(위 코드) 6728ms가 나왔다. 한 번에 읽지 않고 카운터 등을 쓰지 않으면 메모리 문제를 해결할 수 있고, 그러면 보이어-무어 다수결 투표 알고리즘 없이도 무난히 통과할 수 있는 문제다.
import sys
def input():return sys.stdin.readline().rstrip()위 코드를 추가하면 500ms정도 줄어든다.