랜덤 알고리즘과 알고리즘의 확률적 분석 (Randomized Algorithms & Probabilistic Analysis of Algorithms)

Photo by Isaac Smith on Unsplash

요새 알고리즘에 어떻게 확률론이 사용되는지를 공부하고 있습니다. 그러면서 예전에는 잘 몰랐거나 어렴풋이만 알던 내용들을 정확히 바로 잡고 있는데요. 그중에서도 가장 기본적인 내용을 하나 가볍게 짚고 넘어 가고자 합니다. 바로 랜덤 알고리즘(randomized algorithm)과 알고리즘의 확률적 분석(probabilistic analysis of algorithm)인데요. 결론을 미리 말씀 드리자면 둘은 서로 다릅니다.

• 랜덤 알고리즘은 확률 시행이 알고리즘의 내부에서 이루어지는 것을 지칭합니다. 대신 주어지는 입력에 대해서는 어떠한 가정도 존재하지 않죠. 확률 시행이 알고리즘의 내부에서 진행되니, 알고리즘은 동일한 입력에 대해서도 다른 결과를 출력할 수 있습니다. 이러한 알고리즘의 성능을 분석할 때는 임의의 입력에 대해서 해당 알고리즘을 수행시켰을 때 얼마나 좋은 성능을 "기대"할 수 있는지를 따집니다.
• 반대로 알고리즘의 확률적 분석은 주어지는 입력이 어떠한 확률 분포(probability distribution)를 갖는다는 가정 아래에서 이루어집니다. 이때 알고리즘은 같은 입력에 대해서는 동일한 출력을 주는 결정론적(deterministic) 알고리즘일 수도 있습니다. 대신 입력이 확률적으로 주어지기 때문에, 우리는 입력에 대한 알고리즘의 "평균"적인 성능을 측정하거나 나쁜 성능을 보이는 상황은 그리 높은 확률을 갖지 않음을 보일 수 있을 것입니다.

간단한 예시를 통해 실제로 두 개념이 어떻게 다른지를 비교해 보도록 하겠습니다.

---

예전에 학부 알고리즘 과목에서 조교를 할 때 있었던 일입니다. 한번은 다음과 같은 문제가 과제로 나갔습니다. 똑같은 문제를 소개하기는 좀 그러니, 약간 각색하도록 하겠습니다.

총 \(n + 2\) 장의 카드가 책상 위에 일렬로 놓여 있다. 각 카드에는 '→'와 '←'가 그려져 있다. 첫 번째 카드와 마지막 카드에는 각각 '→'와 '←'가 그려진 것으로 공개됐지만, 나머지 카드들은 뒤집힌 채로 있다. 이때, 가운데 카드를 최대한 적게 뒤집으면서 각각 '→', '←'가 그려진 연속된 카드 두 장을 찾으시오.

이 문제를 해결하는 가장 "멍청한" 방법은 다음과 같습니다.

가운데 카드를 앞에서부터 하나씩 차례로 뒤집으면서 언젠가 '←'가 나오는 순간 이 카드와 바로 이전의 카드를 답으로 출력한다.

이 알고리즘은 최악의 경우 가운데 카드들을 모두 뒤집어야 원하는 답을 얻을 수도 있습니다. 바로 다음과 같은 입력에서 말이죠.

→, →, →, …, →, ←

이보다 적은 카드를 뒤집고도 답을 구하는 알고리즘이 있는데요, 이분 탐색(binary search)과 유사한 방법을 사용하면 됩니다. 그러면 \( O(\log n) \) 개의 카드만 뒤집는 것으로 충분하다는 것을 증명할 수 있습니다. 당시에도 후자와 비슷한 알고리즘을 제시하는 것이 출제 의도였습니다.

 

안타깝게도 몇몇 학생들은 앞에서부터 하나씩 뒤집어 보는 알고리즘으로 답안을 작성했었습니다. 그런데 개중에서 유독 제 눈을 사로잡은 답안이 있었습니다. 해당 답안의 한 구절을 간략하게 인용해 보겠습니다.

