[C++로 배우는 알고리즘과 자료구조 심화] Day 25: 임의화 알고리즘 (Randomized Algorithms)

임의화 알고리즘 (Randomized Algorithms)

임의화 알고리즘은 무작위성을 도입하여 문제를 해결하는 알고리즘입니다. 이러한 알고리즘은 일반적으로 평균적인 성능이 좋으며, 특정 패턴이나 최악의 경우를 피할 수 있습니다. 대표적인 임의화 알고리즘에는 랜덤 선택 알고리즘 (Randomized Selection Algorithm), 랜덤 탐색 알고리즘 (Randomized Search Algorithm) 등이 있습니다.

랜덤 선택 알고리즘 (Randomized Selection Algorithm)

랜덤 선택 알고리즘은 주어진 배열에서 k번째 작은 원소를 찾는 문제를 해결합니다. 이 알고리즘은 퀵 선택(Quickselect) 알고리즘의 변형으로, 피벗을 무작위로 선택하여 평균적인 성능을 향상시킵니다.

문제 정의

주어진 배열에서 k번째 작은 원소를 찾는 문제입니다.

 

랜덤 선택 알고리즘 구현

다음은 C++로 랜덤 선택 알고리즘을 구현한 예제입니다.

#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 + 1);
    std::swap(arr[randomPivotIndex], arr[high]);
    return partition(arr, low, high);
}

// 랜덤 선택 함수
int randomizedSelect(std::vector<int>& arr, int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }

    int pivotIndex = randomizedPartition(arr, low, high);
    int leftSize = pivotIndex - low + 1;

    if (leftSize == k) {
        return arr[pivotIndex];
    } else if (k < leftSize) {
        return randomizedSelect(arr, low, pivotIndex - 1, k);
    } else {
        return randomizedSelect(arr, pivotIndex + 1, high, k - leftSize);
    }
}

int main() {
    std::srand(std::time(0));
    std::vector<int> arr = {12, 3, 5, 7, 4, 19, 26};
    int n = arr.size();
    int k = 3; // 세 번째로 작은 원소를 찾습니다.

    int result = randomizedSelect(arr, 0, n - 1, k);
    std::cout << k << "번째 작은 원소: " << result << std::endl;

    return 0;
}

랜덤 탐색 알고리즘 (Randomized Search Algorithm)

랜덤 탐색 알고리즘은 무작위로 탐색을 수행하여 문제를 해결합니다. 이러한 알고리즘은 주로 탐색 공간이 크고 최적해를 찾기 어려운 문제에 사용됩니다.

문제 정의

주어진 함수의 최대값이나 최소값을 찾는 문제입니다.

랜덤 탐색 알고리즘 구현

다음은 C++로 랜덤 탐색 알고리즘을 구현한 예제입니다.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <functional>

// 랜덤 탐색 알고리즘 함수
double randomizedSearch(std::function<double(double)> func, double low, double high, int iterations) {
    double bestX = low;
    double bestY = func(low);

    for (int i = 0; i < iterations; ++i) {
        double x = low + static_cast<double>(rand()) / RAND_MAX * (high - low);
        double y = func(x);

        if (y > bestY) {
            bestX = x;
            bestY = y;
        }
    }

    return bestX;
}

int main() {
    std::srand(std::time(0));
    auto func = [](double x) {
        return -std::pow(x, 2) + 4 * x + 10;
    };

    double low = -10;
    double high = 10;
    int iterations = 10000;

    double result = randomizedSearch(func, low, high, iterations);
    std::cout << "최대값을 갖는 x: " << result << std::endl;

    return 0;
}

설명

1. 랜덤 선택 알고리즘:
   • randomizedSelect 함수는 주어진 배열에서 k번째 작은 원소를 찾습니다.
   • randomizedPartition 함수는 무작위로 피벗을 선택하여 배열을 분할합니다.
   • randomizedSelect 함수는 재귀적으로 k번째 작은 원소를 찾습니다.
2. 랜덤 탐색 알고리즘:
   • randomizedSearch 함수는 주어진 함수의 최대값을 찾습니다.
   • func는 탐색할 함수입니다.
   • low와 high는 탐색 범위입니다.
   • iterations는 탐색 반복 횟수입니다.

랜덤 선택 알고리즘과 랜덤 탐색 알고리즘의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 26: 선형 계획법(Linear Programming)"에 대해 학습하겠습니다.