Selection Algorithm   선택 알고리즘, 선택 문제

1. 선택 알고리즘 (Selection Algorithm) 

  ㅇ 주어진 데이터 집합에서 특정 순위(order)의 원소를 찾는 알고리즘

  ㅇ 목적
     - 전체 정렬 없이도, 최솟값, 최댓값, k번째 작은(큰) 값 등을 효율적으로 찾기 위함

  ㅇ 특징
     - 값의 존재/위치가 아니라 순위에 관심
     - 전체 정렬(O(n log n))보다 보통 더 효율적
     - 문제에 따라 다양한 방법 사용

  ㅇ 대표 방법
     - 단순 선택 (선형 탐색)
        . 한 번 순회하며 최솟값/최댓값 갱신
        . 시간복잡도 : O(n)
     - 분할 기반 선택 (Quickselect)
        . 피벗 기준으로 분할 반복하여 k번째 원소 탐색
        . 시간복잡도 : 평균 O(n), 최악 O(n2)

  ㅇ 적용
     - 통계량 계산 : 중앙값(median), 분위수(percentile) 등


2. 최대 최소 구하기 例)

  ㅇ 가장 큰 숫자를 기억해가며 진행함 
          
int maximum( int arr[], int n ) {

    int max, i;

    max = arr[0];
    for ( i=1; i<n; i++ )
        if ( arr[i] > max )
            max = arr[i];

    return max;

}