[알고리즘] 보이어-무어 다수결 알고리즘 - Boyer-Moore Majority Vote Algorithm

안녕하세요, 오늘은 프로그래밍과 알고리즘의 흥미진진한 세계에서 매우 중요한 주제인 '보이어-무어 다수결 알고리즘'을 살펴보려고 합니다. 🧐 이 알고리즘은 코딩 인터뷰에서 자주 마주치는 다양한 문제들, 특히 배열에서 가장 많이 등장하는 요소를 찾는 문제를 효율적으로 해결하는 데 큰 도움을 줍니다. 🎓

 

 

Boyer-Moore Majority Vote Algorithm

 

---

🧐 Boyer-Moore Majority Vote Algorithm 이란?

• 이 알고리즘은 1981년 Robert S. Boyer와 J Strother Moore가 개발했어요.
• 목적: 주어진 배열에서 과반수를 차지하는 요소를 효율적으로 찾는 것입니다.
• 특징: 배열을 한 번만 순회하면서 과반수 요소를 찾아낼 수 있어요.

•  

 

Boyer-Moore Majority Vote Algorithm

 

---

🔍 작동 원리

1. 변수 설정: '후보 요소(candidate)'와 '카운터(count)' 두 가지 변수를 사용합니다.
2. 순회: 배열을 순회하면서 현재 후보와 같은 요소를 만나면 카운터를 증가, 다른 요소를 만나면 카운터를 감소시킵니다.
3. 후보 교체: 카운터가 0이 되면 새로운 요소를 후보로 선택합니다.

📈 시간 복잡도와 공간 복잡도

• 시간 복잡도: O(n)
  • 배열을 단 한 번만 순회하기 때문에 시간 복잡도는 O(n)입니다. n은 배열의 길이를 의미해요.
• 공간 복잡도: O(1)
  • 추가적인 공간을 사용하지 않고, 몇 개의 변수만을 이용하기 때문에 공간 복잡도는 O(1)입니다.

 

def majority_element(nums):
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

# Example usage
example1 = [1, 2, 1, 3, 1]
example2 = [2, 2, 1, 1, 2, 2]
example3 = [3, 3, 4, 2, 4, 4, 2, 4, 4]

majority_element_1 = majority_element(example1)
majority_element_2 = majority_element(example2)
majority_element_3 = majority_element(example3)

(majority_element_1, majority_element_2, majority_element_3)

 

보이어-무어 다수결 알고리즘을 사용하여 세 가지 예제에 대한 결과를 얻었습니다:

• 예제 1 ([1, 2, 1, 3, 1]): 다수의 요소는 1입니다.
• 예제 2 ([2, 2, 1, 1, 2, 2]): 다수의 요소는 2입니다.
• 예제 3 ([3, 3, 4, 2, 4, 4, 2, 4, 4]): 다수의 요소는 4입니다.

---

🎉 보이어-무어 다수결 알고리즘은 배열에서 과반수 요소를 찾는 매우 효율적인 방법입니다. 특히, 그 효율성은 시간 복잡도 O(n)과 공간 복잡도 O(1)로 나타납니다. 데이터 처리나 알고리즘 문제 해결에 있어 큰 힘을 발휘할 수 있습니다. 💡