[C++로 배우는 알고리즘과 자료구조 심화] Day 24: 확률적 알고리즘 (Monte Carlo, Las Vegas 알고리즘)

확률적 알고리즘

확률적 알고리즘은 무작위성을 도입하여 문제를 해결하는 알고리즘입니다. 이러한 알고리즘은 일반적으로 평균적인 성능이 좋으며, 최악의 경우를 피할 수 있습니다. 확률적 알고리즘은 크게 두 가지 유형으로 나눌 수 있습니다: Monte Carlo 알고리즘과 Las Vegas 알고리즘.

Monte Carlo 알고리즘

Monte Carlo 알고리즘은 정해진 시간 내에 정답을 찾을 확률을 높이는 알고리즘입니다. 정확한 답을 보장하지 않지만, 답을 찾을 확률이 높습니다.

예시: 소수 판별

Monte Carlo 알고리즘을 사용하여 주어진 수가 소수인지 판별하는 방법입니다. 주로 Miller-Rabin 소수 판별법이 사용됩니다.

 

Monte Carlo 알고리즘 구현: Miller-Rabin 소수 판별법

#include <iostream>
#include <vector>
#include <cstdlib>

// 거듭제곱 함수
long long power(long long a, long long b, long long mod) {
    long long result = 1;
    a = a % mod;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % mod;
        b = b >> 1;
        a = (a * a) % mod;
    }
    return result;
}

// Miller-Rabin 소수 판별법
bool millerRabin(long long n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;

    long long d = n - 1;
    while (d % 2 == 0)
        d /= 2;

    for (int i = 0; i < k; i++) {
        long long a = 2 + rand() % (n - 4);
        long long x = power(a, d, n);

        if (x == 1 || x == n - 1)
            continue;

        bool composite = true;
        while (d != n - 1) {
            x = (x * x) % n;
            d *= 2;

            if (x == 1) return false;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }

        if (composite)
            return false;
    }
    return true;
}

int main() {
    int k = 4; // 테스트 횟수
    long long n;
    std::cout << "수를 입력하세요: ";
    std::cin >> n;

    if (millerRabin(n, k))
        std::cout << n << "은(는) 소수입니다.\n";
    else
        std::cout << n << "은(는) 소수가 아닙니다.\n";

    return 0;
}

 

Las Vegas 알고리즘

Las Vegas 알고리즘은 항상 정확한 답을 보장하지만, 실행 시간이 무작위적으로 달라질 수 있는 알고리즘입니다. 일반적으로 답을 찾을 때까지 반복하여 실행됩니다.

예시: 퀵 정렬

Las Vegas 알고리즘의 예시로 퀵 정렬을 들 수 있습니다. 퀵 정렬은 피벗을 무작위로 선택하여 평균적으로 매우 빠른 정렬을 보장합니다.

 

Las Vegas 알고리즘 구현: 퀵 정렬

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

// 배열 분할 함수
int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 무작위 피벗을 사용한 배열 분할 함수
int randomizedPartition(std::vector<int>& arr, int low, int high) {
    int randomPivotIndex = low + rand() % (high - low);
    std::swap(arr[randomPivotIndex], arr[high]);
    return partition(arr, low, high);
}

// 퀵 정렬 함수
void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = randomizedPartition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    std::srand(std::time(0));
    std::vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    std::cout << "정렬된 배열: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

설명

1. Monte Carlo 알고리즘:
   • millerRabin 함수는 주어진 수가 소수인지 판별하는 Monte Carlo 알고리즘입니다.
   • power 함수는 모듈러 거듭제곱을 계산합니다.
   • millerRabin 함수는 (k)번의 테스트를 수행하여 소수일 확률을 높입니다.
2. Las Vegas 알고리즘:
   • quickSort 함수는 무작위 피벗을 사용하여 배열을 정렬하는 Las Vegas 알고리즘입니다.
   • randomizedPartition 함수는 무작위로 피벗을 선택하여 배열을 분할합니다.

Monte Carlo와 Las Vegas 알고리즘의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 25: 임의화 알고리즘(Randomized Algorithms)"에 대해 학습하겠습니다.