먹고 기도하고 코딩하라

파이썬과 자료구조 (3) - 우선순위 큐, 힙, 해시 테이블 본문

자료구조&알고리즘/이론

파이썬과 자료구조 (3) - 우선순위 큐, 힙, 해시 테이블

2G Dev 2021. 9. 30. 18:05
728x90
728x90

 

졸업 전시회가 1개월 남은 데다가 새로운 스터디를 2개 시작해서 몸이 2개라면 얼마나 좋을까 공상의 나래를 펼치는 요즘이다. 오늘은 오랜만에 저번에 정리를 못 끝낸 자료구조 이론을 정리할까 한다.

사실 힙은 트리를 설명할 때 함께 설명하는 것이 좋다는 생각이 들지만, 적어도 파이썬에서는 힙을 직접 구현하기보다는 내장된 heapq를 사용하는 것이 훨씬 낫다는 생각에 이 글에 쓴다.

 

 

6. 우선순위 큐 (Priority Queue)

우선순위 큐는 큐의 심화판이다. 큐는 FIFO, 선입선출 자료구조이다. 우선순위 큐 역시 큐와 비슷한 자료구조이기는 하지만, 일반적인 큐에서는 우선권을 따지지 않는 반면 우선순위 큐에서는 큐에 들어오는 자료마다 우선순위가 있어 우선순위가 높은 것은 나중에 들어왔더라도 더 먼저 나가게 된다. 마치 웨이팅이 긴 식당에 예약하지 않은(우선순위가 낮은) 손님들은 밖에서 하염없이 기다리지만, 예약한 손님들(우선순위가 높은)은 먼저 들어갈 수 있는 것과 비슷하다.

큐에 데이터를 넣을 때는 아무렇게나 넣어도 상관없다. 어차피 나오는 순서는 우선순위가 제일 높은 것부터 나오게 되어 있다. 이것이 바로 우선순위 큐의 개념이다.

우선순위 큐는 힙과 거의 비슷하다. 우선순위 큐는 최단경로를 구하는 다익스트라 알고리즘을 구현할 때도 유용하게 쓰인다. 우선순위 큐를 사용하고 싶다면 heapq 모듈을 사용하면 된다.

 

 

7. 힙 (Heap)

힙은 사실 트리 기반 자료구조이다. 학교에서 자료구조를 배웠을 때도 트리를 먼저 배우고 힙을 배웠던 기억이 난다. heapq 모듈이 바로 이 힙으로 구현이 되어 있는데, 힙의 루트에는 항상 우선순위가 가장 높은 것이 위치한다.

파이썬에서 기본적으로 heapq 모듈을 사용하면 이진 트리 기반의 최소 힙(min heap)으로 구현을 한다. 무슨 말이냐면 [3, 5, 2, 7, 4]를 힙에 넣으면 2가 루트 자리에 와서 heap에서 데이터를 뺐을 때 2가 제일 먼저 나간다는 의미이다. 즉, 값이 작을수록 우선순위가 더 높은 것이다.

그렇다고 힙이 이진 트리처럼 정렬된 것은 아니다. 이진 트리라면 루트의 값이 트리에 있는 값들 중에서 중위값 정도여야 할 텐데 그렇지 않다. 최소 힙일 때는 부모 노드가 자식 노드보다 우선순위가 높다는 것 빼고는 딱히 정렬에 대해 정해진 것이 없다. 

힙을 사용하고 싶다면 당연하게도 heapq 모듈을 사용하면 된다. 우선순위 큐와 힙의 직접 구현은 생략하겠다.

 

heapq 모듈의 사용법을 알아보자. heapq를 사용하고 싶다면 import부터 해줘야 한다.

import heapq

deque처럼 heapq라는 타입의 자료구조가 있는 건 아니다. 일반 리스트를 힙처럼 사용할 수 있도록 하는 것이 heapq 모듈이다.

 

만약 arr이라는 리스트를 힙처럼 쓰고 싶다고 해보자. 그럼 일단 arr이라는 빈 리스트를 생성하는 것이 순서이다.

그 다음에는 데이터를 리스트에 넣으면 된다. 이 때 잠깐, 일반적으로 리스트에 데이터를 추가할 때 쓰는 append를 쓰는 게 아니라 heapq.heappush 메소드를 써야 한다.

