반응형 정렬2 정렬 알고리즘 3 : 계수 정렬(Counting sort) 세 번째로 알아볼 정렬 알고리즘은 바로 계수 정렬! 계수 정렬은 수의 범위가 적을 때 사용하면 좋은 정렬 알고리즘으로 배열의 가장 큰 값에 따라 시간 복잡도가 달라진다. 배열의 가장 큰 값이 k라고 한다면 O(n+k)의 시간 복잡도를 갖는다. 즉, 입력에 비해서 원소들의 값의 범위가 적다면 계수정렬을 사용하는 것이 효율적인 방법이 될 수 있다! 방법 1. 입력된 배열중 가장 큰 값(k) 찾기 2. k+1 크기의 0으로 초기화된 배열 생성한다. 이는 입력된 배열의 원소가 각각 몇 개가 있는지 셀 배열이다. 3. 배열의 원소를 하나씩 검사하여 2번에서 생성한 배열의 인덱스에 해당하는 값을 1씩 올려준다. (즉, 각 값이 몇 개가 나왔는지 카운팅 해준다.) 4. 각 인덱스를 값만큼 반복하여 출력한다. 예시 배.. 2022. 1. 31. 백준 10989 : 수 정렬하기3(카운팅정렬) 수 정렬하기 3https://www.acmicpc.net/problem/10989 코드# https://teching.tistory.com/import sys# 계수정렬countingNum = [0] * 10001for _ in range(int(sys.stdin.readline().rstrip())): countingNum[int(sys.stdin.readline().rstrip())] += 1for i in range(10001): for _ in range(countingNum[i]): print(i)해설메모리 제한이 8MB로 빡빡한 문제이다. 계수 정렬을 구현해서 풀었다. 계수 정렬에 관한 내용은 https://teching.tistory.com/80에서 정리를 해두었다! .. 2022. 1. 30. 이전 1 다음 반응형