[알고리즘 - 이론] The Selection Problem and the Adversary Argument (선택 문제와 적대적 논쟁)

선택 문제란 키가 n개인 리스트에서 k번째로 큰 (혹은 k번째로 작은) 키를 찾는 것이다.

여기서 키는 정렬되어 있지 않은 리스트에 있다고 가정한다.

먼저 k = 1일 때, 우리는 가장 크거나, 가장 작은 키를 찾으면 된다.

 

그런 다음에, 최소키와 최대 키를 동시에 찾으면서 각각 따로 찾는 경우보다 더 적은 비교 횟수를 가짐을 볼 것이다.

마지막으로 k = 2일 때, 두 번째로 큰 값, 혹은 두 번째로 작은 값을 찾아볼 예정이다.

---

1. Finding the Largest Key

 

 

problem : find the largest key in the array S of size n, indexed from 1 to n

outputs : variable large, whose value is the largest key in S

 

def find_largest(n: int, S: list) -> int:
    large = S[1]
    
    for i in range(2, n + 1):
        if S[i] > large:
            large = S[i]
            
	return large

이렇게 함수를 짠다면, T(n) = n - 1이 된다.

직관적으로 이 이상 성능을 향상하는 것은 불가능해 보인다.

이를 증명하기 위해서는 토너먼트 경기로 생각해서 알아볼 수 있다.

최대 키를 결정하기 위한 토너먼트 경기를 할 때 n - 1번의 경기를 해야 한다.

만약 n - 2번의 경기만 한다면, 비교되지 않은 최소 2개의 키가 존재하게 된다. 따라서 두 개의 키 중 하나는 최대 키로 보고될 수 없다.

 

따라서 키를 비교하여 주어진 리스트에서 가장 큰 키를 찾는 어떤 Deterministic Algorithm (결정적 알고리즘)이라도 최소 n - 1번의 비교를 해야 됨을 알 수 있다.

즉, n - 1 is a lower bound for the problem of finding the largest key임을 알 수 있다.

하지만 이는 모든 알고리즘이 적어도 n - 1번의 비교를 해야 한다는 뜻은 아니다. 만약 리스트가 정렬되어 있다면, 간단히 리스트의 맨 마지막 원소를 참조하면 될 것이다.

하지만 이는 가능한 모든 입력에 대해서 최대 키를 찾을 수 있는 것이 아니다. 따라서 가능한 모든 입력에서 최대 키를 찾기 위해서는 n - 1이 최소키를 찾는 하한이라는 사실을 증명할 수 있다.

 

---

2. Finding Both the Smallest and Largest Key

 

 

최대 키와 최소 키를 동시에 찾는 방법은 위의 알고리즘을 조금 수정하면 된다.

 

problem : find the smallest and largest key in list S

outputs : variable smallest and largest key in lsit S

 

def find_largest(n: int, S: list) -> int:
    large = S[1]
    small = S[1]
    
    for i in range(2, n + 1):
        if S[i] > large:
            large = S[i]
        elif S[i] < small:
            small = S[i]
            
    return large, small

확실히 이 알고리즘은 위의 독립적으로 찾는 것보다 좋다. 왜냐하면 어떤 입력에 대해서 S[i]와 small의 비교가 모든 i에 대해서 이루어지지 않기 때문이다.

따라서 수행 능력인 개선이 되었다.

 

만약 최악의 경우 S[1]가 최대 키가 된다면 맨 처음의 if문은 항상 False가 될 것이고, 키의 비교 횟수는 2(n-1)이 된다.

즉 W(n) = 2n - 2가 된다.

이는 최대, 최소를 독립적으로 찾는 경우와 비교 횟수가 정확하게 같다.

 

아무튼 우리는 이 이상 성능을 향상할 수 없는 것처럼 보이지만, 사실은 성능 향상이 가능하다.

 

모든 키를 짝을 지어서 찾으면 된다.

토너먼트처럼 짝을 지어서 작은 키를 찾는다. 이 작업은 n/2번 비교하여 이루어지고, 작은 키 가운데서 최소 키를 찾는데 n/2번 비교하면 된다.

