Hippo's data

오늘은 선택문제(Selction Problem)에 속하는 Median of medians 알고리즘에 대해 알아보겠습니다! 지난번에 선택문제에 대해 다뤘었는데욥 다시 복습하자면선택문제란, k번째로 작은(또는 큰) 요소를 찾는 문제입니다!  해당 문제를 해결하는 방법에는 여러 전략이 존재하는데욥 1) 매번 큰 값을 찾아 k번째 큰 값을 찾기가장 쉽게 생각할 수 있는 전략이다매번 큰 값을 찾아 총 k번 큰 값을 찾으면, k번째로 큰 값을 찾을 수 있다 총 비교횟수를 생각해보면1st max : n-12nd max: (n-1) + (n-2) = 2n-33rd max: (n-1) + (n-2) + (n-3) k번째 max: (n-1) + (n-2) + (n-3) + ... + (n−k)  등차수열의 합: 항의개수k..