[알고리즘] 2. 계수 정렬(카운팅 정렬 / Counting Sort)

백준 문제를 풀다가 정말 쉬운 문제인 줄 알고

제 방식대로 풀었다가... 계속 틀려서...

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

다른 분들 질문을 보니 카운팅 정렬, 계수 정렬을 사용해서 풀면 풀린다고 하셔서

인터넷 폭풍 검색으로 풀고

이 부분을 처음 접해서 블로그에 남겨놓으면 혹시 다른 분이나 이후에 도움이 될 것 같아

간략하게 정리하려 합니다.

 

 

Counting sort라고 불리는 이유가 리스트 내 요소의 개수를 파악하여 정렬하기 때문입니다.

 

다음과 같은 수열이 있다고 하겠습니다.

5

2

3

1

4

2

3

5

1

7

계수 정렬의 실행 순서는 다음과 같습니다

 

1. 첫번째로 숫자들이 몇 개 등장하는지 세어 줍니다.

숫자	1	2	3	4	5	7
갯수	2	2	2	1	2	1

 

2. 갯수의 누적 합을 구해줍니다.

숫자	1	2	3	4	5	7
누적 합	2	4	6	7	9	10

누적 합이 이 숫자들의 마지막 숫자가 존재하는 인덱스 값이 되는 것입니다.

 

3. 이제 처음 수열을 뒤에서부터 읽어오면서 정렬된 배열에 넣습니다.

5

2

3

1

4

2

3

5

1

7

마지막 숫자인 7의 정렬된 수열에서의 인덱스는 10(누적 합)이 됩니다.

그 후 7의 누적 합 값에 -1을 해줍니다.

이때, 기존 5의 누적 합과 같아지기 때문에 더 이상 7이 들어갈 자리는 없습니다.

7

 

숫자	1	2	3	4	5	7
누적 합	2	4	6	7	9	9

 

다음 수인 1을 현재 누적 합을 인덱스로 해서 배열에 넣으면

1

7

 

숫자	1	2	3	4	5	7
누적 합	1	4	6	7	9	9

 

이렇게 정렬하려는 배열에 존재하는 요소의 갯수를 카운트하여

정렬하려는 인덱스에 대입하여 정렬하는 것을 count 정렬이라 합니다.

 

제 설명이 두서가 없어서 이해가 잘 안되셨을 것 같아서

Counting Sort를 잘 설명해놓은 사이트 링크도 같이 첨부하겠습니다!

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

부족한 설명 읽어 주셔서 감사하고

보충할 내용 계속 채워나가겠습니다!

 

더 덧붙일 설명있으시면 질문 댓글로 남겨주세요!