[신찬수 교수님] 4. 선택(Selection) 문제

선택(Selection) 문제

입력 : n개의 값과 k (1 <= k <= n) 값

출력 : k번째로 작은 입력 값

목표 : 비교 횟수 최소화

 

예 : K가 특별한 경우

k = n : 최대값 찾기

최대값 찾기 같은 경우는 n - 1 번 비교를 해야한다.

- 왼쪽부터 하나씩 비교해도 n - 1

- 토너먼트 방식으로 비교해도 n - 1

n - 1번의 비교로 최대값 찾기가 가능하다면 상한(Upper bound) -> 원하는 값을 찾기 위해 일정 횟수면 충분하다.

최소 n - 1번의 비교가 필요한 경우는 하한(Lower bound) -> 어떤 알고리즘도 최소 일정 횟수만큼 비교를 해야한다.

상한과 하한이 같다면 최소한의 비교 횟수로 원하는 값을 찾을 수 있다는 뜻이다. -> 완전히 풀림

 

k = 1, n : 최대값, 최소값 찾기

- 왼쪽에서부터 하나씩 비교하면 2n - 3

n - 1 번 비교 -> 최대값

n - 2 번 비교 -> 최소값

 

- 토너먼트 방식으로 비교하면 3/2n - 2 -> 상한, 하한

n - 1 번 비교 -> 최대값

토너먼트 1차전에서 탈락한 n / 2에서 비교를 해 (n / 2) - 1 번 비교 -> 최소값

 

k = 1, 2 :  제일 작은 값, 두번째로 작은 값

- 왼쪽에서부터 하나씩 비교하면 2n - 3

최소값 -> n - 1 번 비교

두번째로 작은 값 -> n - 2번 비교

 

- 토너먼트 방식으로 비교하면 3/2n - 2

최소값 -> n - 1 번 비교

두번째로 작은 값 -> 최소값과 만나서 진 값들 중에서 두번째로 작은 값이 있으므로 (round수 - 1)번 == n - 올림(log2n) - 2

 

 

quick selection 알고리즘

1. p(pivot)를 고른다.

  - 랜덤하게, 가장 첫 번째, 가장 마지막 번째 등 아무렇게나 고를 수 있다.

2. p와 다른 값을 일일이 비교하여 끼리끼리 모은다. -> n - 1 번 비교

  - A = { p보다 작은 값 }, B = { p보다 큰 값 }, M = { p와 같은 값 }

3. k번째로 작은 것을 찾고 싶을 때

3 - 1. A에 들어가 있는 값들의 갯수가 k보다 크다면 k번째로 작은 값은 A에 들어있다. -> k보다 작은 값은 M과 B에는 없다.

  A에서 k번째로 작은 값 == 전체에서 k번째로 작은 값

A에서 k번째로 작은 값은 재귀적으로 찾는다.

 

3 - 2. A와 M의 값들의 갯수를 더한 수가 k보다 작으면 B에서 찾아야한다. 이 때는 k - (A와 M의 갯수)번째로 작은 값을 찾는다.

3 - 3. k보다 작은 값이 A에도 없고 B에도 없다면 M에 있다. M은 p와 같으므로 p를 리턴하면 된다.

def quick_select(list, k):
  p = list[0] # 1.
  A, B, M = [],[],[]
  for x in list: # 2.
    if p > x:
      A.append(x)
    elif p < x:
      B.append(x):
    else:
      M.append(x)
  if len(A) > k: # 3.
    return quick_select(A, k) # 재귀적으로 호출되다가 p가 return 될테니 마지막에도 다시 return 해줘야 한다.
  elif len(A) + len(M) < k:
    return quick_select(B, k - len(A) - len(M))
  else:
    return p

 

임의로 선택한 pivot에 따라서 상황이 좋을 수도 있고 안 좋을수도 있다.

worst case에 대한 시간은 T(n) = n(n+1)/2 = O(n**2)

best case에 대한 시간은 T(n) = n(1 + 1/2 + ... + 1/2**k) = 괄호 안은 다 더해도 2가 되지않으므로 2n = O(n)

average case는 O(n)이 된다.

 

 

MoM (median of medians) 알고리즘

1. A나 B의 갯수가 n/c보다 작을 수 있도록 비교 횟수 p를 사용해 pivot을 잘 고른다.

2. pivot을 고르고 나머지 값들 전부와 비교를 하는 n번의 비교 횟수가 필요하다. O(nlogn)

 

MoM(L, K)

1. 5개씩 그룹을 짓고 -> 그룹수 : n/5

2. 각 그룹의 중간값(median)을 구한다. -> n/5 * 6 비교

3. 중간값을 모은 중간값들(medians) 중에 중간값을 구한다.

m* = MoM(medians, medians/2) -> 재귀적으로 본인을 호출

4. quick selection 처럼 A와 m*와 B와 비교한다. -> n번 비교

5. 재귀 호출하거나 m*를 리턴한다.

T(n) = T(n/c) + T(n/5) + 11/5n = T(3/4n) + T(n/5) + 11/5n

 

시간을 계산하는 방법은 나열해서 구하는 방법도 있지만 추측해서 귀납법(Induction)으로 계산하는 방법도 있다.

T(n) <= 44n = O(n)

---

모르겠어요 교수님.... 일단 넘어갈게요.... 수학 공부 더 하면 다시 볼게요...

폭포같은 눈물을 흘리는 나