선택(Select)

Select

Contents

정렬반을 졸업한 소년 빌게이츠는 정렬과는 다른 새로운 문제를 만났다. 문제는 n개의 원소가 아무런 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾는 것이다. 이러한 문제를 다루는 알고리즘을 선택 알고리즘이라 하는데 평균적으로 선형시간(O(n))이 걸리는 선택 알고리즘은 다음과 같다. 

select(A[], p, r, i) //배열 A[p..r]에서 i번째를 찾는다.

{

   if(p == r) return A[p];

   q = partition(A, p, r); //QuickSort에서 partition과 같음

   k = q - p + 1;

   if(i < k) return select(A, p, q - 1, i);

   else if(i > k) return select(A, q + 1, r, i - k);

   else return A[q]; //i == k

}

빌게이츠는 QuickSort와 동일하게 다음과 같은 방법으로 partition을 할 때, 배열 내 원소들 사이의 교환 회수를 측정하기로 했다.  

partition(A[], p, r){

   x = A[r];

   i = p - 1;

   for j = p to r - 1

      if(A[j] ≤ x) swap(A[++i], A[j]);

   swap(A[i+1], A[r]);

   return i + 1;

}

 

Input

첫 줄에는 원소의 개수 n(1<=n<=10000)와 몇 번째 원소를 선택할 것인지 가리키는 인덱스 i (<=n)가 들어온다.

그 다음 줄에는 n개의 임의의 정수가 들어온다.

Output

i번째 숫자를 찾기 위해 배열 내 원소들이 교환 되는 횟수를 출력한다.

Sample Input

10 3

4 3 7 8 0 5 2 1 6 9 

 

Sample Output

21

=================================================================

Linear Select

Contents

소년 빌게이츠는 배열 내 i번째 원소를 O(n)에 찾아낼 수 있어서 스스로 너무 자랑스러웠다. 그러나 어제 익산에서 전학 온 소년 스티브 잡스는 빌게이츠의 소스를 보자마자 특정 상황에서는 O(n^2)이 될 수 있음을 알아챘다. 스티브 잡스는 코피를 쏟아가며 연구를 한 끝에 최악의 경우에도 O(n)에 수행 할 수 있는 select 알고리즘을 찾아 냈다. 스티브잡스가 생각해낸 알고리즘은 다음과 같다. 

linearSelect(A, p, r, i){

  1. 원소의 총 수가 5개 이하이면 원하는 원소를 찾고 알고리즘을 끝낸다. 

     (원소를 찾기 위해서 select함수를 사용한다.)

 

  2. 전체 원소를 5개씩의 원소를 가진 ceil(n/5)개의 그룹으로 나눈다.

     (원소의 총수가 5의 배수가 아니면 이 중 한 그룹은 5개 미만이 된다.)

     (ceil은 소수점 첫째자리에서 올림을 수행하는 함수이다. )

 

    2.1 여기서 중앙값을 담을 배열 B를 ceil(n/5)만큼 확보한다. 

 

  3. 각 그룹에서 중앙값(원소가 5개이면 3번째 원소)을 찾는다.

     이렇게 찾은 중앙값들을 m_1, m_2, ..., m_[n/5]라 하자. 

     각 원소를 배열 B에 담는다.

 

    3.1 마지막 그룹의 개수가 4개 일 때는 2번째, 2개일 때는 1번째,

        나머지 홀수개에 대해서는 정가운데 원소를 중앙값이라 한다.

 

    3.2 각 그룹에서 중앙값을 선택 할 때는 select 문제에서 사용 했던 select 알고리즘을 써야한다.

        select 알고리즘에서는 아래 partition 함수를 이용해야한다.

  

  4. 3번에서 중앙값을 담은 배열 B 중에서 다시 중앙값 M을 재귀적으로 구한다. 

     배열 B의 원소의 개수를 t개 라고 하자.

    ▷ M = linearSelect(B, 0, t - 1, ceil(t/2))

 

    4.1 배열 B에서 중간의 위치는 ceil(t/2)로 한다. 

    

    4.2 M값을 이 단계에서 출력한다. 

 

  5. M을 기준원소로 삼아 전체 원소를 분할한다. 

     (M보다 작거나 같은것은 왼쪽에, M보다 큰 것은 M의 오른쪽에) 

    ▷ q = partitionByMedian(A, p, r, M)

 

  6. 분할된 두 그룹 중 적합한 쪽을 선택해 1 ~ 6단계를 재귀적으로 반복 

    ▷ call linearSelect

}

5번의 M을 기준 원소로 파티션을 할 때는 다음과 같이 해야 한다.

partitionByMedian(A[], p, r, M){

   // i = A[p..r]에서 M의 인덱스를 찾아 반환

    

   swap(A[i], A[r]); // M의 인덱스의 값과 마지막 원소와 교환

 

   //아래와 같은 방법으로 partition 수행

   return partition(A, p, r)

 

}

partition은 아래와 같이 마지막 원소를 기준으로 해야한다.

partition(A[], p, r){

   x = A[r];

   i = p - 1;

   for j = p to r - 1

      if(A[j] ≤ x) swap(A[++i], A[j]);

   swap(A[i+1], A[r]);

   return i + 1;

}

스티브 잡스는 위 코드가 제대로 동작하는지 알기 위해서 원소를 선택하는 과정에서 찾는 중앙값(M, 4번 과정에서)들을 출력하기로 했다. 

Input

첫 줄에는 원소의 개수 n (1<=n<=10000)과 몇 번째 원소를 선택할 것인지 가리키는 인덱스 i(<=n)이 들어 온다. 

그 다음 줄에는 n개의 임의의 정수가 들어온다.

Output

i번째 숫자를 찾기 위해 찾는 중앙값(M)들을 한 줄씩 출력한다.

Sample Input

10 3

4 3 7 8 0 5 2 1 6 9 

 

Sample Output

4

Sample Input

33 5

1 2 55 41 69 85 32 68 20 7 45 54 86 99 102 31 22 77 44 50 52 89 61 37 6 9 78 46 28 23 94 56 11

 

Sample Output

28

41

44

11