우선 교재에서 배운 정렬
1.선택정렬(Selection sort)
시간 복잡도 O(N^2)
2.삽입정렬(Insertion sort)
시간복잡도 O(N^2)
그렇지만 최선의 경우(리스트가 거의 다 정렬이 되어있는 경우) O(N)
3.퀵정렬(Quick sort)
O(NlogN)
그치만 최악의 경우(거의 다 정렬이 되어있는 경우) O(N^2)
4.계수정렬(Counting sort)
최악의 경우에도 O(N+K)
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있으며
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 가능
공간복잡도 O(N+K)
5.파이썬 기존 정렬 라이브러리
sorted()
퀵 정렬과 비슷한 병합 정렬을 기반으로 만들어졌으며
최악의 경우에도 O(NlogN)을 보장
연산 횟수? 시간?
늘 알고리즘을 풀면서 흐린눈 해왔던게 데이터의 개수(ex. 1≤N≤1,000,000...), 제한시간 이었는데
여태까지는 그냥 내가 코드를 잘짜서 연산 횟수를 대충 최대한 줄이면 되겠지!! 라는 생각으로 제대로 알아볼 생각을 안했다.
근데 정렬 같은 경우는 이미 정형화된 알고리즘을 내가 체득해서 쓰는 방식이고, 데이터의 개수, 범위, 제한 시간에 따라 알맞은 정렬 방법을 선택해야 하기 때문에
제한 시간과 데이터의 개수에 따라 가져야하는 최소한의 시간복잡도를 알아야 하는 과정이 필요하다고 느꼈다.
(아직 메모리 제한은 최선을 다해 흐린눈 하고 있는게 ㄹㅈㄷ)
제한 시간
Python은 초당 2000만번의 연산이 가능하다고 생각하는게 좋다.
어떤 문제의 시간 제한이 2초이고, 100만개의 수를 정렬한다고 생각하면
4000만번의 연산 안에 100만개의 수를 정렬하는 방법을 찾는게 맞다는 것
그러면 해당 문제는 O(NlogN)안에서 해결해야 한다.
(근데 서버에 따라 시간이 좀 다른 것 같기도...?)
문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)임
시간제한이 1초인 문제를 만났을 때 일반적인 기준은 다음과 같습니다
- N의 범위가 500인 경우: 시간 복잡도가 O(N³)인 알고리즘을 설계하면 문제를 풀 수 있음
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N²)인 알고리즘을 설계하면 문제를 풀 수 있음
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있음
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있음
#2751 수 정렬하기 2
🔗https://www.acmicpc.net/problem/2751
구현
시간 제한 : 2초, 100만개의 수를 정렬 -> O(NlogN)
정말 간단한 정렬 문제!
우선 교재에서 배운 정렬방법으로는 가능한게 없는 것 같아서 (Quick sort는 최악의 경우에서 걸림)
파이썬 기존 시스템 정렬 방법으로 풀어보았다.
코드1 (Python3)
import sys
n=int(sys.stdin.readline().rstrip())
numList=[int(sys.stdin.readline().rstrip()) for _ in range(n)]
numList=sorted(numList)
for num in numList:
print(num)근데 이렇게 푸는게 맞나? 이게 도움이 되는건가?... 싶어서 파이썬 기존 정렬 방법에 사용되었다는 병합 정렬(Merge sort)을 이용해 풀어보았다. 🔗참고 블로그
Python3으로는 시간 초과가 뜬다. 기존 sorted 함수가 정말 잘 만들어진거구나... 를 느낄 수 있었다.
코드2 (PyPy3로만 성공, merge sort 이용)
def merge_sort(numList):
if len(numList)<=1:
return numList
mid = len(numList)//2
left = numList[:mid]
right = numList[mid:]
left1=merge_sort(left)
right1=merge_sort(right)
return merge(left1,right1)
def merge(left, right):
i=0
j=0
numList=[]
while(i<len(left)) & (j<len(right)):
if left[i] < right[j]:
numList.append(left[i])
i+=1
else:
numList.append(right[j])
j+=1
while (i<len(left)):
numList.append(left[i])
i+=1
while (j<len(right)):
numList.append(right[j])
j+=1
return numList
import sys
n=int(sys.stdin.readline().rstrip())
numList=[int(sys.stdin.readline().rstrip()) for _ in range(n)]
numList=merge_sort(numList)
for num in numList:
print(num)#1427 소트인사이드
🔗https://www.acmicpc.net/problem/1427
구현
제한시간 : 2초, 10개의 수를 내림차순으로 정렬(하는 것과 같다), 수의 범위 0~9
이거 완전 계수정렬로 풀기 좋은 문제!!
코드
import sys
digit=[0 for _ in range(10)]
number=sys.stdin.readline().rstrip()
for num in number:
digit[int(num)]+=1
for i in range(9,-1,-1):
if digit[i]==0:
continue
else:
for j in range(digit[i]):
print(i,end='')#1026 보물
🔗https://www.acmicpc.net/problem/1026
구현
교재에 있는 예제와 비슷한 문제!
a는 오름차순 정렬, b는 내림차순 정렬을 한 후
a b를 각각 순서대로 곱해주면 최솟값을 만들 수 있다.
코드
import sys
n=int(sys.stdin.readline().rstrip())
a=list(map(int,sys.stdin.readline().split()))
b=list(map(int,sys.stdin.readline().split()))
answer=0
a=sorted(a)
b=sorted(b,reverse=True)
for i in range(n):
answer+=a[i]*b[i]
print(answer)#1764 듣보잡
🔗https://www.acmicpc.net/problem/1764
구현
듣도 못한 사람의 이름과 보도 못한 사람의 이름 중 같은 것들을 찾는 거라
set 자료형을 써 교집합을 구했다.
조금 더 정렬을 이용해서 풀 수 있는 방법이 있을까 고민하다가... 포기
코드
import sys
n1,n2=map(int,sys.stdin.readline().split())
canthear=set([sys.stdin.readline().rstrip() for _ in range(n1)])
cantsee=set([sys.stdin.readline().rstrip() for _ in range(n2)])
answer=[]
answer=sorted(canthear&cantsee)
print(len(answer))
for a in answer:
print(a)#11004 K번째 수
🔗https://www.acmicpc.net/problem/11004
구현
제한 시간:2초 500만개의 수를 정렬해야함 -> 이거 O(NlogN)도 안된다... 더 좋은 정렬 방법을 구현해야한다............
그냥 무대뽀로 merge sort와 기존 정렬 방법을 PyPy3으로 돌렸더니 시간 초과는 안 떴지만
뭔가 찝찝하다.....
코드1(PyPy3)
import sys
n,k=map(int,sys.stdin.readline().split())
numList=list(map(int,sys.stdin.readline().split()))
numList=sorted(numList)
print(numList[k-1])코드2(PyPy3)
def merge_sort(numList):
if len(numList)<=1:
return numList
mid = len(numList)//2
left = numList[:mid]
right = numList[mid:]
left1=merge_sort(left)
right1=merge_sort(right)
return merge(left1,right1)
def merge(left, right):
i=0
j=0
numList=[]
while(i<len(left)) & (j<len(right)):
if left[i] < right[j]:
numList.append(left[i])
i+=1
else:
numList.append(right[j])
j+=1
while (i<len(left)):
numList.append(left[i])
i+=1
while (j<len(right)):
numList.append(right[j])
j+=1
return numList
import sys
n,k=map(int,sys.stdin.readline().split())
numList=list(map(int,sys.stdin.readline().split()))
numList=merge_sort(numList)
print(numList[k-1])