<보기>는 배열 arr에서 k번째로 작은 원소를 찾는 알고리… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
<보기>는 배열 arr에서 k번째로 작은 원소를 찾는 알고리즘이다. (가), (나)에 들어갈 내용으로 가장 옳게 짝지은 것은? (단, partition(arr, p, r) 함수는 탐색 구역의 시작 인덱스 p부터 끝 인덱스 r 사이에서 피벗(pivot)을 기준으로 피벗보다 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 재배치하는 분할을 수행한 후, 피벗의 최종 위치 인덱스를 반환한다.)<보기>select(arr, p, r, k) if p == r return arr[p] q←partition(arr, p, r) i←q - p + 1 if k == i return arr[q] else if k < i return select(arr, p, q-1, (가) ) else return select(arr, q+1, r, (나) )
1
(가) k (나) k − i
2
(가) k (나) k
3
(가) k − i (나) k − i
4
(가) k − i (나) k
해설
(가)에는 k, (나)에는 k − i가 들어간다.
i는 피벗이 구간 [p, r]에서 몇 번째로 작은지를 나타내며, 왼쪽 구간 [p, q−1]에는 피벗보다 작은 원소 i−1개가 있다.
k < i이면 찾는 원소가 왼쪽 구간에 있고 순위도 그대로 k번째다. k > i이면 왼쪽 원소와 피벗을 합한 i개를 건너뛰므로 오른쪽 구간에서는 k − i번째가 된다.
- (나)에 k: 오른쪽 구간에서는 앞선 i개가 빠졌으므로 순위를 그대로 쓰면 다른 원소를 찾는다.
- (가)에 k − i: 왼쪽 구간은 시작점이 같아 순위가 줄어들지 않는다.
오류나 개정된 내용이 보이면 알려주세요