오늘 공부한 내용
Baekjoon Online Judge의 10989문제의 풀이에서 사용한 계수정렬(Counting sort)에 대해서 정리를 해본다.
계수정렬은 O(N)의 시간복잡도를 갖는다.
계수 정렬을 사용하려면 정렬 대상 배열의 최소값과 최대값을 알고 있어야 한다. 최대값만큼 최대 길이를 설정해서 별도의 리스트를 생성해야 되기 때문이다.
정렬 이름대로 요소의 값에 해당하는 index의 위치에 요소의 갯수만큼 카운트해서 값을 증가시켜 주는 형태를 갖는다.
예를 들어 [1, 5, 1, 5, 6] 이라는 리스트가 있다고 가정하자.
총 5개의 숫자, 최소값은 1, 최대값은 6이라는 전제 조건이 성립하며, 계수정렬을 사용하기 위한 조건을 만족한다.