또한 큰 키들 가운데 최대 키를 찾는 작업은 n/2번 비교하면 된다.

따라서 3n/2번의 비교만에 최대, 최소 키를 찾을 수 있다.

간단히 하기 위해 n이 짝수라고 가정했다.

 

이때 T(n)은 n이 짝수이면, 3n/2 - 2이고, n이 홀수이면 3n/2 - 3/2가 된다.

여기서 과연 성능을 더 향상할 수 있을까?

답은 아니오다. 

 

lower bound를 구하기 위해 adversary argument(적대적 논쟁)이라는 방법을 사용합니다.

---

3. Adversary Argument (적대적 논쟁)

 

 

만약에 당신이 Adversary가 된다면, 당신은 yes/no 질문에만 대답할 수 있다. 당신은 제대로 된 답을 알려줄 의도가 없으므로, 가능한 질문을 많이 하도록 유도해야 한다.

여기서 중요한 점은 당신이 대답할 때 이미 준 답과 일관성을 유지해서 답을 줘야 하다는 점이다.

따라서 당신의 답변의 목적은 최대한 많은 가능성이 남아있게 답변하는 것이다.

상대방이 최대한 논리적인 결론에 도달하기 전에 가능한 많은 질문을 할 수 있게 해야 된다는 것이다.

 

 

어떤 Adversary의 목표는 알고리즘이 최대한 비효율적이게 만드는 것이 목표라고 가정해보자.

알고리즘이 결정을 해야 하는 시점에 이 방해꾼은 최대한 알고리즘이 느리게 실행하게 하는 결정을 선택한다.

여기서 유일한 제한 사항은 이미 준 답과 언제나 일관성 있는 답을 해야 한다는 점이다.

이때 adversary가 알고리즘을 f(n)번 실행하도록 만들었다면, f(n)은 worst-case complexity의 lower bound가 되는 것이다.

 

 

이때 최대 키와 최소 키를 모두 찾는데 필요한 최악의 경우 비교 횟수 하한을 구하기 위해 adversary argument를 사용한다.

lower bound를 구하기 위해서는 키들은 모두 다르다고 가정한다.

비교만으로 최소 키와 최대 키를 찾는 문제를 푸는 알고리즘이 있다고 가정해보자.

 

이때 알고리즘을 실행하는 중에 키의 상태를 확인할 수 있는 방법은 다음 네 가지밖에 없다.

• X : 이 키는 아직 한 번도 비교하지 않았다.
• L : 이 키는 최소 한 번은 졌고, 한 번도 이기지 않았다.
• W : 이 키는 최소 한 번은 이겼고, 한 번도 지지 않았다.
• LW : 이 키는 비교에서 최소 한 번은 졌고, 최소 한 번은 이겼다.

이때 위 상태에서 얻을 수 있는 정보는 다음과 같다. 

X는 아직 정보가 하나도 없다. L, W는 최소 한 번은 비교에서 이겼거나 졌다는 사실을 알 수 있으므로 알 수 있는 정보가 하나이다.

만약 LW라면 비교에서 이기기도, 졌기도 했다는 사실을 알 수 있으므로 알 수 있는 정보는 두 가지다.

 

이때 small key는 최소이고, large key는 최대이므로, 이 둘을 제외한 다른 모든 키는 최소한 비교에서 한 번은 이기고, 한 번은 져야 한다.

따라서 알고리즘은 다음 개수만큼 의 정보를 알아야 한다. 

(n - 1 ) + (n - 1) = 2n - 2

 

이때 Adversary의 전략은 최대한 알고리즘에게 정보를 덜 줘야 하는 것이다.

 

간단히 예를 들어서 알고리즘이 방해꾼에게 s1과 s2의 대소를 물어봤다고 가정하자.

이때 방해꾼은 s1이 크다고 대답한다. (사실 뭐를 대답하던 상관은 없다. 왜냐하면 제공되는 정보는 어느 쪽이나 2개이기 때문이다.)

아무튼 s1은 W가 되고, s2는 L이 될 것이다.

따라서 알고리즘이 얻은 정보의 수는 2개가 된다.

 

이때 알고리즘이 방해꾼에게 s3와 s1을 비교한다고 가정하자.

