특수한 선택 문제
다음과 같은 요구 조건을 가지느 문제들은 선택(Selection)문제라고 보면 된다.
- 입력 : n개의 값과 k(1<=k<=n) 값
- 출력 : k번째로 작은 입력 값
- 목표 : 비교 횟수 최소화
상한(upper bound) : 어떤 결과를 찾아내는데 항상 임의 횟수의 연산이면 무조건 찾아낼 수 있다.
하한(lower bound) : 어떤 결과를 찾아내는데 임의 횟수의 연산이 반드시 필요한 경우가 존재한다.
상한과 하한이 같은 경우가 해당 문제를 해결하는 적절한 알고리즘!
k = n : 최대값 찾기
현재 최대값을 따로 변수로 저장해놓으면서 하나씩 비교해보면 된다. ->항상 n-1번 비교로 가능(상한 upperbound)
혹은 이웃한 두쌍이 비교해서 큰 값이 토너먼트 방식으로 비교 -> n-1번 비교로 가능
최대값찾기는 무조건 n-1번 연산이 알맞은 알고리즘이다.
k=1, k=n : 최대값, 최솟값 찾기
먼저 토너먼트 식으로 최대값을 찾고(n-1번 비교)
첫 비교에서 진 요소들(n/2개)끼리 다시 최소값 찾는 토너먼트를 실행(n/2-1번 비교)
총 (3/2)n-2번 비교!
k=1, k=2 :최솟값과 두번째로 작은 값찾기
먼저 작은 값이 이기는 토너먼트로 최솟값 찾고(n-1번 비교)
토너먼트에서 최대값에게 진 값들만 모아서 다시 비교! (라운드 수-1 번=logn올림 -1번)(매 라운드마다 패배자가 발생하므로…)
총 n-2-log2올림번 비교!