알고리즘 선택 문제 (Quick Select, MOM)

드럼치는치즈계란말이·2024년 11월 11일

상한과 하한 :

해당 알고리즘을 수행하기 위해서 alpha번의 기본연산이 반드시 필요하다면, alpha를 하한(lower bound), beta번의 기본연산만 하면 항상 최댓값을 찾을 수 있다면, 이를 상한(upper bound)라고 함. 두 값이 같다면, 알고리즘은 풀린거임. 참고로 상한값을 빅오 표기법으로 나타내고(O(f(n))), 하한값을 빅오메가 표기법으로 나타냄(Ω(f(n))). 둘이 같으면 빅세타 표기법(Θ(f(n)))으로 나타냄.

선택 문제 :

입력 : n개의 값, k (단, 1<=k<=n)
출력 : k번째로 작은 입력값 찾기
목표 : 비교 횟수 최소화

지금부터 볼 예시 : 선택문제 알고리즘이 필요없는 특이 cases

example1 : 최댓값 찾기(k=n)

하나의 값을 currentMax로 정하고 그걸 기준으로 array내의 다른 값들과 비교해가면서 다른 값이 더 크면 그 값을 currentMax로 대치하면서 구하기 -> 소요 비교횟수 : N-1
- 소요 비교 횟수 : N-1
- 토너먼트 방식으로 진행할 수도 있음. 이때에도 N-1번의 비교가 필요
- 최솟값을 찾는 예제 역시 같은 비교 횟수가 필요

example2 : 최대와 최솟값 동시에 찾기

최댓값을 먼저 찾고, 남은 값들로 최솟값 찾기.
- 각 과정은 각각 N-1번, N-2번의 비교가 필요 (총 2N-3번)
- 토너먼트 방식으로 하더라도 같은 비교 횟수 (최댓값 구한 후 나머지로 최솟값 구하기)

example3 : 최솟값과 그 다음으로 작은 값 찾기

최솟값 먼저 찾고 남은 값들로 그 다음으로 작은 값 찾기
- 이 역시 example2처럼 2N-3번의 비교가 필요
토너먼트로 최솟값 찾고, 최솟값과 겨뤘던 놈들중에 가장 작은 값 찾기
- 이러면 최솟값은 N-1번으로 찾고, 그 다음으로 작은 값은 총 라운드 값으로 구할 수 있음.
  - 만약 N=8이라면, log2(8) = 3으로, 최솟값을 찾기위해 총 3개의 라운드가 필요
  - 만약 N=15라면, 올림(log2(15)) = 4번의 라운드가 필요(부전승 고려)
  - 이말은 즉, 올림(log2(N)) 값이 두번째로 작은 값을 찾기위해 비교해야할 값들의 개수임.
    + 즉, 두번째로 작은 값을 찾기위한 비교 횟수는 "올림(log2(N))-1" 임.
- 따라서 총 비교 횟수는 N+올림(log2(N))-2

선택 문제 알고리즘 :

선택문제는 n개의 값 중 k번째로 작은 수를 찾는 것. 위와 달리 이젠 일반적인 k의 경우를 볼거임. 이를 위해 알려진 알고리즘은 대표적으로 두가지가 있음

Quick Select
MOM(Median of Median)

Quick Select 알고리즘

List 안의 하나의 랜덤한 값을 고른다 (pivot. 이하 p)
p와 List안의 다른 값들을 비교하여 p봐 작은 값, 같은 값, 큰 값을 서로 다른 List로 저장한다.
- A는 작은 값, M은 같은 값, B는 큰 값을 넣는 List
- 이때 A와 B는 각각의 List 안의 값들의 대소는 모르고 다만 p보다 작고, 크다는 것만 알고 있음
if len(A) >= k : -> k번째로 작은건 A안에 들어있기에, A에서 k번째로 작은 값 찾으면 됨
- 이는 1,2번 과정을 재귀적으로 하면됨. A라는 리스트에서 k번째로 작은 값 찾기
elif len(A)+len(M) < k: -> k번째로 작은건 B안에 들어있음. 고로 B에서 "k-len(A)-len(M)"번째로 작은 값을 찾으면 됨.
- 이 역시 1,2번 과정을 재귀적으로 하면됨. B라는 리스트에서 "k-len(A)-len(M)"번째로 작은 값 찾기
else: -> k번째로 작은 값은 p와 같은 값임(M안에 있음)
- return p

Quick Select pseudocode

def quick_select(L,k):
	P = L[0]	# pivot 설정
    A,B,M = [],[],[]
    for i in L:
    	if p>i:
        	A.append(i)
        elif p<i:
        	B.append(i)
        else:
        	M.append(i)
    if len(A) > k:
    	return quick_select(A,k)
    elif len(A)+len(M) < k:
    	return quick_select(B,k-len(A)+len(M))
    else:
    	return p

Quick Select 예시

Quick select 시간복잡도 : O(f(n))

worst case : L을 업데이트하면서 고른 pivot이 항상 L안에서 가장 큰 값이거나 가장 작은 값일 경우

T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

best case : L을 업데이트하면서 고른 pivot이 항상 중앙 값일 때

T(n) = n + T(n/2) = n + n/2 + n/(2^2) + ... + n/(2^(k-1)) + n/(2^k) = O(n)

average case : T(n) = O(n). 따로 증명은 하지 않겠음

MOM(Median of Median) 알고리즘

List 안에서 5개씩 그룹을 만든다 (일반적으로 5개의 그룹으로 나눔)
각 그룹의 중간 값들을 구함 (medians 구하기)
- 중간 값들이 총 5개이므로, 6번 비교시 항상 찾을 수 있음 -> 비교횟수 : 6n/5
n/5 개의 중간 값들 중에서 다시 또 중간 값을 구함 -> 2번 과정을 n/5 로 하기에 T(n/5)
3번을 통해 구한 m*가 pivot이 되어, quick select처럼 A,M,B로 나눔
- 이때 len(A) <= n/c 이며, len(B) <= n/c 임
quick select의 3번 과정을 거침 (MOM 재귀호출 or return m*)