[python] 다수결 투표 알고리즘

다수결 투표 알고리즘

• Robert S. Boyer와 J Strother Moore의 알고리즘
• 배열에서 과반수(50% 초과)이상 등장하는 요소를 찾는 알고리즘

알고리즘 동작 원리

• 변수 설정
  • candidate: 잠재적 과반수 후보
  • count: 후보의 득표 수
• 첫 번째 순회
  • 배열을 순회하며 현재 요소가 candidate와 같으면 count 증가
  • 다르면 count 감소
  • count가 0이 되면 새로운 candidate 선택
• 두 번째 순회
  • 최종 candidate의 실제 등장 횟수 확인
  • 과반수(50% 초과) 여부 검증

예시 코드

def majority_vote(arr):
    candidate = None
    count = 0
    
    # 후보 찾기
    for num in arr:
        if count == 0:
            candidate = num
        
        count += 1 if num == candidate else -1
    
    # 과반수 검증
    return candidate if arr.count(candidate) > len(arr) // 2 else None