문제가 잘 풀리지 않는다.. 어디까지 공부를 해야할지도 모르겠고, 이것도 해야할 거 같고 저것도 해야할 것 같아서 마음은 급한데, 별로 성과가 안나오는거 같아서 ㅎㅎ
Today I Learn : heapq,set()
#heapq
힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.
- 최소 힙: 부모 노드의 키값이 자식노드의 키값보다 항상 작은 힙
- 최대 힙: 부모 노드의 키값이 자식노드의 키값보다 항상 큰 힙
python에서는 Priority Queue보다 heapq를 많이 사용한다. (빠르게 동작)
python의 힙은 최소 힙 (Min_heap)으로 구성되어 있다 == 최소 힙의 자료구조의 최상단 원소는 항상 '가장 작은 원소'가 된다
heap 함수 활용하기
import heapq
- heapq.heappush(heap,item) : item을 heap에 추가
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴, 비어있는 경우 IndexError
- heapq.heapify(x) : 리스트 x를 heap으로 변환함
힙 생성 & 원소 추가
import heapq
heap = []
heapq.heappush(heap,50) # heap에 50원소 추가
heapq.heappush(heap,30) # heap에 50원소 추가
heap2 = [10,20,30]
heapq.heapify(heap2)
힙에서 원소 삭제
res = heapq.heappop(heqp) #가장 작은 원소를 힙에서 제거 & 결과 값을 리턴
print(res)
#10
print(heap)
#[20,50]
res2 = heap[0]
print(res2)
#20최대 힙 만들기
파이썬의 heap 모듈은 최소힙으로 구성되어 있어 최대 힙 구현을 위해서는 다른 방법이 필요하다
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap,(-item,item))
print(max_heap)
#[(-9,9),(-7,7),(-3,3)#set()
수학에서 말하는 집합 연산자를 뜻한다.
순서가 없고, 집합 안에서는 unique한 값을 가진다.
set의 기본 함수
set(집합)의 선언
- 중복 된 값은 자동으로 제거가 됨
- set은 순서가 없어서, 어떤 값이 먼저 나올 지 알 수 없다.
s1 = set()
s1 = {1,3,5,5,7,8,8}
print(s1)
# {1,3,5,7,8}set의 원소 추가 (add) / update
s1.add(10)
print(s1)
# {1,3,5,7,8,10}
#update는 수정보다는 여러데이터를 한번에 추가할 때 사용
s1.update([10,12,13])
print(s1)
# {1,3,5,7,8,10,12,13}set의 원소 제거 (remove/ discard)
두 메소드의 차이는 item에 해당하는 원소를 제거하고, 없으면 Erorr 발생 여부
k = {1,2,3}
k.remove(3)
print(k)
# {1,2}
k.remove(5)
# 에러 발생
k.discard(1)
print(k)
#{2}set의 연산 - 연산자
heeeeello