arr = []
heapq.heappush(arr, 5)
heapq.heappush(arr, 2)
heapq.heappush(arr, 3)
heapq.heappush(arr, 7)

heapq.heappush(arr, val) 메소드는 첫 번째 인자로 리스트를 받고, 두 번째 인자로는 리스트에 추가할 데이터를 받는다. 이 때 arr은 이진 힙처럼 구성이 됐기 때문에 실제로는 5를 제일 먼저 추가했음에도 리스트 맨앞에는 우선순위가 제일 높은 2(최소 힙에서는 숫자가 작을수록 우선순위가 높다)가 위치한다.

이제 힙을 구성했으니 우선순위가 제일 높은 것부터 꺼내보고 싶다. 그럼 heapq.heappop 메소드를 쓰면 된다.

print(heapq.heappop(arr))	# 2

heapq.heappop(arr) 메소드는 인자를 하나만 받는데 이 인자는 heapq.heappush를 해서 이진 힙으로 구성된 리스트가 들어와야 한다. 이 리스트에서 우선순위가 제일 높은, 즉 0번 인덱스에 있는 값을 리스트에서 추출한다.

 

원래 있는 리스트를 힙처럼 구성하고 싶다면 어떻게 해야 할까? 이 때는 heapq.heapify 메소드를 사용하면 된다.

arr2 = [51, 245, 39, 8, 6, 40, 28, 4, 68]
heapq.heapify(arr2)
heapq.heappop(arr2)	# 4

heapq.heapify(arr) 메소드 역시 heappop처럼 인자를 하나만 받는데 힙으로 만들고 싶은 리스트를 받는다. 이렇게 해서 arr2의 데이터들이 이진 힙 구조로 재구성되면서, 우선순위가 가장 높은 숫자 4가 0번 인덱스에 위치하게 된다. 따라서 heappop을 했을 때 4가 추출되는 것을 확인할 수 있다.

 

그런데 살다 보면.. 백준 문제를 풀다 보면 최소 힙이 아니라 최대 힙을 구현해야 될 때도 있다. 그럴 때 쓰는 트릭 아닌 트릭이 있는데, 바로 튜플을 데이터로 넣는 것이다.

리스트 정렬할 때도 생각해보라. 리스트 안에 튜플이나 리스트가 원소로 들어가 있으면 정렬을 할 때 원소의 0번 인덱스를 기준으로 쭉 정렬을 한다. 힙도 마찬가지로 그렇게 하면 되는 거다. 아래의 예시는 0부터 9까지 max_heap에 넣고, 우선순위가 높은 것부터 빼는 코드이다.

# 최대 힙 구현하기
import heapq

max_heap = []
for i in range(10):
  heapq.heappush(max_heap, (-i, i))	# 만약 현재 i가 5라면 (-5, 5)가 된다.
while max_heap:
  print(heapq.heappop(max_heap)[1])

작은 숫자가 우선순위가 높다는 것에는 음수에도 예외가 없다. 음수가 양수보다 당연히 우선순위가 높다. 숫자가 더 작으니까 말이다. 여기서는 이 점을 이용해 음수 기호 마이너스를 붙여 양수에서의 숫자가 클수록 음수에서의 숫자가 작도록, 즉 우선순위가 크도록 만들어 최대 힙을 만든 것이다.

 

 

8. 해시 테이블

해시 테이블, 혹은 해시 맵은 key-value가 쌍으로 맵핑되는 자료구조이다. 익숙한 설명 아닌가? 파이썬에서는 딕셔너리나 마찬가지이다. 해시 테이블에 들어오는 데이터들을 해시 함수를 거쳐서 여기저기로 쪼개져서 들어가기 때문에 테이블 내 데이터들을 연산해야 할 때 그 데이터의 해시값만 안다면 O(1) 정도의 놀라운 시간복잡도를 갖는다는 장점이 있다.

이것도 자료구조를 직접 구현하는 작업은 생략하겠다. 이걸 읽으실 정도라면 딕셔너리를 어떻게 쓰시는지는 알 것이고 하니 defaultdict과 Counter를 설명하는 것이 더 낫다는 생각이 든다.

