TL;DR

  • 원소가 ⌊N/2⌋개보다 많이 등장하는 다수 원소가 반드시 존재하는 수열에서 Boyer–Moore 다수결 투표 알고리즘은 O(N) 시간과 O(1) 공간으로 해당 원소를 찾음.
  • 해시 맵으로 원소별 개수를 세는 방식은 O(N) 시간·O(N) 공간을 사용함.
  • 수열을 정렬한 뒤 가운데 원소를 고르는 방식도 가능하며, 정렬에 드는 시간과 O(1) 공간을 사용함.
  • 알고리즘의 핵심은 서로 다른 원소를 짝지어 상쇄하는 방식이며, 다수 원소는 이 과정에서 살아남음.
  • 이 알고리즘은 수열을 한 번 순회하며 후보와 계수를 갱신하고, 스트리밍 알고리즘으로도 널리 쓰임.

문제와 간단한 풀이

  • 문제 해결 능력을 되살리려다 간단한 문제를 접했고, 그 문제를 통해 우아한 알고리즘을 발견함. 수열의 길이가 N일 때 ⌊N/2⌋개보다 많이 등장하는 원소를 찾는 문제이며, 그런 다수 원소가 반드시 존재한다고 가정함.
  • 해시 맵에 각 원소의 등장 횟수를 기록한 뒤, ⌊N/2⌋개보다 많이 나온 원소를 반환할 수 있음. 시간 복잡도는 O(N), 공간 복잡도는 O(N)임.
  • 수열 전체를 정렬한 뒤 가운데 원소를 반환하는 방법도 있음. 다수 원소가 수열의 절반보다 많이 등장하므로 가운데 원소도 다수 원소여야 함.
  • 모순을 이용하면 이를 증명할 수 있음. 가운데 원소가 다수 원소가 아니라고 가정하면, 다수 원소는 가운데 원소의 왼쪽이나 오른쪽에 있어야 하며, 어느 쪽이든 등장 횟수가 ⌊N/2⌋개보다 적어짐. 이는 다수 원소가 ⌊N/2⌋개보다 많이 등장한다는 가정과 모순임.
  • 정렬 방식의 시간 복잡도는 사용하는 정렬 알고리즘에 따라 달라지며, 공간 복잡도는 O(1)임.
  • 다수 원소를 인공지능(AI)에게 물어보는 방법도 농담 삼아 언급함. 이 방법의 시간·공간 복잡도는 평가할 수 없지만, AI 제품을 보유했다고 말할 수 있다는 농담임.

Boyer–Moore 다수결 투표 알고리즘

  • 문제를 O(N) 시간·O(1) 공간으로 풀 수 있는지 묻는 힌트를 받고 조사한 끝에 Boyer–Moore 다수결 투표 알고리즘을 발견함.
  • 이 알고리즘은 효율적이며 스트리밍 알고리즘으로도 널리 쓰임. 앞선 방법들은 다수 원소를 계산할 때마다 배열 전체를 살펴봐야 하지만, Boyer–Moore 알고리즘은 수열을 순회하며 후보 원소와 계수를 갱신함.
  • C++ 구현은 첫 원소를 후보로 정하고 계수를 1로 시작함. 각 원소를 살펴보면서 계수가 0이면 현재 원소를 새 후보로 삼고, 현재 후보와 같으면 계수를 늘리며, 다르면 계수를 줄임. 마지막 후보를 반환함.

상쇄 방식의 직관

  • 알고리즘은 수열을 순회하며 서로 다른 원소를 상쇄하는 방식으로 동작함. 다수 원소가 ⌊N/2⌋개보다 많이 등장한다는 조건이 보장되므로 상쇄 과정을 거친 뒤에도 다수 원소가 남음.
  • 알고리즘의 형식적 증명은 언급된 위키백과 페이지와 별도의 자료에서 확인할 수 있음.
  • 이 알고리즘의 우아함이 인상적이었으며, 읽는 사람에게도 같은 즐거움을 전하고 싶다는 소감으로 글을 마무리함.