Status
- 아 늦게 회사에서 마치고 운동하러 갔다 오는 게 이렇게 힘든 일이었나
저번 주는 거의 운동을 못 가다시피 했다. - 주말도 공지 안 보고 늦어서 팀 WOD 없이 혼자 운동..
-
그래서 이번 주 목표 : gym 휴무 날을 빼고 무조건 간다!
- 집 근처의 gym은 9시가 마지막 타임이라 결국 시간 배정이 애매해져 제외되다 보니, 어서 결국 다니던 먼.. 곳을 계속 등록하게 되었다
-
다행히 이곳은 9시 30분 한타임 더 운영함
- 최대한 회사에서 공부를 마치고, 올 때 앉아서 인강 공부를 이어서 하기로 결심했다
-
그리고 오늘…. 9시 반 타임 들어가서 운동 + 추가 줄넘기 250개를 채우고 집에 왔다
- 분명 도보 시간을 줄이기 위해 지하철을 타고 귀가했는데, 11시다?
씻고나니 12시 실화냐
주말
- 주말마다 바쁘다.
- 스터디에, 프로젝트에... 게다가 시험시험시험!
- 기사 자격증 (정보기, 정처기 ) 두 시험 모두 한 달 조금 남았다
진짜.. 너무 바쁜데 아무것도 못 이루고 흐지부지될까 봐 미칠 것 같다
Python
- heap
- 바이너리 구조 ( 이진 트리 )
- 최댓값, 최속값 찾는 연산을 빠르게 처리하기 위한 완전 이진트리가 기본!
- 부모 자식 노드간에 "키값" 대소 관계가 성립
- 형제 노드 사이간 대소관계 없음
최소 힙
-
인덱스 0 부터 시작해 k 번째 원소가
항상 자식원소들(leaf) ==(2k+1, 2k+2)
보다 작거나 같은 Minimum Heap- 오름차순 구현용
-
호출:
- 참고로 heapq는 기본 내장함수
import heaq from heaq import heaqpush,heappop... heap = [] -
힙 정렬 :
for i in range(1,6): heapq.heappush(heap,i) -
힙 출력 :
for i in range(5): print(heapq.heappop(heap))최대 힙
-
부모 노드의 값이 자식 노드의 키값 보다 항상 크거나 같다
key(부모) >= key(자식)- heapq에선 최대 힙을 제공하지 않는다!
-
부호를 변경하는 방식으로 최대힙 구현.
- 즉 부호를 바꿔 최소 힙에 넣어준 뒤 최솟값부터 pop을 해줄 때 다시 부호를 바꿔주면 최대 힙과 동일하다
-
내림 차순 구현용
- 선언
max_heap= []
- 최대 힙 생성
heap_item=[1,3,5,7,9]
for item in heap_items:
heapq.heappush(max_heap, (-item,item))
print(max_heap)
- 출력
[(-9,9), (-7.7), (-3,3),(-1,1),(-5,5)]
- 최대힙 -> 최소힙
for i in range(5):
print(-heapq.heappop(heap))
- 출력
5 ,4, 3, 2 ,1- 최대 힙의 최댓값 반환
max_item = heapq.heapop(max_heap)[1]
print(max_item)- 출력
9힙 함수
-
heapq.heappush(heap,item) :item을 heap 추가
-
heapq.heappop(heap) :
- heap에서 가장 작은 원소 pop 해서 return한다
- 비어있는 경우 IndesError()
- heap에서 가장 작은 원소 pop 해서 return한다
-
heap.heapify(x) : 리스트 x를 즉석으로 heap으로 변환한다 `O(n)
-
힙 생성 :
import heapq
heap1 = []
# 원소 삽입
heapq.heappush(heap1, 50)
heapq.headpush(heap1,10)
heapq.heappush(heap1,20)
# 원소 삭제
result = heapq.heappop(heap1)
print(result)
print (heap)
# 10
# [50,20]- 힙 자료형 변환
heap2 = [50,10,20]
heapq.heapify(heap2)
print(heap2) #[10,50,20] - 삭제 heap 대신, 인덱스로 접근할 경우 heap 원본이 그대로 있게 된다
시간 복잡도
- 배열, 연결 리스트 == O(n)
- 힙 트리 === O(log₂n)
우선순위 큐 와 힙
-
queue :FIFO
-
먼저 들어오는 데이터 X
우선순위 높은 데이터 먼저 나가는 구조 -
push, pop 두가지 연산이 지원되어야 함.
-
같은 우선순위일 경우 먼저 들어온 원소 처리
-
호출 :
from queue import PriorityQueue q = PriorityQueue() q1 =PriorityQueue(maxsize=10) # maxsize를 통한 크기 제한 가능 -
put(item)
q.put(3)
q.put(4)
q1.put((1, 'applp')) # 우선순위, 값
- get()
q.get() # 원소를 갖고온다
q1.get()[1] #우선순위, 값 의 형태에서 값 반환 비교 C 에도 우선순위 큐 힙이 있음
- insert(x)
- x를 마지막 노드에 이어서 새로운 노드로 추가
- 새로운 노드와 부모 노드 비교하며 교환
- 정상적인 힙트리 될 때까지 반복
- remove()
- 우선순위 큐에서 가장 우선순위 높은 요소 삭제 후 반환
- 시간복잡도 O(log₂n)
- find()
- 가장 우선순위 높은 요소 반환
🏠TECH & GOSSIP