시간 복잡도

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택정렬	O(N^2)	O(N)	아이디어가 매우 간단하다.
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정려로디어 있을때는 가장 빠르다.
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠르다.
계수 정렬	O(N + K) (K는 데이터 중에서 가장 큰 양수)	O(N + K) (K는 데이터 중에서 가장 큰 양수)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작한다.

 

정렬 알고리즘 동작 아이디어

정렬 알고리즘	핵심 아이디어
선택 정렬	가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법
삽입 정렬	데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법
퀵 정렬	기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
계수 정렬	특정한 값을 가지는 데이터 개수를 '카운트'하는 방법

 
파이썬의 표준 라이브러리에서 기본 제공하는 정렬 라이브러리는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
따라서 계수 정렬을 사용해 매우 빠르게 정렬해야 하는 특이한 케이스가 아니라면 파이썬의 정렬 라이브러리를 사용하는 것이 가장 합리적이다.

문제

Q 23 국영수

# 국어 점수가 감소하는 순서로
# 국어 점수가 같으면 영어 점수가 증가하는 순서로
# 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
# 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다.)

n = int(input())

list_data = []

# list에 tuple 입력하기
for _ in range(n):
    list_data = list(input().split())

result = sorted(list_data, key = lambda x : (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

# 정렬된 학생 정보에서 이름만 출력
for idx in range(len(result)):
    print(result[idx][0])

 

Q 24 안테나

정확히 중간값에 해당하는 위치의 집에 안테나를 설치했을 때, 안테나로부터 모든 집까지의 거리의 총합이 최소가 된다.
1 2 3 5 8 9 일 경우
3 혹은 5에 안테나를 설치하는 경우, 안테나로부터 모든 집까지의 거리의 총합이 최소가 된다.
소스

# A.24 안테나
n = int(input())
data = list(map(int, input().split()))
data.sort()

# 중간값(median)을 출력
print(data[(n - 1) // 2])

 

Q 25 실패율

실패율 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수
소스

def solution(N, stages):
	answer = []
	length = len(stages)
	
	# 스테이지 번호를 1부터 N까지 증가시키며
	for i in range(1, N + 1):
		# 해당 스테이지에 머물러 있는 사람의 수 계산
		count = stages.coumt(i)
		
		# 실패율 계산
		if length == 0:
			fail = 0
		else:
			fail = count / length
		
		# 리스트에 (스테이지 번호, 실패율) 원소 삽입
		answer.append((i, fail))
		length -= count
		
	# 실패율을 기준으로 각 스테이지를 내림차순 정렬
	answer = sorted(answer, key=lambda t: t[1], reverse=True)

	# 정렬된 스테이지 번호 출력
	answer = [i[0] for i in answer]
	return answer

 

Q 26 카드 정렬하기

항상 가장 작은 크기의 두 카드 묶음을 합쳤을 때 최적의 해를 보장한다.
무조건 가장 작은 크기의 두 카드 묶음을 합치면 된다.
ex)
10 20 40 -> 30 40 -> 70
40 10 20 -> 50 20 -> 70
매 상황에서 가장 작은 트기의 두 카드 묶음을 꺼내서 이를 합친 뒤에 다시 리스트에 삽입하는 과정
이때, 가장 효과적으로 수행할 수 있는 자료구조 : 우선순위 큐 (원소를 넣었다 빼는 것만으로도 정렬된 결과를 받을 수 있다.)
우선순위 큐는 heap 자료구조를 이용해서 구현할 수 있으며, 파이썬에서는 heapq 라이브러리를 지원하고 있다.

import heapq

n = int(input())

# 힙(Heap)에 초기 카드 묶음을 모두 삽입
heap = []
for i in range(n):
	data = int(input())
	heapq.heappush(heap, data)
	
result = 0

# 힙(Heap)에 원소가 1개 남을 때까지
while len(heap) != 1:
	# 가장 작은 2개의 카드 묶음 꺼내기
	one = heapq.heappop(heap)
	two = heapq.heappop(heap)
	# 카드 묶음을 합쳐서 다시 삽입
	sum_value = one + two
	result += sum_value
	heapq.heappush(heap, sum_value)

print(result)