파이썬에서 기본으로 제공하는 딕셔너리들 중에는 OrderedDict라고 순서를 보장해주는 딕셔너리도 있지만, 최근의 업데이트된 버전 파이썬에서는 이제 딕셔너리에 값을 넣을 때 그 순서가 유지되기 때문에 쓸 일이 없어서 따로 소개하지 않겠다.

 

먼저 defaultdict부터 살펴보자. defaultdict은 한마디로 딕셔너리에 어떤 키값이 존재하지 않는데, 그 키값에 존재하려고 할 때 어떤 타입의 기본값을 주는 딕셔너리이다.

일반 dict 타입의 딕셔너리에 없는 키를 접근하려고 하면 에러를 뱉거나, .get 메소드를 쓰면 그나마 None을 돌려주는 식으로 처리가 된다. 하지만 defaultdict를 써서 딕셔너리를 생성하면, 미리 지정한 타입의 기본값을 줄 수 있도록 딕셔너리를 만들게 된다.

예컨대 defaultdict(int)라고 만들게 되면, 없는 키값에 접근했을 때 0을 반환하게 된다. defaultdict(list)라고 만들면 없는 키값에 접근했을 때 에러가 나는 것이 아니라 빈 리스트인 []를 반환하게 된다. 쉬운 그래프 문제를 풀 때 잠깐 썼던 기억이 난다. defaultdict를 만들 때 매개변수로 타입의 이름을 주는 것에 주목하자.

from collections import defaultdict, Counter

def_dic = defaultdict(int)
def_dic['name'] = 'default dict'
print(def_dic['length'])	# 0
print(def_dic['name']) # default_dict

 

Counter는 문자열이나 리스트 등의 이터러블 객체를 받아 어떤 원소의 개수가 얼마나 있는지 세 주는, 말그대로 카운터 역할을 하는 딕셔너리이다. Counter를 만들 때 아예 매개변수로 원소의 개수를 세고 싶은 이터러블 객체를 넣어버리면 된다. 

counter = Counter('elephant')
print(counter)
# Counter({'e': 2, 'l': 1, 'p': 1, 'h': 1, 'a': 1, 'n': 1, 't': 1})

여기 더 좋은 활용방법이 있다.

Counter를 왜 쓰겠는가? 당연히 원소 개수를 셀 때 쓴다. 그럼 최빈값 구할 때도 쓰기 좋지 않을까? Counter에는 most_common 이라는 이름으로 n번째로 많이 나온 원소와 그 횟수를 돌려주는 메소드가 있다.

counter2 = Counter([1, 1, 3, 5, 2, 4, 6, 13, 7, 4, 2, 3, 5, 7, 6, 5])
print(counter2)
# Counter({5: 3, 1: 2, 3: 2, 2: 2, 4: 2, 6: 2, 7: 2, 13: 1}) 
print(counter2.most_common())
# [(5, 3), (1, 2), (3, 2), (2, 2), (4, 2), (6, 2), (7, 2), (13, 1)]
print(counter2.most_common(1))
# [(5, 3)]

most_common에 매개변수를 비워두면 (데이터, 횟수) 튜플들로 이뤄진 리스트가 반환된다. 이제 뭐 for문을 돌린다거나 하고 싶다면 most_common()을 써서 리스트로 받아두면 쓰기 좋다.

만약 첫번째로 많이 나온 원소와 그 횟수를 보고 싶다면, most_common(1)을 쓰면 된다. 그럼 역시 튜플들로 이뤄진 리스트가 반환된다. 리스트에 튜플이 1개가 아닐 수도 있다. 위의 예시처럼 지금 2번째로 많이 나온 원소들이 저렇게 많다면 튜플들이 많이 담겨 나올 수도 있는 것이다.

이 때 횟수에 접근하고 싶다면 most_common(n)[0][1]을 하면 되는 것이고(횟수는 다 똑같을 테니까), n번째로 많이 나온 값들에만 집중하고 싶다면 most_common(n) 리스트에 담긴 모든 튜플의 0번 인덱스에 든 값에만 집중하면 된다.

 

다음에는 트리와 그래프를 살펴보겠다.

 

 

 

References

 

 

728x90
반응형
0 Comments
댓글쓰기 폼