만약 방해꾼이 s3가 크다고 하면 어떻게 될까?

s3는 W가 되고, s1은 LW가 될 것이다.

즉 정보 2개가 노출되었다는 뜻이다.

 

따라서 방해꾼은 s1이 크다고 말해야 한다.

그렇게 되면 s3는 L이 되고, s1은 W (원래 상태)가 됨으로써 노출되는 정보는 1개가 된다.

 

그러므로 방해꾼은 필연적으로 s1이 크다고 말해야 한다.

 

아무튼 이러한 방해꾼의 전략을 가지고 5개의 키가 있는 알고리즘을 최대한 방해해보자.

이때 알고리즘이 알아야 하는 정보는 총 8개다. (2 * 5 - 2)

참고로 해당 알고리즘은 다음과 같다.

def find_largest(n: int, S: list) -> int:
    large = S[1]
    small = S[1]
    
    for i in range(2, n + 1):
    	if S[i] < small:
            small = S[i]
        elif S[i] > large:
            large = S[i]
        
            
    return large, small

(참고로 위의 코드와는 small, large의 위치가 다르다)

(아래의 표에서 L/10 이라는 것은 Lose했고, 그 값이 10이라는 뜻이다)

비교	방해꾼의 답	s1	s2	s3	s4	s5	배운 정보의 개수
s2 < s1	s2	L/10	W/20	x	x	x	2
s1 > s2	s2	L/10	W/20	x	x	x	0
s3 < s1	s3	L/10	W/20	W/15	x	x	1
s3 > s2	s3	L/10	WL/20	W/30	x	x	1
s4 < s1	s4	L/10	WL/20	W/30	W/15	x	1
s4 > s3	s4	L/10	WL/20	WL/30	W/40	x	1
s5 < s1	s5	L/10	WL/20	WL/30	W/40	W/15	1
s5 > s4	s5	L/10	WL/20	WL/30	WL/40	W/50	1

위의 표를 보면 이해가 될지 잘 모르겠다.

중간 중간 키의 값이 바뀌지만, 일관성 있는 답을 위해서 일관성 있게 대답할 수 있게 값을 할당한 것이다.

즉, 최대한 알고리즘을 방해하면서 일관성 있는 답을 위해서 실시간으로 값을 할당한 것이라고 보면 되겠다.

 

중요한 건 위의 표를 보면 총 8번의 비교가 이루어졌고, 우리의 방해꾼이 알고리즘을 성공적으로 방해했다는 것을 알 수 있다.

---

4. Adversary Argument 정리

 

 

우리는 최대, 최소 값을 동시에 찾기 위해서는 2n - 2개의 정보가 필요하다는 것을 알게 되었다.

이제 나는 동시에 찾기 위해서 최소한의 비교 횟수에 대해 증명하려고 한다.

n이 짝수면 3n/2 - 2, n이 홀수면 3n/2 - 3/2를 증명할 것이다.

 

다시 한번 정리하자면, 알고리즘은 최대한의 정보를 얻으려고 할 것이고, 방해꾼은 최소한의 정보를 제공할 것이다.

이를 바탕으로 한 번 생각을 해보자.

 

(짝수일 때, 토너먼트 방식을 떠올리면 간단하다.)

알고리즘이 얻을 수 있는 최대한의 정보는 2개다.

따라서 최소한의 비교로 최대한의 정보를 얻는 방법을 무엇일까?

바로 이전 비교에 쓰이지 않은 키들에 대해서만 비교하는 것이다.

 

즉 n/2번 비교하는 방법이다.

이때 2개의 정보와 n/2개의 비교를 하므로 총 n개의 정보를 얻을 수 있다.

이후부터는 방해꾼은 최대 1개의 정보를 제공한다. (W과 W을 비교하면 한 개만 LW로 바뀜)

이제 남은 비교 횟수는 2n - 2 - n = n - 2개다.

 

따라서 방해꾼은 알고리즘이 최소한 n/2 + n - 2 = 3n/2 - 2번 비교를 하게 만들었다.

 

홀수일 때는 스스로 생각해보시면 될 것 같다.

 

