[Algorithm] 정렬: 계수 정렬, 선택 문제
+ 항공대학교 이인복 교수님의 알고리즘 해석 및 설계 과목 내용를 정리한 글입니다. 계수 정렬 (counting sort) - 범위가 작은 수들을 빠르게 정렬할 때 사용된다. 1. 각 수가 나온 횟수를 센다. (자신보다 작은 원소의 개수를 센다.) 2. 1 결과를 이용하여 각 수보다 작은 숫자가 몇 개 있는지 센다. (누적합 이용) ex) {5, 9, 3, 6, 9, 5, 2, 10, 1} 1. 하나의 숫자를 찾아갈 수 있는 시간을 Θ(1)이라고 가정할 때, 각 숫자가 나온 횟수를 세는데 Θ(n) 2. 다시 숫자를 정렬된 리스트에 채워넣는데 Θ(n) => Θ(n) ex) {12387, 90123, 39735, 9012344} - (최대값 - 최소값)의 범위 수..