물론 이 알고리즘은 최악의 경우에는 모든 카드를 뒤집어야 할 수도 있다. 하지만, 각 카드가 \( \frac{1}{2} \)의 확률로 '→'와 '←' 중 하나를 가질 것이므로, 그 확률은 \( \frac{1}{2^n} \)이 되어 그러한 상황은 거의 일어나지 않는다. 따라서 이 알고리즘은 선형 시간보다 빠르게 동작한다.

슬프지만 이 학생은 좋은 점수를 받지 못하였습니다. 문제의 조건 중에 최악의 경우에도 선형 시간보다 빠르게 동작하는 알고리즘을 제시하는 것이 있었기 때문이죠. 하지만 이 학생이 분석한 방법이 이 글의 주제인 알고리즘의 확률적 분석이 무엇인지를 잘 보여주고 있습니다. 이 학생은 처음에 뒤집혀 있는 카드에 각각 독립적으로(independently) 균일한 확률로(uniformly at random) 화살표가 그려지는 특정한 분포에 대해서 멍청한 알고리즘이 실제로 멍청하게 동작할 확률이 그리 높지 않다는 것을 보였습니다.

 

이처럼 주어지는 입력이 어떤 특정한 확률 분포를 나타낼 때, 우리는 알고리즘의 평균적인 성능(average-case performance)이나 성능이 나빠지는 경우가 확률적으로 잘 나타나지 않는다는 것을 보일 수 있는 경우가 많습니다. 이러한 분석 방법이 바로 알고리즘의 확률적 분석이 되는 것입니다.

 

재밌는 사실은 학생이 가정한 입력 분포에 대해 멍청한 알고리즘은 평균적으로 준수한 성능을 보입니다. 왜냐하면 그 알고리즘이 뒤집어 보는 카드의 개수가 정확히 \(p = \frac{1}{2}\)인 기하 분포(geometric distribution)를 따르기 때문입니다. 따라서 그때 뒤집는 카드 개수의 기댓값은 기하 분포의 기댓값인 \(2\)가 됩니다. 즉 상수 시간(constant time)에 알고리즘이 끝난다는 것이죠. 어쩌면, 이 입력 분포에서는 앞에서 소개한 이분 탐색의 변형 알고리즘보다 좋은 성능을 보이는 것 같기도 하네요. 기하 분포의 기댓값을 구하는 방법에 대해서는 아래 포스트를 참조하시기 바랍니다.

2020/11/10 - [알고리즘 & 확률/Coupon collector] - 쿠폰 수집가 문제 (Coupon Collector Problem)

쿠폰 수집가 문제 (Coupon Collector Problem)

---

알고리즘의 확률적 분석은 입력이 어떤 확률 분포에 따라 주어지며, 그때 알고리즘의 평균적인 성능 등을 분석하는 일입니다. 이와 비슷하지만 궤를 달리하는 개념이 있는데요. 바로, 랜덤 알고리즘입니다. 랜덤 알고리즘은 알고리즘 내부에서 자체적으로 확률 시행을 거칩니다. 그 때문에 이 알고리즘은 독특한 특징을 갖습니다. 그것은 바로 동일한 입력에 대해서도 매번 다른 결과를 출력할 수 있다는 것입니다. 예를 들어, 두 장의 카드 A와 B가 주어졌을 때, 어떤 알고리즘이 균등한 확률로 각각을 뽑는다고 해 보죠. 그러면 분명 동일한 입력에 대해서도 어떨 때는 A를 또 어떨 때는 B를 출력할 것입니다.

 

