무작위 알고리즘 (randomized algorithm)

한 줄 정의: 실행 과정에서 난수를 사용하여 동작을 결정함으로써 평균적으로 빠르거나 간단한 해를 얻는 알고리즘.

쉽게 풀면

무작위 알고리즘은 동전 던지기나 주사위 굴리기처럼 알고리즘 내부에서 무작위 선택을 이용한다. 예를 들어 퀵정렬에서 기준값(피벗)을 무작위로 고르면, 어떤 입력이 들어와도 최악의 경우가 발생할 확률을 매우 낮출 수 있다. 항상 정확한 답을 내지만 실행 시간이 확률적으로 정해지는 라스베가스 알고리즘과, 실행 시간은 고정적이지만 정답을 낼 확률이 높은 몬테카를로 알고리즘으로 나뉜다.

왜 중요한가

많은 조합 최적화·그래프 문제는 결정론적으로 풀면 계산량이 폭발적으로 늘어나지만, 무작위성을 도입하면 훨씬 단순하고 빠른 알고리즘으로 실용적인 성능을 낼 수 있다. 이 때문에 알고리즘 이론뿐 아니라 대규모 데이터 처리, 암호학, 분산 시스템 등에서 확률적 보장을 갖춘 기법으로 폭넓게 연구된다. 또한 무작위 알고리즘의 분석 기법(기댓값, 집중 부등식 등)은 이후 확률적 근사나 스트리밍 알고리즘 연구의 기반이 된다.

논문에서는 이렇게 쓰입니다

"제안한 무작위 알고리즘은 몬테카를로 방식으로 동작하며, 오류 확률을 임의로 작게 만들 수 있음을 보였다."

확정적 알고리즘보다 단순하거나 빠른 대안으로 무작위성을 도입한 기법을 설명할 때 사용된다.

"대규모 그래프에서 최소 신장 트리를 근사하기 위해 라스베가스 방식의 무작위 알고리즘을 설계하였고, 기대 실행 시간이 선형에 가까움을 증명하였다."

그래프 알고리즘 분야에서 무작위성을 이용해 이론적 시간 복잡도를 개선한 결과를 제시할 때 자주 쓰인다.

"암호학적으로 안전한 난수 생성기를 기반으로 한 무작위 알고리즘을 통해 키 교환 프로토콜의 취약점 탐지 시간을 단축하였다."

보안·암호학 분야에서 무작위 알고리즘을 응용해 효율성이나 안전성을 높인 사례를 서술할 때 사용된다.

조금 더 깊게 보면

라스베가스 알고리즘과 몬테카를로 알고리즘의 구분 외에도, 논문에서는 알고리즘의 성능을 '기대 실행 시간(expected running time)'이나 '고확률(high probability)' 보장으로 분석하는 경우가 많다. 이때 체르노프 부등식(Chernoff bound)이나 마르코프 부등식 같은 집중 부등식이 오류 확률이나 편차를 수학적으로 제한하는 데 사용된다. 또한 실제 구현에서는 진짜 난수 대신 유사난수 생성기(PRNG)를 사용하므로, 이론적 무작위성 가정과 실제 구현 사이의 차이도 함께 논의되곤 한다.

주의할 점

무작위 알고리즘의 '평균적으로 빠르다'는 보장은 난수 생성기가 충분히 무작위적이라는 가정에 의존하며, 최악의 경우 성능이 여전히 나쁠 가능성이 이론적으로 남아있는 경우가 많다.