[Algorithm] 선택문제 알고리즘 (feat. Quick-Sort)

선택문제?

• n개의 숫자들 중에서 k번재로 작은 숫자를 찾는 문제

 

💡어떻게 해결하면 좋을까?

• 첫번째 방법 : 순차탐색! 최소숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거
  • 숫자제거 = 추가 수행시간 + 추가 메모리 필요
  • O(kn) -> 최악의 경우, n번의 순차 탐색 ! 주어진 숫자 개수 n이 크면 커질 수 있다.
• 두번째 방법 : 숫자들을 정렬한 후, k번째 숫자를 찾는다.
  • O(nlogn)
• k가 작을 경우, 1번 방법이 유리
• 그렇지 않을 경우, 2번 방법이 유리

 

 💡아이디어

• 이진탐색 활용 : 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중에서 한 부분만을 검색
• 선택문제는 입력이 정렬되어 있지 않아서, 입력 숫자들 중에서 (퀵정렬에서와 같이) pivot을 선택하여 분할
  • small group 피봇보다 작은 숫자 그룹
  • large group 피봇보다 큰 숫자의 그룹
• small 그룹에서의 원소개수(그룹의 크기)를 구해서 k번째 작은 숫자가 어디에 있는지 찾는다.
  • small 그룹에 k번째 작은 숫자가 속하는 경우 : k번째 숫자를 small 그룹에서 찾는다.
  • large 그룹에 속하는 경우 : (k-|Small group|-1)번째로 작은 숫자를 large 그룹에서 찾는다.

 

💡 C++ 실행코드

#include <iostream>
#include <cstdlib> //rand 함수 사용<
#include <time.h>
using namespace std;

int n=9; //array_size

void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int Selection(int A[], int left, int right, int k){

    /* 정렬 !!!!!! */
    int pivot;
    int low;
    int high;

    int pivot_lo; // A[] 중 랜덤하게 정할 pivot index
    pivot_lo = (rand() % right-left+1)+left;
    
    pivot = A[pivot_lo]; // 피봇 랜덤하게 설정

    swap(&A[pivot_lo], &A[left]); //피봇과 A[left]의 자리를 바꾼다

    low = left;
    high = right + 1;

    //퀵 정렬과 같다
    // 전체 do-while 문 : low와 high가 교차할 때까지 반복 = 교차할 경우 stop!!
    do{

        //low를 먼저 증가시키면서 시작
        //low가 right보다 작거나 같고 && list[low]가 pivot보다 작을 경우 동안 반복
        do{
            low++;
        }while(A[low]<pivot && low<=right);

        //high를 먼저 증가시키면서 시작
        //high가 left보다 크거나 같고 && list[high]가 pivot보다 클 경우 동안 반복
        do{
            high--;
        }while(A[high]>pivot && high>=left);

        // 내부 두개의 do-while 문을 거쳐서 나온 low와 high의 값에서
        // low와 high가 교차하지 않는다면, 두 list[low]와 list[high]의 값을 바꾸어 준다.
        if(low<high){
            swap(&A[low], &A[high]);
        };

    }while(low<high);
    //low와 high가 교차했으면, list를 빠져나와 pivot과 list[high]를 교환한다.
    swap(&A[high], &A[left]);

    pivot_lo = high; // high가 pivot의 위치임



    /* k번째 위치 비교 !!!!!! */

    int s; // small group의 크기

    s = (pivot_lo-1)-left+1;

    if(k<=s) Selection(A, left, pivot_lo-1, k); // small group에서 찾기
    else if(k==s+1)  return A[pivot_lo]; // pivot = k번째 작은 숫자
    else Selection(A, pivot_lo+1, right, k-s-1); //large group에서 찾기

}

int main(){
    srand(time(0));
    int k; // 몇번째의 숫자를 찾고 싶은지?
    int list[9] = {5, 3, 8, 4, 9, 1, 6, 2, 7};
    cout << "몇번째 숫자를 찾고 싶나요? : ";
    cin >> k;
    
    int answer;
    answer = Selection(list, 0, n-1, k);

    cout << answer << endl;
}

 

---

💡시간 복잡도

• Pivot을 정하고 partition 하고자 할 때, pivot 배열 값과 배열내 모든 값과 비교하여 partition을 하는 경우 고려하면!
  • (k번째 최소 숫자찾기 -> 최소 숫자를 k번 찾는다 -> O(kn))

1️⃣ 최선의 경우

• 처음 한번 partition 했을 때, pivot point가 k인 경우
• n-1번 비교한후, partition 되므로, B(n) = n - 1
  • n-1 ? pivot 하나를 제외하고 그 pivot과 나머지 n-1개를 비교
• B(n) = n - 1

2️⃣ 최악의 경우

• 크기가 1이 될때까지 partition을 진행하고 크기가 1이면 그 위치가 k번째 원소일 경우
• n개의 입력이 non-decreasing order로 정렬되어 있고, n번째 원소를 찾는 경우
• pivot을 계속 가장 작은 경우로 잡아서 한쪽으로 치우치는 경우
• partition에서 전체 비교횟수는 (n-1) + (n-2) + ... + 1 = n(n-1)/2
• W(n) = O(n^2)

3️⃣ 평균의 경우

• 선택 알고리즘은 pivot을 랜덤하게 정해 pivot에 따라 입력 리스트의 분할이 결정된다. -> pivot에 따라 알고리즘의 수행시간이 변경
• 만일 피봇이 입력리스트를 너무 한쪽으로 치우치게 분할하면 -> 알고리즘의 수행시간이 길어진다.
  • 그런데, 선택 알고리즘이 호출될 때마다 line1 에서 입력을 한쪽으로 치우치게 분할될 확률은 1/2해도 무방
• Good 분할 : 분할될 두 그룹중의 하나의 크기가 입력크기의 3/4보다 작게 분할
• Bad 분할 : 분할될 두 그룹중의 하나의 크기가 입력크기의 3/4보다 크거나 같게 분할
  • 이 Good / Bad 분할을 얻을 확률은 반반!
  • 따라서 평균 2회 연속해서 랜덤하게 pivot을 정하면 good 분할을 할 수 있다.
• 즉, 매 2회 pivot을 호출마다 good 분할이 되므로, good 분할만 연속하여 이루어졌을 때만의 시간을 구하여 그 값에 2를 곱하면 평균 시간복잡도를 얻을 수 있다.

 

• 따라서, Good 분할이 반복될 경우, list 크기가 n에서부터 3/4배로 연속적으로 감소되고, 리스트 크기가 1 일때 분할과정이 멈춘다.
• Selection 알고리즘의 평균 시간 복잡도 A(n)
  • = 2[n + 3/4n + (3/4)2n + (3/4)3n + ... + (3/4)i-1n + (3/4)in]
  • = 2n[1+3/4+3/4(2)+ ... (3/4)i]
  • = O(n)

---

 

💡응용

• 선택알고리즘은 정렬을 하지 않음
• 따라서 데이터 분석을 위한 중앙값(median)을 찾는데 활용된다.
• 중앙값이 평균값보다 더 설득력있는 데이터 분석을 제공

 

 

 

Reference

• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업
• https://yexjinitlog.tistory.com/4