41. randomized algorithms [15 1주차]

41. Randomized Algorithms [15-1주차]

2024년 1월 14일 일요일

오후 5:27

<Randomized Algorithm - Carrier Landing>

항공모함이 착륙하려면 바닥의 장치에 항공모함과 연결된 줄이 걸려야 한다. 장치에 줄을 거는 것이 실패하면, 항공모함은 착륙할 수 없고, 그대로 날아간 뒤 다시 착륙을 시도해야 한다.

 

특정 형태의 항공모함은 줄이 걸리지 않을 확률이 높아 문제가 되었다. 이에 줄의 길이를 무작위로 만들자, 비행기의 종류와 관계없이 줄이 걸릴 확률이 비슷해졌다.

줄이 걸리지 않을 확률이 높은 비행기를 사용하게 되면 큰 손해를 입기 때문에, 확률이 비슷한 것이 낫다.

 

 

<Randomized Algorithm>

우리가 지금까지 보았던, 특정 입력에 대해 수행 시간이 일정한 Deterministic Algorithm과 반대되는 개념이다.

 

Randomized Algorithm은 입력이 똑같아도 어떤 때는 빠르고 어떤 때는 느릴 때도 있다. 심지어 어떤 때는 정답이 틀릴 수도 있다. 물론 답을 맞출 확률이 매우 높다는 것이 보장되어야 실제로 알고리즘이 사용될 수 있다.

 

Quick Sort에서 randomized algorithm을 사용할 경우, 피벗을 첫번째나 중간 등으로 정해 놓지 않고, 랜덤으로 선택하도록 할 수 있다.

이에 따라 고정된 하나의 입력에 대해서도 돌릴 때마다 수행 시간이 달라지며, 특정 입력에 대한 평균 수행 시간이 O(nlogn) 이 된다.

 

특정 종류의 입력에 대해 반복적으로 시간이 오래 걸리는 일이 없다는 점이 장점이다. 알고리즘이 특정 종류의 입력을 주로 처리하고, 그 특정 종류의 입력이 거의 정렬이 어느정도 완료된, 일반적 퀵소트에서 O(n²)이 걸리는 경우, 랜덤 피벗 선정이 도움이 된다.

 

 

<Las Vegas vs Monte Carlo>

Randomized Algorithm은 Las Vegas와 Monte Carlo 알고리즘으로 분류할 수 있다.

 

Las Vegas Algorithm : 답을 항상 맞추고, 특정 입력에 대해 수행 시간이 확률적으로 달라지는 알고리즘

Monte Carlo Algorithm : 특정 입력에 대한 수행 시간은 변하지 않지만, 확률적으로 답을 맞출 때도 있고 틀릴 때도 있는 알고리즘. 답을 맞출 확률이 어느 정도 높아야 실제로 사용 가능하다.

 

Las Vegas를 Monte Carlo 알고리즘으로 바꾸거나, Monte Carlo를 Las Vegas 알고리즘으로 바꿀 수도 있다.

• Las Vegas -> Monte Carlo : 입력에 대한 수행 시간 제한을 걸어 놓고, 그 시간이 지나면 알고리즘을 멈추고 무작위의 답을 낸다.
• Monte Carlo -> Las Vegas : 알고리즘이 구한 답이 정답인지 확인할 수 있는 방법이 있다면 가능하다. (정답을 구하는 것보다 답이 정답인지 아닌지 확인하는 것이 더 쉬운 경우가 많다). 정답이 나올 때까지 반복해서 알고리즘을 돌리면 된다.

 

 

<Linked List in an Array (Las Vegas)>

실수값과 링크로 구성된 구조체의 배열이 존재하고, 오름차순으로 링크가 연결되어 있다. 즉, 배열과 연결 리스트가 중첩되어 있으며, 연결 리스트 관점에서는 정렬된 상태이다. 여기서 값 x를 찾아라.

 

모든 값을 확인하면 O(n)이 걸린다. Las Vegas 알고리즘을 사용하면 평균 수행 시간을 O(n^1/2)으로 줄일 수 있다.

 

해당 확률적 알고리즘은 다음과 같다.

• n^1/2 개의 원소를 랜덤으로 선택한다. 이중 x보다 작은 것 중 가장 큰 원소 y를 선택한다. 그 원소의 링크를 따라가며 x를 찾는다.

 

