반응형 10989번1 [알고리즘] 계수정렬(Counting Sort) .feat 백준 10989번(파이썬) 계수 정렬이란? - 원소들간의 비교를 하지 않고, 숫자의 개수를 파악하여 정렬을 수행하는 알고리즘이다. - 타 정렬들과 다르게 비교하지않아서 시간복잡도는 O(N)이다. - 10989번의 문제는 시간제한이 있어 계수정렬을 이용하여 풀기로 생각하였다! 계수 정렬 수행과정 1. 입력받은 혹은 정렬을 하고 싶은 데이터 리스트에서 최대값 + 1 하여 리스트를 만든다. 2. 최대값 + 1 리스트에 데이터가 몇개가 겹치는지 횟수를 기록한다. 3. 그 횟수를 토대로 인덱스를 출력한다. 아래는 위의 계수 정렬을 파이썬코드로 구현한겁니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys input = sys.stdin.readline N = int(.. 2023. 6. 25. 이전 1 다음 반응형