[알고리즘] Randomized algorithm - quicksort, randomized selection, majority element

제목: Randomized algorithm, 예측 불가능 속의 효율

서론

알고리즘 설계에 있어서 '무작위성(randomness)'은 상상 이상의 효율성을 가져다줄 수 있다. 마치 카드 게임에서 카드를 섞는 것처럼, 무작위성을 통해 입력 데이터의 순서를 재배열하고 알고리즘의 효율성을 높일 수 있다. 이번 포스팅에서는 Randomized algorithm의 개념과 함께, 대표적인 예시인 Randomized Quicksort, selection, majority element를 살펴보며 무작위성이 알고리즘에 어떻게 활용되는지 알아보자.

무작위 알고리즘: 예측 불가능을 활용

무작위 알고리즘은 알고리즘의 실행 과정에서 무작위성을 도입하여 문제를 해결하는 알고리즘이다. 일반적으로 무작위 알고리즘은 다음과 같은 특징을 갖는다.

평균적인 경우에 좋은 성능: 무작위 알고리즘은 최악의 경우에는 성능이 좋지 않을 수 있지만, 평균적으로는 좋은 성능을 보인다.
높은 확률로 정확한 답: 무작위 알고리즘은 항상 정확한 답을 보장하지는 않지만, 높은 확률로 정확한 답을 찾는다.
근사값: 경우에 따라 무작위 알고리즘은 정확한 답을 찾는 대신, 근사값을 빠르게 찾는 데 사용될 수 있다.

무작위 알고리즘은 크게 Monte Carlo 알고리즘과 Las Vegas 알고리즘으로 나눌 수 있다.

Monte Carlo 알고리즘: 실행 시간은 보장되지만, 정확성은 보장되지 않는 알고리즘이다. 예를 들어, Karger's 알고리즘은 최소 컷(min cut) 문제에 대한 근사 해를 빠르게 찾는 데 사용된다.
Las Vegas 알고리즘: 정확성은 보장되지만, 실행 시간은 보장되지 않는 알고리즘이다. 이번 포스팅에서는 Las Vegas 알고리즘에 대해 자세히 알아볼 것이다.

Bogosort

Bogosort는 입력 리스트를 무작위로 섞고, 정렬되었는지 확인하는 과정을 반복하는 정렬 알고리즘이다. 정렬될 때까지 리스트를 계속해서 섞기 때문에 매우 비효율적이지만, 무작위 알고리즘의 개념을 이해하는 데 좋은 예시이다.

Python
import random

def bogosort(A):
  # 리스트가 정렬될 때까지 무작위로 섞는다
  while True:
    random.shuffle(A)
    sorted = True
    for i in range(len(A)-1):
      if A[i] > A[i+1]:
        sorted = False
        break
    if sorted:
      return A

Bogosort의 최악의 경우 시간 복잡도는 O(∞)이다. 즉, 리스트가 정렬될 때까지 무한히 실행될 수 있다. 반면, 평균적인 경우 시간 복잡도는 O(n⋅n!)이다. (n개 뽑기, 순열 n!가지)

Randomized Quicksort

Quicksort는 분할 정복(divide and conquer) 기법을 사용하는 효율적인 정렬 알고리즘이다. Randomized Quicksort는 Quicksort의 피벗 선택 과정에 무작위성을 도입하여 최악의 경우를 피하고 평균적인 성능을 향상시킨 알고리즘이다.

Randomized Quicksort의 작동 방식은 다음과 같다.

피벗 선택: 리스트에서 무작위로 하나의 요소를 피벗으로 선택한다.
분할: 피벗을 기준으로 리스트를 분할하여, 피벗보다 작은 요소들은 왼쪽, 큰 요소들은 오른쪽에 위치하도록 한다.
재귀: 왼쪽과 오른쪽 부분 리스트에 대해 Randomized Quicksort를 재귀적으로 적용한다.

Quicksort

Python
import random

def randomized_quicksort(A):
  if len(A) <= 1:
    return A
  pivot = random.choice(A)
  left = [x for x in A if x < pivot]
  right = [x for x in A if x >= pivot]
  return randomized_quicksort(left) + [pivot] + randomized_quicksort(right)

이상적으로 pivot이 list를 n/2로 나누는 경우를 생각해보면 O(n log n), pivot이 list의 요소를 1개밖에 나누지 못한 경우는 O(n²)으로 다음과 같이 증명할 수 있다.

recurrence relation

최악의 경우를 피할 수는 없을까? 지난 번 linear-time selection에서도 다뤘듯, list에서 중앙값을 pivot으로 설정하도록 만든다면 가능하다. 지난 시간의 median of medians 부분을 참고하자.

