보이어-무어 다수결 투표 (2) 썸네일형 리스트형 [Python] 1270번 전쟁 - 땅따먹기 1270번: 전쟁 - 땅따먹기 (acmicpc.net) 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n 보이어-무어 다수결 투표 알고리즘(Boyer-Moore Majority Vote Algorithm) 최근에 배우게 된 보이어-무어 다수결 투표 알고리즘에 대해 글을 써보고자 한다. 보이어-무어 다수결 투표 알고리즘이란? K명의 후보들이 N명에게 투표받을 때, 과반수 이상인 후보가 나오는지, 나온다면 그 후보가 어떤 후보인지 알아내는 알고리즘.과반수 후보를 가려내는 방법 중 브루트 포스를 이용한 방법과 맵을 이용한 방법(파이썬에서는 딕셔너리 자료형)보다 시간복잡도, 공간 복잡도 면에서 우월함.O(N)의 시간 복잡도로 판단 가능함. 반면, 브루트 포스를 이용한 방법은 O(N^2) 임. 맵을 이용한 방법은 같은 시간 복잡도를 차지하나, 메모리를 더 많이 차지함.스트리밍 알고리즘의 대표적인 예시임.(공간복잡도가 O(1) 임) 이 알고리즘은 두 부분으로 이루어져 있다. 첫 부분은 과반수 원소가 될 수 있는 후보.. 이전 1 다음
