정렬-삽입정렬,퀵정렬,병합정렬,기수정렬

이론

📖 삽입정렬

• 대상을 선택해 정렬된 영역에서 적절한 위치를 찾아 삽입하면서 정렬.
• 시간복잡도 : O(n^2) -----> 느린편이지만 구현하기 쉽다.

📖 퀵정렬

• 기준값(pivot값)을 선정해서 해당 값을 기준으로 정렬.
• 기준값을 어떻게 정하는지에 따라 시간복잡도가 달라진다.
• 시간복잡도 : O(nlogn) -----> 최악인 경우, O(n^2)이 될 수도 있다.

📖 병합정렬

• 분할정복방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합친다.
• 시간복잡도 : O(nlogn)
• 문제풀 때, 투 포인트 개념을 사용하여 왼쪽,오른쪽 그룹을 병합하는 방식으로 푼다.

📖 기수정렬

• 데이터의 자릿수를 비교해 데이터를 정렬.
  ex) 123, 456을 비교하면 1과4 / 2와5 / 3과6 을 비교한다.
• 시간복잡도 : O(kn) , k는 데이터의 자릿수를 의미.
• 시간복잡도가 가장 짧은 정렬이다.
• 문제풀 때, 10개의 큐를 사용하여 푼다.

문제풀이

📖 백준 11399 (🔗백준 11399 문제)

✏ 그리디 방식.

✏ 정렬사용.

• 시간의 합이 최소가 되려면, 각 사람이 돈을 인출하는 데 필요한시간이 최소가 되어야한다.

• 각 사람이 돈을 인출하는 데 필요한 시간이 최소가 되려면, 인출시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 해야된다.

• 따라서, 정렬을 사용한 후 시간의 합을 구하면 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구할 수 있다.

# 그리디방식
# 시간의 합이 최소가 되려면, 각 사람이 돈을 인출하는 데 필요한시간이 최소가 되어야한다.
# 각 사람이 돈을 인출하는 데 필요한 시간이 최소가 되려면, Pi가 오름차순으로 정렬을 이루어야 한다.

import sys
input=sys.stdin.readline

n=int(input())
time=list(map(int,input().split()))
sum=0
sumlist=[]
sum2=0

time.sort()

for i in time:
	sum=sum+i
	sumlist.append(sum)

for i in sumlist:
	sum2=sum2+i
print(sum2)

❗ 병합정렬 - 투 포인터 개념 사용.

❗ 기수정렬 - 10개의 큐 사용.

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준