Selection 이번에는 '선택'과 관련한 문제입니다. 만약 어떤 배열에서 '최소/최대'의 값을 구해야 한다면 배열을 한 번만 쭉 훑으면서 최소/최대의 값을 저장하면 되기 때문에 선형 시간이 필요할 것입니다. 즉, N만큼의 시간이 소요되죠. 하지만 배열에서 k번째의 값을 구하려면 이는 단순히 한 번 훑어보는 것으로 판단할 수 있는 문제가 아니게 됩니다. 정렬 후 k번째 값을 가져오면 되지만 이는 linearithmic, 즉 NlogN만큼의 시간이 필요한 작업입니다. 뭔가 비슷한듯 비슷하지 않은 두 방식에 대해서, 후자도 선형 시간으로 처리할 수 있지 않을까? 라는게 과거 학자들의 궁금증이었습니다. Quick-select import random def partition(a, lo, hi): i, j =..
