-1) 정렬 개념
정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것
사용자가 정의한 순서는 오름차순이나 내림차순일 수도 있고 임의의 조건이 될 수도 있음
정렬이 필요한 이유
정렬을 하면 원하는 데이터를 쉽게 찾을 수 있다!
1. 삽입 정렬
데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬
** 키 : 정렬되지 않은 영역의 맨 앞에 있는 값
1. 최초에는 정렬된 영역은 왼쪽 1개, 정렬되지 않은 영역을 나머지로 한다
2. 키와 정렬된 영역의 맨 끝 값부터 거슬러 올라가며 다음 처리를 한다
2-1. 키보다 크면 해당 값을 오른쪽으로 한 칸 밀어낸다
2-2. 키보다 작거나 더 이상 비교할 값이 없으면 밀어낸 자리에 키를 넣는다
3. 모든 데이터가 정렬될 때까지 2단계를 반복한다
-> 최악의 경우 O(N^2), 최선의 경우 O(N)
2. 병합 정렬
정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬
( 이런 방식을 분할 정복이라고 함 )
-- 병합할 때 정렬하는 과정 --
1. 각 데이터의 첫 번째 원소를 가리키는 포인터를 만든다
1-1. 포인터가 가리키는 두 값 중 작은 값을 선택해 새 저장 공간에 저장한다
1-2. 값이 선택된 포인터는 다음 위치의 값을 가리킨다
2. 새 저장 공간에 하나의 데이터가 완전히 저장될 때까지 과정 1을 반복한다
2-1.그러고 나서 저장할 값이 남은 데이터의 값을 순서대로 새로운 공간에 저장한다
2-2. 그러면 새로운 저장 공간에 두 개의 데이터가 정렬된 상태로 저장된다
3. 새로운 저장소에 저장된 값의 개수와 초기에 주어진 데이터에 들어 있는 값의 개수가 같을 때까지 과정 1,2를 반복한다
-> O(NlogN) 나누는 횟수 logN, 합치는 횟수 NlogN
3. 힙 정렬
힙이라는 자료구조를 사용해서 정렬
힙 정렬은 데이터의 추가, 삭제가 빈번할 때 유용 !
힙이란?
특정 규칙이 있는 이진 트리
그 규칙에 따라 최대힙, 최소힙으로 나눔
최대힙은 부모 노드가 자식 노드보다 크고, 최소힙은 부모 노드가 자식 노드보다 작음
힙 구축 방법 - 최대 힙
max_heapify() : 특정 노드가 최대힙의 규칙을 만족하지 못하면 힙을 구축하는 과정을 아래로 내려가면서 반복하는 동작
- 현재 노드와 자식 노드의 값을 비교한다
1-1. 현재 노드의 값이 가장 크지 않으면 자식 노드 중 가장 큰 값과 현재 노드의 값을 바꾼다
1-2. 만약 자식 노드가 없거나 현재 노드의 값이 가장 크면 연산을 종료한다
( 자식 노드가 없으면 아무런 동작을 안 하므로 사실 N이 아니라 N/2 부터 힙 구축을 시작해도 괜찮음 )
힙 정렬 과정 - 최대 힙
1. 정렬되지 않은 데이터로 최대 힙을 구축한다
2. 현재 최대힙의 루트 노드와 마지막 노드를 맞바꾼다
맞바꾼 뒤 마지막 노드는 최대힙에서 제외한다
3. 현재 최대힙은 마지막 노드가 루트 노드가 되었다
따라서 max_heapify(1)을 진행하여 최대힙을 다시 구축하고 과정 2를 수행한다
이 과정은 최대 힙의 크기가 1이 될 때까지 진행한다
-> O(NlogN) N개를 힙으로 나타내면 높이가 O(logN)인 트리가 됨
우선순위 큐
우선순위 큐는 우선순위가 높은 데이터부터 먼저 처리하는 큐
즉 큐는 큐인데 우선 순위에 따라 팝을 하는 큐
우선순위 큐를 구현할 때는 힙을 활용하는 것이 효율적
우선순위 큐가 동작하는 방식
** 작은 값일수록 우선순위 작다고 가정
1. 빈 우선순위 큐를 하나 선언, 형태는 큐와 동일
2. 처음 원소 삽입, 별다른 우선순위를 생각하지 않고 맨 앞에 푸시
3. 다음 원소 삽입, 더 작은 값이라면 앞에 삽입
4. 팝
파이썬에서는 heapq 모듈로 힙을 제공함 !
힙으로 우선 순위 큐 구현하기
import heapq
heap=[]
heapq.heappush(heap,10)
heapq.heappush(heap,5)
heapq.heappush(heap,20)
heapq.heappush(heap,1)
print(heap) # [1,5,20,10]
print(heapq.heappop()) # 1
print(heap) # [5,10,20]
print(heapq.heappop()) # 5
print(heap) # [10,20]데이터 자체에 우선순위를 직접 정하고 싶다면 튜플 형태로 (우선순위,데이터)를 heappush() 메서드에 전달하면 됨
ex) heappush(heap,(3,'A'))
값이 클수록 우선순위가 높은 우선순위 큐를 쓰고 싶다면 값을 푸시할 때 -1을 곱하고
팝할 땐 팝한 값에 -1을 곱해서 사용하면 됨
import heapq
class MaxHeap():
def __init__(self):
self.heap=[]
def push(self,value):
heapq.heappush(self.heap,-value)
def pop(self,value):
return -heapq.heappop(self.heap)
max_heap=MaxHeap()
값을 한꺼번에 우선순위 큐에 넣으려면?
앞선 방식은 우선순위 큐에 하나씩 추가할 때를 가정
여러개 한번에 넣으면 heapify() 메서드를 활용할 수도 있음
import heapq
tasks=[(3,"작업 A"),(1,"작업 C"),(2,"작업 B")]
# 리스트를 힙으로 변환
heapq.heapify(tasks)
heapq.heappush(tasks,(0,"작업 D"))
-> heapify : O(N), heappush()/heappop() : O(logN)
우선순위 큐는 데이터의 중요성 혹은 우선순위에 따라 처리해야 하는 경우 많이 활용됨
4. 위상 정렬
일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘
일의 순서가 중요하므로 반드시 간선의 방향이 있어야 함
만약 그래프에 순환이 있거나 간선의 방향이 없으면 일의 방향이 없는 것이므로 안됨
즉 방향 비순환 그래프(Directed Acyclic Graph) 에서만 사용할 수 있음
위상 정렬과 진입차수
진입차수 : 자신을 향한 화살표의 개수
진입차수가 0이면 자신을 향한 화살표가 없다 = 선행 작업이 필요 없는 바로 할 수 있는 일
위상 정렬 과정
바로 진행할 수 있는 일, 다시 말해 진입차수가 0인 일을 해결하고 관련된 작업의 진입차수를 1씩 낮추면서 새롭게 진입차수가 0이 된 작업들을을 해결하는 식으로 진행
-> 해결할 때 큐를 활용하여 구현
진입차수가 0인 작업을 일단 전부 큐에 넣고 하나씩 팝하면서 해당 작업과 연결되어 있는 작업들의 진입차수를 줄인다
진입차수가 0이 된 작업은 큐에 넣음
팝한 순서를 늘어놓으면 위상 정렬 끝!
-> 모든 정점과 간선을 딱 한 번씩만 지나므로 O(|V|+|E|)
5. 계수 정렬
데이터에 의존하는 정렬 방식, 데이터의 빈도수로 정렬
배열에서 데이터의 빈도수를 세어 빈도수 배열에 저장
- 빈도수 배열에 빈도수를 세어 채운다
ex ) 1이 2번 나오면 인덱스 1에 2 넣기 - 우선 순위가 높은 데이터부터 빈도수만큼 출력한다
ex ) 빈도수 배열에서 인덱스 1이 2 이니 1 1 이렇게 출력
빈도수 배열에서 인덱스 오름차순으로 각 인덱스를 빈도수만큼 출력하면 자연스럽게 오름차순으로 정렬한 배열이 나옴
계수 정렬의 한계
-150,100,10억 과 같은 값의 빈도수를 측정하여 빈도수 배열에 저장한다면
- -150 이라는 값은 음수이므로 배열의 인덱스로 표현할 수도 없고
- -150과 500 사이의 공간 낭비도 있고
- 크기가 10억 이상인 배열을 만드는 것은 환경에 따라 어려울 수 있음
-> O(N+K) 데이터 세는 과정은 데이터 N개를 한 번씩 세므로 N, 값의 최솟값~최댓값 범위 크기가 K라면 빈도수 배열에서 K+1 만큼 탐색해야 하므로
