[이것이 취업을 위한 코딩 테스트다 with 파이썬] 4-2강(계수 정렬, 예제)
2021. 5. 2. 17:01ㆍ민공지능/알고리즘
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
이중 반복문의 시간 복잡도는 N + K이다.
데이터가 0과 999,999로 단 2개만 있지만, 공간은 1,000,000개 있어야 하기 때문에 비효율
from random import randint
import time
# 배열에 10,000개의 정수를 삽입
array = []
for _ in range(10000):
array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수
# 선택 정렬 프로그램 성능 측정
start_time = time.time()
# 선택 정렬 프로그램 소스코드
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 스와프
end_time = time.time() # 측정 종료
print("선택 정렬 성능 측정:", end_time - start_time) # 수행 시간 출력
# 배열을 다시 무작위 데이터로 초기화
array = []
for _ in range(10000):
array.append(randint(1, 100)) # 1부터 100 사이의 랜덤한 정수
# 기본 정렬 라이브러리 성능 측정
start_time = time.time()
# 기본 정렬 라이브러리 사용
array.sort()
# 최악의 경우에도 O(NlogN)시간 복잡도를 보장한다
end_time = time.time() # 측정 종료
print("기본 정렬 라이브러리 성능 측정:", end_time - start_time) # 수행 시간 출력
# 선택 정렬 성능 측정: 5.040791749954224
# 기본 정렬 라이브러리 성능 측정: 0.0009980201721191406
n, k = map(int, input().split()) # N과 K를 입력 받기
a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기
b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기
a.sort() # 배열 A는 오름차순 정렬 수행
b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행
# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
for i in range(k):
# A의 원소가 B의 원소보다 작은 경우
if a[i] < b[i]:
# 두 원소를 교체
a[i], b[i] = b[i], a[i]
else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
break
print(sum(a)) # 배열 A의 모든 원소의 합을 출력
'민공지능 > 알고리즘' 카테고리의 다른 글
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 6-1강(다이나믹 프로그래밍, 개미전사, 1로만들기) (0) | 2021.05.03 |
---|---|
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 5강(이진 탐색 알고리즘) (0) | 2021.05.02 |
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 4-1강(정렬 알고리즘:선택 정렬, 삽입 정렬, 퀵 정렬) (0) | 2021.05.01 |
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 3-1강(스택, 큐, 재귀 함수) (0) | 2021.04.30 |
[이것이 취업을 위한 코딩 테스트다 with 파이썬] 1-4강(함수와 람다 표현식, 라이브러리) (0) | 2021.04.29 |