이러한 알고리즘의 평균 수행 시간을 계산해 보자. 또한, n^1/2개의 원소를 선택하는 것이 최선이라는 것도 증명해 보자.

 

알고리즘 시작 시, 랜덤으로 k개의 원소를 선택하고 y를 찾는 데는 O(k) 시간이 걸린다.

그 다음 링크를 따라가며 x를 찾는 데 걸리는 시간이 평균 O(f(n, k)) 라 하자.

총 수행시간은 O(k+f(n, k))이다.

 

n이하의 자연수 d에 대해, y로부터 d개의 링크를 타고 x에 도착할 확률 P(d)를 구해 보자.

 

위 그림과 같이 원소를 연결 리스트 순서대로 나열하고, y와 y이전의 원소가 a개, x 이후의 원소개 b개라고 하자.

y와 x사이의 거리가 d이상일 확률은, 위 그림의 d개 원소가 선택되지 않을 확률과 같으므로, 대략

이다. 마찬가지 방법으로 계산하면, 거리가 d+1 이상일 확률은 대략

이다. 거리가 d일 확률은 거리가 d 이상일 확률에서 d+1일 확률을 뺀

이다. 이를 이용하여 f(n, k)를 계산하면 다음과 같다.

따라서 총 수행시간은 평균 O(k + n/(k+1)) 이다.

산술기하평균 부등식에 따르면, a * b 의 값이 일정한 경우, a+b는 a=b일 때 최소이다.

어느 정도 근사를 하면, 이를 a=k, b=n/(k+1) 인 경우에도 적용할 수 있다.

(k * {n/(k+1)} ~= n으로 거의 일정하므로)

k = n/(k+1),  k(k+1) = n

방정식을 근사적으로 풀면, k = n^1/2 가 된다.

따라서, k = n^1/2일 때, 총 수행시간은 O(n^1/2 + n/(n^1/2+1)) = O(n^1/2)으로 최소가 된다.

 

 

<Primality Test (Monte Carlo)>

2부터 n까지 수를 하나하나 나누어서 n이 소수인지 판단하는 알고리즘은 Pseudopolynomial이므로 오래 걸린다.

Monte Carlo알고리즘을 사용하면 더 빠르게 소수인지를 판단할 수 있다.

 

소수 여부를 판단하는 Monte Carlo 알고리즘은 다음 "페르마의 소정리"를 이용한다.

• 자연수 n이 소수라면, 1 < a < n 을 만족하는 자연수 a에 대해, a^n-1 % n = 1 이 성립한다.

그러나 자연수 n이 소수가 아니라고 해서, a^n-1 % n ≠ 1 이 성립하는 것은 아니다.

 

따라서 a^n-1 % n ≠ 1 인 경우가 한번이라도 발견되면 n이 소수가 아니라고 확신할 수 있지만, a^n-1 % n = 1 인 경우가 반복적으로 발견된다고 해서 n이 소수라고 확신할 순 없다.

심지어 1 < a < n인 모든 자연수 a에 대해 a^n-1 % n = 1 이 성립함에도, n이 소수가 아닌 경우가 있다. 이러한 자연수를 Carmichael Number 라고 한다. 다행히도 Carmichael Number를 걸러낼 수 있는 방법이 존재한다.

 

또한, n이 소수도 Carmichael Number도 아니라면, 1 < a < n인 a의 값 중 절반 이상은

a^n-1 % n ≠ 1 을 만족함이 증명되었다. (증명 생략)

 

위 사실을 바탕으로, 알고리즘은 다음과 같이 동작한다.

 

primalityTest (int n) {

먼저 n이 Carmichael Number인지 판단한다.

n이 Carmichael Number라면, n은 소수가 아니다.

1 < a < n을 만족하는 자연수 a를 랜덤으로 고른다.

a^n-1 % n = 1이 성립하는지 판단한다.

성립하지 않는다면, n은 소수가 아니다.

성립한다면, a를 고르는 행으로 돌아가 반복한다. k번째 반복이라면, n을 소수로 결론짓는다.

}

 

이 알고리즘은 n이 소수가 아님에도 소수라고 판단할 가능성이 있다. 그러나 매 판단마다 절반 이상의 확률로 소수가 아님이 확인되므로, 그 가능성은 1/2^k 로 매우 낮다.