전역변수 선언 global
join 함수: 배열을 문자열로 묶어줌 (int형을 쓰려면 str형으로 변환해줘야 함)
ex) a_list = [0, 0, 0, 0] 이라면
print(" ".join(map(str, a_list)), sep="")
output => 0 0 0 0deque: 파이썬은 모듈 제공 (from collections import deque)
deque 쓰면 앞이랑 뒤에서 모두 삽입/삭제가 가능(left/right)
힙(Heap)
: 최댓값/최솟값을 빠르게 찾기 위한 자료형으로 완전 이진 트리의 일종
완전 이진 트리는 중복을 허용하지 않지만 힙은 허용함
*완전 이진 트리(Complete Binary Tree)
노드를 삽입할 때, 왼쪽부터 차례대로 삽입하는 트리
힙의 부모 자식 관계
* 부모 인덱스 = (자식 인덱스)/2
* 왼쪽 자식 인덱스 = (부모 인덱스)*2+1
* 오른쪽 자식 인덱스 = (부모 인덱스)*2최대 힙(Max Heap)
최대 트리(Max Tree)이면서 완전 이진 트리
즉, 부모 노드는 자식 노드보다 크거나 같아야 함
최소 힙(Min Heap)
최소 트리(Min Tree)이면서 완전 이진 트리
즉, 부모 노드는 자식 노드보다 작거나 같아야 함
힙의 삽입/삭제
[삽입]
트리의 마지막 노드에 삽입하며 시작해 루트 쪽으로 올라가는 상향식 방법
최대/최소 힙이 될 때까지 위로 올라가는 과정 반복, 즉 부모 노드와 서로 교환하며 위로 올라가는 과정을 반복한다.
[삭제]
힙의 루트에서 삭제, 루트 노드가 비어져 있는 상태에서 마지막 노드가 루트 노드로 옴
그 후 새로 올라온 값이 제자리를 찾아갈 수 있도록 자식 노드와 값을 비교하며 아래로 내려가는 과정 반복
파이썬의 heapq 모듈 (import heapq)
-heapq.heappush(heap, item): 힙 특성을 유지하며 item값을 heap으로 push
-heapq.heappop(heap): 힙 특성을 유지하며 heap에서 가장 작은 항목을 pop/반환
해당 모듈은 최소힙의 특성을 따르고 최대힙을 사용하려면 힙에 push할 때 -를 붙여 음수로 삽입하고 pop할 때 -를 붙여 다시 원래 값으로 가져온다