무작위 선택 (Randomized Selection)

무작위 선택 알고리즘은 정렬되지 않은 배열에서 k번째로 작은 요소를 찾는 알고리즘이다. 이 알고리즘은 Quickselect 알고리즘과 유사하지만, 피벗을 무작위로 선택한다는 점이 다르다. 무작위 선택 알고리즘의 최악의 경우 실행 시간은

O (n^{²})

이지만, 평균 실행 시간은

O (n)

이다.

무작위 선택 알고리즘의 작동 방식은 다음과 같다.

배열에서 무작위로 하나의 요소를 피벗으로 선택한다.
피벗을 기준으로 배열을 분할한다. 피벗보다 작은 요소들은 왼쪽, 큰 요소들은 오른쪽에 위치하도록 한다.
k번째로 작은 요소가 어느 부분에 있는지 확인하고, 해당 부분 배열에 대해 재귀적으로 알고리즘을 적용한다.

Python
import random

def randomized_select(A, k):
    if len(A) == 1:
        return A[0]
    pivot = random.choice(A)
    left = [x for x in A if x < pivot]
    right = [x for x in A if x >= pivot]
    if k <= len(left):
        return randomized_select(left, k)
    elif k == len(left) + 1:
        return pivot
    else:
        return randomized_select(right, k - len(left) - 1)

무작위 선택 알고리즘이

O (n)

시간에 실행될 수 있는 이유는 피벗을 무작위로 선택하기 때문이다. 피벗이 배열을 거의 균등하게 나눌 경우, 알고리즘은 선형 시간에 실행된다. 최악의 경우는 피벗이 배열을 매우 불균등하게 나눌 때 발생하지만, 무작위로 피벗을 선택하기 때문에 이러한 경우는 드물다.

과반수 요소 (Majority Element)

과반수 요소 문제는 배열에서 과반수 이상 나타나는 요소를 찾는 문제이다. 즉, 배열의 크기가 n일 때, ⌊n/2⌋ + 1번 이상 나타나는 요소를 찾아야 한다.

과반수 요소 문제는 분할 정복 알고리즘과 무작위 알고리즘을 사용하여 해결할 수 있다.

Majority element 분할 정복 알고리즘 ver.

분할 정복 알고리즘은 배열을 두 개의 부분 배열로 나누고, 각 부분 배열에서 과반수 요소를 재귀적으로 찾는다. 두 부분 배열에서 찾은 과반수 요소가 같으면 해당 요소가 전체 배열의 과반수 요소이다. 만약 두 부분 배열에서 찾은 과반수 요소가 다르면, 전체 배열을 순회하면서 각 요소의 개수를 세어 과반수 요소를 찾는다.

Python
def majority_element(A):
    # 분할 정복
    n = len(A)
    if n == 1:
        return A[0]
    mid = n // 2
    m1 = majority_element(A[:mid])
    m2 = majority_element(A[mid:])
    if m1 == m2:
        return m1
    count1 = 0
    count2 = 0
    for a in A:
        if a == m1:
            count1 += 1
        elif a == m2:
            count2 += 1
    if count1 > n // 2:
        return m1
    elif count2 > n // 2:
        return m2
    else:
        return None  # 과반수 요소가 없음

핵심 인사이트) 전체의 majority = 부분의 majority

이 경우, merge sort와 같은 T(n) = 2T(n/2) + O(n)의 꼴을 갖으므로 runtime은 O(n log n)이다.

Majority element 무작위 알고리즘 ver.

무작위 알고리즘은 배열에서 무작위로 하나의 요소를 선택하고, 해당 요소가 과반수 요소인지 확인하는 과정을 반복한다. 과반수 요소가 아니라면, 다른 요소를 무작위로 선택하고 다시 확인한다. 이때 과반수 요소가 존재할 경우, 높은 확률로 빠르게 찾을 수 있다. 하지만 과반수 요소가 존재하지 않을 경우, 무한 루프에 빠질 수 있다는 단점이 있다.

expected: O(n), worst case: O(∞)

Python
import random

def majority_element(A):
    # 무작위 알고리즘
    n = len(A)
    while True:
        guess = random.choice(A)
        count = 0
        for a in A:
            if a == guess:
                count += 1
        if count > n // 2:
            return guess

추천글 :

[알고리즘] Linear-Time Sorting
(https://hyeonb.blogspot.com/2024/09/linear-time-sorting.html)

[알고리즘] merge sort algorithm analysis
(https://hyeonb.blogspot.com/2024/09/merge-sort-algorithm-analysis.html)

[알고리즘] linear-time selection
(https://hyeonb.blogspot.com/2024/09/linear-time-selection.html)