이러한 알고리즘을 분석할 때 우리는 대개 입력에 어떠한 가정도 세우지 않습니다. 아무 입력이 들어와도 출력되는 결과가 달라질 수 있기 때문이죠. 그때 알고리즘이 보이는 평균적인 성능을 구하거나 나쁜 상황에 빠지는 확률이 그리 크지 않음을 보임으로써 우리는 랜덤 알고리즘을 분석할 수 있습니다. 여기서 말하는 알고리즘의 성능은 여러 가지가 될 수 있습니다. 경우에 따라서는 알고리즘이 동작하는 시간일 수 있고, 또 어떨 때는 알고리즘이 출력하는 답의 질일 수도 있죠.

 

랜덤 알고리즘의 가장 유명한 예시는 퀵 정렬(quick sort)입니다. 퀵 정렬은 매 재귀 호출마다 축(pivot)을 잡아서 그 축보다 작은 값과 큰 값으로 나눈 다음 각각을 재귀적으로 정렬하는 방법인데, 만약 매번 축을 멍청하게 잡으면 최악의 경우 \( O(n^2) \)의 비교 연산을 진행해야 합니다. 하지만 만약 매번 고려하는 숫자들 중에서 축을 균등한 확률로 뽑는다면 비교 연산의 횟수를 \( O(n \log n) \) 번으로 기대할 수 있게 됩니다. 이때 이 알고리즘의 입력에 대해서 우리는 어떠한 가정도 하지 않았습니다. 즉, 임의의 입력에 대해서 \(O(n \log n)\)의 수행 시간을 기대할 수 있다는 것이죠. 더 자세한 내용은 다음을 참조하세요.

2020/08/01 - [알고리즘 & 확률/Sort & Selection] - 확률 퀵 정렬 분석 (Analysis on Randomized Quick-Sort)

확률 퀵 정렬 분석 (Analysis on Randomized Quick-Sort)

---

이번 시간에는 랜덤 알고리즘과 알고리즘의 확률적 분석이 각각 어떤 개념이고, 둘이 어떻게 다른지를 간단한 예시와 함께 알아 봤습니다. 결론은 서두에 이미 정리해 두었으므로 따로 첨언하지는 않겠습니다.

 

랜덤 알고리즘은 크게 두 종류로 나뉩니다. 이는 상술했던 알고리즘의 성능을 무엇으로 두냐에 따라 달라집니다. 하나는 항상 올바른 답을 출력하지만 수행 시간이 매번 바뀌어 수행 시간에 대한 확률적 분석을 진행해야 하는 라스베이거스 알고리즘(Las Vegas algorithm)이고, 다른 하나는 수행 시간은 항상 어느 상한을 넘지 않지만 올바르지 않은 답을 출력할 수도 있는 몬테카를로 알고리즘(Monte Carlo algorithm)입니다. 실례로 랜덤 퀵 정렬은 항상 정렬에 성공하지만 축을 어떻게 선정하냐에 따라서 수행 시간이 최악의 경우에는 \(O(n^2)\)에 이를 수 있는 라스베이거스 알고리즘입니다. 반면 아직 몬테카를로 알고리즘은 이 블로그에서 소개할 기회가 없었던 것 같네요. 다음에는 두 알고리즘이 각각 어떤 성질을 갖는지 설명 드리고, 그리고 기회가 되면 몬테카를로 알고리즘의 실제 예시도 함께 소개해 보도록 하겠습니다. 몬테카를로 알고리즘의 대표 격인 유명한 예시가 있거든요.

 

번역을 할 때 애를 좀 먹었습니다. 예전에는 randomized algorithm을 확률 알고리즘으로 번역했는데, 그러다 보니 probability analysis of algorithm을 번역할 때 혼동이 올 소지가 다분하겠더군요. 이제부터 randomized algorithm은 랜덤 알고리즘으로 번역하고자 합니다. 혹여 더 좋은 번역이 있다면 제게 좀 알려 주시면 감사하겠습니다.

 

잘못된 점이 있거나, 궁금하신 점이 있으시면 언제든지 알려 주세요. 고맙습니다. :)

참조

[1] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.