무작위 알고리즘: 동전을 던져 더 빨라지다

지난 글에서 근사 알고리즘이 “정확성”을 양보해 다항 시간을 얻는 길을 보았습니다. 이번에는 또 다른 종류의 양보를 살펴봅니다. 알고리즘 안에서 동전을 던지는 것 — 즉 무작위성을 계산 도구로 끌어들이는 무작위 알고리즘(randomized algorithm)입니다. 무작위성은 적의 최악 입력을 무력화하고, 복잡한 결정론적 설계를 놀랍도록 단순하게 만들며, 때로는 결정론으로는 알려진 방법이 없는 일도 해냅니다.

두 가지 무작위 알고리즘

무작위 알고리즘은 무엇을 확률적으로 두느냐에 따라 두 부류로 나뉩니다.

라스베이거스와 몬테카를로

라스베이거스(Las Vegas) 알고리즘은 결과가 항상 옳습니다. 대신 실행 시간이 무작위로 변동하며, 우리는 그 기댓값으로 성능을 평가합니다. 무작위 퀵정렬이 대표적입니다. 몬테카를로(Monte Carlo) 알고리즘은 반대로 실행 시간은 확실하게 정해져 있지만, 결과가 작은 확률로 틀릴 수 있습니다. 소수 판정에 쓰이는 밀러–라빈이 대표적입니다. 한쪽은 시간의 확실성을, 다른 쪽은 정답의 확실성을 양보합니다.

무작위 퀵정렬의 기대 시간

퀵정렬의 최악 시간은 O(n²)입니다. 이미 정렬된 배열에서 항상 첫 원소를 피벗으로 고르면 분할이 극도로 치우치기 때문입니다. 적이 우리 코드를 보고 최악 입력을 만들 수 있다면 이 약점은 치명적입니다. 해결책은 단순합니다 — 피벗을 무작위로 고르는 것입니다.

import random

def quicksort(arr, lo, hi):
    if lo >= hi:
        return
    # 무작위 피벗을 끝으로 이동
    p = random.randint(lo, hi)
    arr[p], arr[hi] = arr[hi], arr[p]

    pivot = arr[hi]
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]

    quicksort(arr, lo, i - 1)
    quicksort(arr, i + 1, hi)

이제 어떤 입력이 들어와도 분할이 치우칠 확률은 우리가 던지는 동전에만 달려 있습니다. 두 원소가 비교되는 횟수를 확률 변수로 분석하면 기대 비교 횟수가 약 2n ln n, 즉 기대 시간 O(n log n)임을 증명할 수 있습니다. 결과는 항상 정렬된 배열이고 시간만 무작위이므로, 이는 전형적인 라스베이거스 알고리즘입니다.

정렬된 i, j 원소가 비교될 확률 = 2 / (j - i + 1)
기대 비교 횟수 = Σ Σ 2/(j-i+1) ≈ 2n ln n = O(n log n)
적이 만든 어떤 입력에서도 동일하게 성립

오류를 증폭으로 길들이기

몬테카를로의 “틀릴 수 있음”은 불안하게 들리지만, 반복으로 오류를 원하는 만큼 낮출 수 있습니다. 한쪽 오류(예: “합성수인데 소수라 답할 확률”이 1/2 이하)인 알고리즘을 독립적으로 k번 돌리면, k번 모두 틀릴 확률은 곱셈으로 줄어듭니다.

오류 증폭

def amplify(monte_carlo_test, x, k):
    # k번 중 한 번이라도 '합성수' 판정이면 확실히 합성수
    for _ in range(k):
        if monte_carlo_test(x) == "composite":
            return "composite"
    return "probably prime"  # 오류 확률 ≤ (1/2)^k

k = 20이면 오류 확률은 약 100만분의 1, k = 50이면 우주적으로 작아집니다 — 하드웨어 오류가 날 확률이 더 높을 정도입니다. 양쪽 오류가 있는 경우에는 여러 번 돌려 다수결로 답을 정하면 되고, 체르노프 한계가 오류가 지수적으로 사라짐을 보장합니다.

밀러–라빈 소수 판정

이 아이디어가 실제로 빛나는 곳이 밀러–라빈(Miller–Rabin) 소수 판정입니다. 큰 수의 소수 여부는 암호학의 기반인데, 무작위 밑(base)을 골라 페르마 소정리의 강화판을 검사합니다. 한 번의 검사로 합성수를 놓칠 확률이 1/4 이하이므로, 밑을 여러 개 무작위로 고르면 오류가 급격히 작아집니다.

def miller_rabin(n, rounds=20):
    if n < 2:
        return False
    # n - 1 = d * 2^r
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    for _ in range(rounds):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False  # 확실히 합성수
    return True  # 매우 높은 확률로 소수

결정론적 소수 판정(AKS)도 존재하지만, 실무에서는 빠르고 간단한 밀러–라빈이 압도적으로 쓰입니다. 무작위성이 “이론적 우아함”이 아니라 “현실적 효율”을 주는 대표 사례입니다.

무작위성이 강력한 이유

무작위 알고리즘이 강한 본질적 이유는 최악 입력을 적이 고를 수 없게 만든다는 데 있습니다. 결정론 알고리즘의 약점은 코드만 보면 드러나지만, 무작위 알고리즘의 동전은 실행할 때마다 새로 던져집니다. 적은 입력만 정할 수 있을 뿐 동전 결과는 통제하지 못하므로, “기대 성능”이 곧 “어떤 입력에서든의 성능”이 됩니다. 해싱에서의 무작위 해시 함수, 빠른 선택, 최소 절단의 카거 알고리즘 등 현대 알고리즘 곳곳에서 같은 원리가 반복됩니다.

이것으로 자료구조·알고리즘이 닿을 수 있는 마지막 지점에 이르렀습니다. 알고리즘 분석의 기초에서 출발해 자료구조, 그래프, 정렬과 탐색, 동적 계획법, 문자열, 정수론, 계산기하, 복잡도 이론, 그리고 근사와 무작위라는 두 갈래의 타협까지 — 정확성·시간·결정성을 어떻게 주고받는지를 함께 살펴봤습니다. 완벽한 답이 비싸질 때, 무엇을 양보하고 무엇을 보장받을지 고르는 안목이야말로 이 긴 여정이 남긴 가장 값진 도구입니다.

지난 글: 근사 알고리즘: 최적을 포기하고 보장을 얻다

읽어주셔서 감사합니다. 😊