무작위 알고리즘
무작위 알고리즘은 난수 선택을 이용해 실행 시간·정확도 또는 탐색 순서를 결정하는 알고리즘 계열이다. 알고리즘의 확률적 알고리즘 설계 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라...
| 분류 | 알고리즘 · 확률적 알고리즘 설계 |
|---|---|
| 목적 | 난수 선택을 이용해 실행 시간·정확도 또는 탐색 순서를 결정하는 알고리즘 계열 |
| 핵심 과정 | 무작위 퀵 정렬은 피벗을 랜덤하게 선택하고, 무작위 샘플링은 확률 분포에 따라 원소를 선택한다 |
| 시간·연산 비용 | 기대 시간·최악 시간·실패 확률을 함께 분석하며 구현마다 다르다 |
| 적용 전제 | 균일성 등 난수 분포 가정과 독립성, 반복 실험 조건을 명시해야 한다 |
| 관련 분야 | 알고리즘 설계, 계산 복잡도 |
| 참고 자료 | MIT 알고리즘 강의 |
무작위 알고리즘은 난수 선택을 이용해 실행 시간·정확도 또는 탐색 순서를 결정하는 알고리즘 계열이다. 알고리즘의 확률적 알고리즘 설계 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라 종료 조건, 필요한 상태의 표현과 입력 조건을 함께 정의한다.[1]
핵심 처리 과정은 다음과 같다. 무작위 퀵 정렬은 피벗을 랜덤하게 선택하고, 무작위 샘플링은 확률 분포에 따라 원소를 선택한다. 결과가 항상 정확하되 실행 시간이 변하는 Las Vegas형과 일정 시간 안에 오답 확률을 허용하는 Monte Carlo형을 구분한다. 설계 시에는 각 단계에서 보존되어야 할 불변식이나 조건을 정의하고, 결과를 반환하기까지 어떤 상태가 수정되는지를 추적한다.
계산 자원은 문제의 크기와 구현 방식에 좌우된다. 기대 시간·최악 시간·실패 확률을 함께 분석하며 구현마다 다르다. 적용 조건은 균일성 등 난수 분포 가정과 독립성, 반복 실험 조건을 명시해야 한다라는 점이다. 이 조건이 성립하는지를 먼저 확인해야 동일한 절차를 다른 입력에도 일관되게 사용할 수 있다.
무작위 선택·해싱·소수 판별에 활용한다. 보안 목적에는 일반 의사난수 생성기 대신 암호학적으로 안전한 난수 생성기가 필요하다. 실제 구현에서는 상태 표현, 자료구조 선택, 재귀 호출 또는 반복 처리, 메모리 접근과 경계 입력을 함께 고려한다. 이론적 계산 모델과 구체적인 프로그램의 시간·공간 비용은 입력 분포와 실행 환경에 따라 달라질 수 있다.[2]