🤍
힙
: 최대힙과 최소힙이 있으며, 데이터에서 최대값 또는 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.
*완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다.
최대힙
: Max heap. 항상 큰 값이 상위 레벨에 있는 자료구조(부모노드 값 > 자식노드 값)로, 최대값을 빠르게 구할 수 있다.
BST(이진 탐색 트리)와 다르게 좌우 자식의 위치는 대소관계와 상관이 없다.
계산의 편의를 위해 인덱스를 1부터 사용.
=> parent: x, left: 2x, right: 2x+1
<최대 힙 원소 추가>
1. 맨 마지막에 원소를 넣는다.
2. 부모노드와 비교한다.
3. 부모노드보다 새로운 원소가 더 크다면 둘의 자리를 변경한다.
4. 과정 2,3을 가장 상위 레벨(루트)에 도달하거나, 새 원소보다 값이 큰 부모노드를 만날 때까지 반복한다.
<최대 힙 원소 추출>
: 루트노트(최댓값)을 삭제하는 것
1. 루트 노드와 맨 끝의 원소를 교체
2. 맨 뒤의 원소(원래의 루트 노드였던 것)를 삭제
3. 변경된 노드와 자식 노드들을 비교. 두 자식 중 더 큰 자식과 비교해 그 자식노드가 더 크면 자리 교체.
4. 자식 노드 둘보다 부모 노드가 크거나, 가장 바닥에 도달하지 않을 때까지 3번을 반복.
5. 2번에서 제거한 원래 루트 노드를 반환.
<최대 힙 원소 삽입, 추출 시간복잡도>
완전 이진 트리의 최대높이와 같은 O(log(N)).
구현
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def __len__(self): # __메서드__ 형식으로 되어있는 것은 일종의 예약어. 이 경우 매직메서드 덮어쓰기(override)가 가능하다.
# len() 연산을 편리하게. 인덱스 1부터 시작하는 것을 감안해 기본 len()연산에서 1을 빼준 값을 반환.
return len(self.items) - 1
def _percolate_up(self):
# percolate: 스며들다.
cur = len(self) # 전체길이
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
while parent > 0: # 부모노드의 인덱스가 0이 되면 안되므로.
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1
if left <= len(self) and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self) and self.items[right] > self.items[biggest]:
biggest = right
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
def insert(self, k):
self.items.append(k)
self._percolate_up()
def extract(self):
if len(self) < 1:
return None
# 하나 이상의 요소가 있다면
root = self.items[1]
self.items[1] = self.items[-1] # 부모노드와 가장 마지막 노드 값 바
self.items.pop()
self._percolate_down(1)
return root
최대 힙 라이브러리
직접 구현할 수도 있지만 파이썬의 라이브러리의 함수를 사용하면 간편하다.
파이썬에서는 최소 힙을 기본으로 하기 때문에 최대 힙을 구하려면 최소 힙을 이용한다. (인덱스[-1])
힙을 만드는 방법 - [ ]로 초기화된 리스트를 사용하거나 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환.
- heapq.heappush(heap, item) : 힙 불변성을 유지하면서, item값을 heap으로 push
- heapq.heappop(heap) : 힙 불변성을 유지하면서, heap에서 가장 작은 항목을 pop하고 반환.
- heapq.heappushpop(heap, item) : 힙에 item을 push한 다음, heap에서 가장 작은 항목을 pop하고 반환. heappush()하고 heappop()을 별도로 호출하는 것보다 더 효율적.
- heapq.heapify(x) : 값이 들어 있는 리스트를 힙으로 변환.
- heapq.heapreplace(heap, item) : 힙에서 가장 작은 항목을 pop하고 반환. 새로운 item도 push. 힙 크기 변하지 X. heappop()하고나서 heappush()하는 것보다 더 효율적. 고정크기 힙에 더 적합!
- heapq.merge(*iterables, key=None, reverse=False) : 여러 정렬된 입력을 단일 정렬된 출력으로 병합. 정렬된 값에 대한 iterator 반환.
- heapq.nlargest(n, iterable, key=None) : iterable에 의해 정의된 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환.
- heapq.nsmallest(n, iterable, key=None) : iterable에 의해 정의된 데이터 집합에서 n개의 가장 작은 요소로 구성된 리스트를 반환.
k번째로 큰 값을 구하는 코드 (직접 구현)
from heap.structures import BinaryMaxHeap
def test_maxheap_we_made(lst, k):
maxheap = BinaryMaxHeap()
# for 문 = > 힙정렬 시간복잡도 계산의 토대
for elem in lst:
maxheap.insert(elem)
return [maxheap.extract() for _ in range(k)][k - 1] # k번째 큰 값을 구하기 위함
함수를 사용하는 경우.
import heapq
def test_maxheap_heapq(lst, k):
return heapq.nlargest(k, lst)[-1]
ALGORITHM CODE KATA
Ⅰ. N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다. N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오. ( 2161번: 카드1 https://www.acmicpc.net/problem/2161)
from collections import deque
N = int(input())
result = []
cards = deque([i for i in range(1, N+1)])
while len(cards) > 1:
result.append(cards[0])
cards.popleft()
cards.append(cards.popleft())
result.append(cards[0])
print(*result) # unpacking operator '*'7
>>> 1 3 5 7 4 2 6
Ⅱ. N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. (1920번: 수 찾기 (acmicpc.net))
result = []
N = int(input())
A = list(map(int, input().split(" ")))
M = int(input())
B = list(map(int, input().split(" ")))
# for i in B:
# if i in A:
a_set = set(A) # 해시테이블
for i in B:
if i in a_set:
result.append(1)
else:
result.append(0)
print(*result, sep = "\n")
주석처리한 부분과 같이 쓰면 시간초과가 떠서 해시테이블을 이용했다. 리스트 A에 대한 검색 시간이 상수시간(O(1))이 돼 시간복잡도를 줄일 수 있다.
아니면 아예 입력받을 때 A, B를 set으로 받아도 된다.
result = []
N = int(input())
A = set(map(int, input().split(" ")))
M = int(input())
B = set(map(int, input().split(" ")))
for i in B:
if i in A:
result.append(1)
else:
result.append(0)
print(*result, sep = "\n")