1. 계수 정렬 이해하기
(1) 계수 정렬이란?
배열 내 원소 개수를 이용하여 정렬을 하는 알고리즘으로 값의 크기를 비교하는 것이 아닌 값의 분포를 이용한다. 주어진 배열의 범위가 크지 않을 때 좋은 성능을 보인다.
(2) 로직 이해하기
- 입력 배열 내의 각 원소 출현 횟수 계산
- 출현 횟수의 누적합 계산
- 입력 배열의 오른쪽부터 정렬
글로 설명하기에 너무 길어질 것 같아, 애니메이션으로 이해할 수 있는 사이트를 첨부한다.
https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html
(3) 성능
계수 정렬의 성능은 선형 시간인 O(n+k)이다. k는 입력 배열 원소중 최댓값을 의미하는데, 이 수가 무한대로 클 수록 성능에 영향을 미치기 때문에 상수값이 무시되지 않는다. 입력 키의 범위 k가 데이터의 개수 n에 비례하는 경우 O(n)의 시간 복잡도를 갖는다.
(4) 특징
입력 키의 범위가 입력 원소의 개수보다 작거나 비례하는 경우 유용하다. 입력 값의 범위가 큰 경우 그만큼 출현 횟수를 저장하는 배열의 크기가 커지기 때문에 단 몇 개의 수를 정렬 하는 경우에도 최댓값만큼의 크기를 가진 배열을 만들어줘야해 메모리 낭비가 발생한다.
2. 로직 적용하여 알고리즘 문제 풀어보기
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.import sys
array = [int(sys.stdin.readline()) for _ in range(int(sys.stdin.readline()))]
counts = [0 for _ in range(max(array)+1)]
results = [0 for _ in range(len(array)+1)]
for i in array:
counts[i] += 1
for i in range(1, len(counts)-1):
counts[i+1] += counts[i]
for i in reversed(array):
results[counts[i]] = i
counts[i] -= 1
for i in range(1, len(results)):
print(results[i])처음에 해당 로직을 그대로 적용하기 위하여 1. 입력 배열 2. 출현 횟수 저장 배열 3. 정렬 결과 배열 이렇게 세 가지의 배열을 만들었다. 정렬은 잘 되었으나 백준에 제출을 해보니 메모리 초과로 통과가 되지 않았다. 아마 큰 배열을 3개나 만들어야해서 그런 것 같았다.
메모리 문제를 해결하기 위해 입력값의 최대값인 10000+1 크기의 배열을 만들어줘서 입력값과 같은 값의 인덱스 위치에 출현횟수를 저장하고, 인덱스를 입력값으로 활용하는 식으로 수정하여 제출하였더니 통과가 되었다.
import sys
n = int(sys.stdin.readline())
array = [0] * 10001
for _ in range(n):
array[int(sys.stdin.readline())] += 1
for i, a in enumerate(array):
while a > 0:
print(i)
a -= 1하지만 이 로직은 누적합을 계산할 필요가 없는 로직이라 계수 정렬이라고 할 수 있는지 잘 모르겠다 ㅋㅋ
참고
https://8iggy.tistory.com/123
https://seongonion.tistory.com/130
