선택 문제

Song_MinGyu·2022년 4월 9일

algorithm

Algorithm

목록 보기

10/30

선택문제(Selection problem)

선택 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제.

간단한 해결 방법
1. 최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다. ⇒ $O(kn)$
2. 최소 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는다 ⇒ $O(nlogn)$

⇒오래걸리는 문제점 발생

선택 문제는 숫자 찾기 문제, 따라서 임의의 숫자를 효율적으로 찾는 이진 탐색에서 아이디어를 찾을 수 있다.

피봇 값을 탐색하여 작으면 small group에서 다시 찾거나 피봇 값이 크다면 Large group에서 찾는 방법을 이용한다.

Pesudo Code

Selection(A,left,right,k)
	입력: A[left]~A[right]와 k, 단 1<=k<=|A|=right-left+1
  출력: A[left]~A[right]에서 k번째 작은 원소
	피봇을 A[left]~A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후 피봇과 배열의
	각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자는 
  A[p+1]~A[right] 로 옮기며, 피봇은 A[p]에 놓는다.
	S=(p-1)-left+1
	if (k <= S) Selection(A,left,p-1,k)
	else if (k=S+1) return A[p]
	else Selection(A,p+1,right,k-S-1) // small group을 전부 제거하므로 그만큼 땡겨줘야함

수행과정

최초로 Selection(A,0,11,7) 호출 ⇒ A 리스트에 0번부터 11번(끝)까지 7번째로 큰 요소 탐색

1번 라인에서 피봇을 결정하고 left와 스왑

left에서 right가 교차되도록 서치를 시작함 탐색을 진행하면서 피봇보다 큰건 오른쪽으로 작은건 왼쪽으로 스왑한다. 그리고 left와 right가 교차하면 서로 만나는 지점(p)를 피봇과 교체한다.

small group의 크기보다 찾고자하는값(k)가 더 크다면 large group을 찾도록 해야한다.

large group에서또한 동일한 작업을 반복한다.

이하 반복

알고리즘 고려 사항

Selection 알고리즘은 분할 정복 알고리즘이기도 하지만 랜덤(Random) 알고리즘 이기도 하다.
- 왜? ⇒ 피봇을 랜덤하게 지정하기 때문이다.
따라서 피봇의 결정 또한 시간 복잡도에 영향을 미치는데,
- Small group << Large group 또는 Small group >> Large group일 때에는 알고리즘의 수행시간이 길어진다.

Good/bad 분할 정의

분할된 두 그룹 중의 하나의 크기가 입력 크기의 3/4과 같거나 그 보다 크게 분할하면 나쁜 분할이라고 정의하자.
좋은 분할은 그 반대의 경우
즉 적절하게 분할된 작업은 시간을 크게 줄이지만, 좋지 않은 분할은 시간 효율성이 떨어지게 된다.

시간 복잡도 정리

피봇을 랜덤하게 정했을 때 good 분할이 될 확률이 절반으로 평균 2회 연속해서 랜덤하게 피봇을 정하면 good 분할이 가능하다.
매 2회 호출마다 good 분할이 되므로, good 분할만 연속하여 이루어 졌을 때만 시간 복잡도를 구하여 그 값에 2를 곱하면 평균 경우 시간 복잡도를 얻을 수 있다.
$n+3/4n+(3/4)^2n+(3/4)^3+...+(3/4)^i-1n+(3/4)^in <= 4n$ 으로, $O(n)$ 이 된다.