<보기>는 배열 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: 왼쪽 구간은 시작점이 같아 순위가 줄어들지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기