아무튼 성공적인 방해꾼의 방해 덕분에 알고리즘은 아무리 방해를 받아도 3n/2 - 2번 보다 더 많이 비교를 할 수 없다는 것을 알게 되었다.

 

즉 이것은 이 문제의 lower bound가 된 것이고, 이 문제의 Computation Complexity를 성공적으로 증명해냈다.

---

5. Finding the Second-Largest Key

 

 

이제 두 번째 큰 키 (차대키)를 찾아보자.

일단 우리는 최대 키를 찾기 위해서 n - 1번 비교를 해야 한다.

그 후 최대 키를 제외하고 n - 2번을 비교하면 차대 키를 찾을 수 있다.

따라서 차대 키를 찾기 위해서는 2n - 3번의 비교를 해야 한다.

 

근데 직관적으로 봐도 분명 이것보다 더 개선할 수 있을 것 같은 느낌이 든다.

곰곰이 생각을 해보자.

최대 키가 아닌 다른 키에게 진 키는 과연 차대 키가 될 수 있을까?

정답은 아니다.

 

필연적으로 최대 키에게 진 키만이 차대 키가 될 자격이 주어진다.

즉 우승자와 경기한 애들 중에 차대 값이 있다는 뜻이다.

 

이는 토너먼트 방식을 떠올리면 쉽다.

 

최대 키가 a라고 하자. 이때 b와 c를 비교했는데, b가 더 크다고 한다.

그런데 과연 c가 차대 키가 될 수 있을까?

절대로 될 수가 없다. 왜냐면 c는 이미 b보다 작고, b는 a보다 작기 때문이다.

 

아무튼 이러한 방식을 통해서 처음 모든 키를 비교할 때는 n - 1번 비교를 해야 한다.

그렇게 함으로써 최대 키가 도출될 것이고, 이후 최대 키에게 진 키를 비교하기 위해서는 lg(n) - 1번의 비교를 해야 한다.

(왜냐하면 n개의 키가 있을 때, 토너먼트 (트리)의 높이는 lg n이 되고, 따라서 최대 키에게 진 키는 총 lg n개가 되기 때문이다.)

 

간단히 하기 위해서 n은 2의 제곱수라고 가정하였다.

즉 차대 키를 찾기 위해서 필요한 비교의 개수는 n + lg(n) - 2가 된다.

---

6. Finding the kth-Smallest Key

 

 

마지막 일반화를 하기 위해 k번째 작은 키를 찾기 위한 비교 횟수에 대해서 알아보겠다.

이쯤 되면 까먹었을 텐데, 우리가 이러한 비교 횟수를 왜 알려고 하냐면, 문제의 복잡도에 대해서 알기 위해서이다.

아~무리 빨리해도 최소한의 비교 횟수는 있을 것이고, 아~무리 느리게 해도 최대한의 비교 횟수는 있을 것이다.

 

아무튼 본론으로 들어가서 우리는 이제 k번째 작은 키를 찾는 방법에 대해서 공부할 예정이다.

편의를 위해 모든 키는 값이 다르다고 가정한다.

 

1. Quick Sort를 이용한 k번째 슬롯 찾기

 

퀵 소트에 대해서 안다고 가정하겠습니다.

만약 퀵 소트를 이용해서 k번째 슬롯을 찾을 때, 가장 최악의 경우는 무엇일까요?

아마 이미 리스트가 정렬되어 있을 때 가장 최악의 경우일 것입니다.

 

퀵 소트를 이용해서 k 번째 슬롯을 찾기 위해서는 총 k번의 분할을 해야 할 것이고, 

분할을 위한 비교 횟수는 n - 1, n - 2, ..., 1이 될 겁니다. (만약 k가 맨 끝이라면)

 

따라서 worst-case time complexity W(n)은 n(n-1)/2이 될 것입니다.

 

 

2. 입력이 동등하게 될 때

 

 

이제 다른 알고리즘을 한 번 생각해보자.

모든 입력은 동등하게 입력된다. 이 말은 곧 모든 k 값은 같은 빈도수로 들어가고, 모든 pivotpoint 값은 같은 빈도수로 반환된다는 뜻이다.

 

