경주마 문제를 일반화 하면, 정렬되지 않은 숫자 n개에서 k번째로 큰 수를 찾는 방법임.


어떻게 풀까 생각해보면 가장 간단한 방법은 n개를 정렬해서 k-1번째 인덱스에 있는 원소를 고르는 거겠지. O(N*logN) 정도 걸림.


다른 방법은 숫자들끼리 토너먼트를 시키는 건데, 숫자들끼리 토너먼트를 시키다보면 1등이 결정됨



1등은 토너먼트의 승자임.

그렇다면 2등은 어떻게 구하냐? 결승전에서 패한놈인가? 

위 그림을 보면 알겠지만, 1차전에 90이란 숫자가 있음. 즉 결승전에서 패한놈이 반드시 2등이 되는게 아님.

그렇다면 2등은 어떻게 구하느냐?

2등은 1등과 겨루었던 애들 중에서 나오게 되어있음.

즉 10과 30 과 90 중에서 나오게 됨.

그렇다면 3등은? 1등과 2등이랑 겨루었던 애들 중에서 나오게 됨.

이런 식으로 하면 정렬하지 않고도 빠르게 풀 수 있음.


대략적으로 logN번 보다 약간 더 많이 나옴. 몇 번째 까지냐에 따라 수가 더 크게 되는데.. 더 자세하게 설명하지 못해서 ㅈㅅ;



-이상.. 오랜만에 아는게 나와서 설명충 빙의함-