힙, 해시 테이블

1. 힙 (Heap)

정해진 우선 순위에 따라 원소를 O(log n)에 추가 / 삭제가 가능한 자료구조. 완전 이진 트리로, 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조이다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있어서, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 파이썬에서는 heapq 라이브러리를 사용해 구현할 수 있다.

파이썬의 heapq 라이브러리는 최소값을 우선 순위로 하는 힙을 제공한다. 

• 기본 연산
  • push : 힙에 새로운 원소 추가
  • pop : 힙에서 가장 우선 순위가 빠른 원소를 추출하고 그 값을 반환
• heapq 라이브러리
  
  • heapify : 리스트를 최소 힙으로 변환
  • heappush : 힙에 원소 추가
  • heappop : 힙에서 가장 작은 원소 제거 후 그 값을 반환
  • 최소 힙의 최솟값 조회 : 0번 인덱스로 조회
    • 0 이외의 다른 인덱스는 큰 의미가 없다. ex) heap[3]과 힙에서 4번째로 작은 값은 다를 수 있다.

from heapq import heapify, heappush, heappop
# 또는 from heapq import *

a = [5, 3, 4, 1, 2]     # 리스트 생성
heapify(a)              # a를 최소 힙으로 변경
print(a[0])             # 1
print(heappop(a))       # 최솟값 추출 -> 1. a는 [2, ....]
print(a[0])             # 1이 제거됨 -> 남아있는 최솟값은 2
heappush(a, 7)          # 힙에 7을 추가
print(a[0])             # 2
heappush(a, 0)
print(a[0])             # 0

 

최소 힙 구하기

from heapq import *
from sys import stdin

input = stdin.readline

N = int(input())
# 아무것도 없는 상황에서는 heapfify를 해줄 필요가 없다. 
# 만약 리스트에 원소들이 채워진 상태라면 해줘야함 
heap = []
for _ in range(N):
    a = int(input())
    if a:
        heappush(heap, a)
    else:
        if heap:
            print(heappop(heap))
        else:
            print(0)

 

최대 힙 구하기

파이썬에서 제공되는 힙은 최소 힙이다. 만약 최대 힙이 필요하다면? ⇒ 음수부호(-) 활용

from heapq import *
from sys import stdin

input = stdin.readline

N = int(input())
heap = []
for _ in range(N):
    a = int(input())
    if a:
        heappush(heap, -a) # - 값 삽입
    else:
        if heap:
            print(-heappop(heap)) # - 값을 삽입했으니, 추출할 때 - 다시 붙여주기
        else:
            print(0)

 

 

🤔 만약 heapq를 사용할때 원소가 튜플이라면 최소값이 어떻게 정해질까?

A. heapq에 튜플이 삽입될 경우, 튜플의 첫번째 요소가 정렬의 기준이 된다.

from heapq import *

heap = [(1, 1), (4, 9), (2, 4), (2, 7), (5, -3), (1, 3)]
heapify(heap)
for i in range(len(heap)):
    print(heappop(heap))

# print
# (1, 1)
# (1, 3)
# (2, 4)
# (2, 7)
# (4, 9)
# (5, -3)

 

 

2. 해시 테이블 (Hash table)

key와 value를 매핑한 자료 구조. 키는 해시 함수를 사용해 해시를 얻을 수 있다. 해시는 값이 저장되어 있는 해시 테이블의 인덱스를 찾을 수 있는 값이다. 해시 함수에 키를 넣으면 해시 테이블에서 매칭되는 결과 값에 바로 접근할 수 있고, 따라서 연산은 평균적으로 O(1)의 시간 복잡도를 가진다. 파이썬의 dictionary나 collections.defaultdict를 활용하여 구현할 수 있다.

• 기본 연산

age_mapper = {}
age_mapper["감자"] = 20 # 신규 값 추가
age_mapper["감자"] += 1 # 기존 값 갱신
print(age_mapper["감자"])

del age_mapper["감자"] # "철수"에 해당하는 매핑을 삭제

 

 

해시 테이블 예시 코드

n = input()
sources = list(map(int, input().split()))
visited = {}
for source in sources:
    visited[source] = 1

m = input()
targets = list(map(int, input().split()))
for target in targets:
    print(visited.get(target, 0))

 

기타

Q. 파이썬 리스트에서 append와 extend의 차이?

A. append는 리스트 끝에 요소 하나만 넣는다. extend는 리스트 끝에 바깥쪽 iterable의 모든 항목을 넣음. 

아래의 코드처럼 [4, 5]의 리스트를 추가한다고 했을때 append는 리스트 자체를 추가하지만 extend는 리스트 내부의 요소들을 추가하려는 배열에 각각 넣어준다. 

a = [1, 2, 3]
b = [4, 5]
c = [1, 2, 3]
d = [4, 5]

a.append(b)
c.extend(d)
print('a',a) # a [1, 2, 3, [4, 5]]
print('c', c) # c [1, 2, 3, 4, 5]

 

 

------

자료구조 힙과 해시테이블 공부를 하고 알고리즘 문제들을 풀었다. 개념을 정리하고 읽어보면 코드에도 바로 적용할 수 있을 것 같고 그래야 할것 같은데 막상 알고리즘 문제를 보면 말하는 감자가 되는 것 같은 기분이다^.ㅠ 아직은 어떤 문제에 어떤 알고리즘을 적용해야하는지 감이 잘 안오는데 계속 하다보면 나아지겠지... 그래도 요즘은 강의를 듣고 내용을 정리하고 문제를 풀다보면 무엇을 사용해야할지 조금은 알 수 있어서 좋다. 그리고 사실 정 안될때는 백준 문제 아래쪽에 있는 태그를 본다 ㅋㅋㅋ 그래도 정 안되면 구글링을 하고 그러고 다시 풀어본다. 잘 하고 있는건가 싶기도 한데 일단은 질문할 수 있을 정도의 내공을 쌓는것이 필요할것같다. 아무튼... 오늘도 이겨냈다^.^