만약 첫 번째 재귀 호출에 0개의 입력이 들어간다면, 결과는 n개가 존재하게 된다. (남은 n개 중에 k개 있으므로)

만약 첫 번째 재귀 호출에 1개의 입력이 들어간다면, 결과는 2개가 존재하게 된다.

(k = 1이고, p = 2 혹은 k = n이고, p = n - 1이면)

만약 첫 번째 재귀 호출에 2개의 입력이 들어간다면, 결과는 2*2개가 존재하게 된다.

(k = 1 또는 2이며, p = 3이거나, k = n -1 또는 n이며, p = n - 2인 경우)

 

아무튼 이러한 방식을 쭉 따라 가다 보면 한 가지 점화식을 얻을 수 있는데, 

A(n) = 입력 크기 * 결과의 개수 / 각각의 발생 빈도수의 합

따라서 A(n) < A(n - 1) + 3, A(0) = 0이 된다.

 

즉 A(n) < 3n이므로, A(n) \(\epsilon \, \theta(n)\)이 된다.

 

 

3. median 값을 이용한 quick sort

 

 

퀵 소트를 할 때 가장 좋은 방식은 무엇일까? 바로 pivotpoint가 리스트를 정확히 반으로 자르는 게 가장 좋을 것이다.

그러기 위해서는 median 값을 알아야 하는데, 중앙값을 찾는 것 자체가 시간 복잡도가 크다.

하지만 항상 median 값을 pivotpoint로 선택할 수 있다면, 성능이 최적일 것이다.

 

하지만 median은 어떻게 구할까?

예를 들어 15개의 key가 있다고 가정해보자.

이때 15개의 키를 5개의 키로 나누어 3개의 그룹을 만든다.

 

그렇게 된다면 각각의 그룹에서 median 값을 구하는데 드는 비교 횟수는 6번이 된다. 

 

위 방식을 통해 3개의 그룹에서 3개의 median이 나오게 되는데, 여기서 median 들의 median을 찾는다.

이때 이 median은 15개의 리스트의 median이 아닐 수도 있지만, 실제 median에 꽤 근접한 값이 될 것이다.

 

아무튼 median of medians에서 한쪽에 올 수 있는 키의 개수는 최대한 7n/-10 - 3/2와 같다.

위의 식을 통해서 k 번째 값을 찾기 위해 필요한 시간 복잡도는 W(n) <= 22n이므로 W(n) \(\epsilon \, \theta(n)\)이 된다.

최악의 경우에도 1차 식으로도 문제를 해결할 수 있게 되었다..

 

 

4. Probabilistic Algorithm for the Selection Problem

 

 

지금까지는 알고리즘의 lower bound를 구할 때 그 알고리즘이 deterministic이라고 가정했다.

그러나 lower bound가 probabilistic일 때도 성립한다는 것도 알 수 있다.

 

이제 우리는 uniform distribution에서 pivot item을 랜덤으로 뽑을 것이다.

그렇게 되면 pivotpoint는 끝점에 가까워지기보다는 멀어질 것이다.

따라서 모든 입력에 평균적으로 랜덤을 적용하면 기대치는 1차 시간이 됨이 틀림없다.

 

아무튼 세 개의 대표적인 랜덤 알고리즘을 알아보자.

• Monte Carlo Algorithms
  • 반드시 맞는 답을 주지는 않는다.
  • 하지만 답의 추정치를 제공하고, 알고리즘의 사용 시간이 증가할수록 커진다.
  • ML 카테고리의 Reinforcement Learning에 자세히 설명해놓았다.
• Sherwood Algorithms
  • 항상 맞는 답을 준다.
  • 최악의 경우보다는 평균의 경우 훨씬 빠르게 실행되는 deterministic algorithm에 적합하게 쓰인다.
• Las Vegas Algorithms
  • 항상 맞는 답을 준다.
  • 하지만 종종 답을 주지 않는 경우가 있다.

아무튼 모든 pivotpoint가 동등하게 선택된다면 E(n, k) <= 4n \(\epsilon \, \theta(n)\)이 된다.

이때 k와 상관없이 항상 1차 시간을 가지게 된다.

 

 

 

 

감사합니다.

 

 

지적 환영합니다.