본문 바로가기

🧩 Algorithm/우선순위 큐6

[백준] 1927번: 최소 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨 백준 1927번: 최소 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최소값 출력하기 print(heapq.heappop(heap) if heap != [] else 0) # 힙이 비어있지 않을 때만 heappop() 하기 else: heapq.heappush(heap, num) # 힙에 숫자 넣기 2023. 2. 28.

[백준] 11279번: 최대 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨. 그렇다면 가장 큰 값을 반환하려면..? 3. 힙에 넣은 숫자들을 마이너스 해서 넣는다면 heappop() 했을 때 어떤 숫자가 먼저 뽑힐까? 백준 11279번: 최대 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최대대값 출력하기 print((heapq.heappop(heap))*(-1) if heap != [] el.. 2023. 2. 26.

[백준] 2075번: N번째 큰 수 Hint 1. 우선순위 큐 - 힙(heap) 자료구조 이용하기 (그게 뭐지?) 2. 힙에서 heappop()을 이용하면 작은 수 부터 출력된다! 백준 2075번: N번째 큰 수 (풀어보기) import heapq N = int(input()) heap = []# 새로운 힙 만들기 for i in range(N): for num in map(int, input().split()): heapq.heappush(heap, num)# 힙에 숫자 삽입하기 if len(heap) > N:# 힙의 원소의 개수가 N개를 넘어가면 heapq.heappop(heap)# 힙에서 가장 작은 수 제거하기 print(heapq.heappop(heap))# N번째로 큰 수 출력하기 2023. 2. 24.

[백준] 11286번: 절댓값 힙 Hint 1. 힙 자료구조에 튜플을 넣을 수 있다 2. 힙 안의 튜플은 들어있는 순서대로 작은거부터 큰거까지 정렬된다 3. 힙 응용방법 알아보기 (여기) 백준 11286번 (풀어보기) import heapq import sys heap = [] for i in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) if n == 0: if heap == []: print(0) else: print(heapq.heappop(heap)[1])# 가장 작은 절댓값을 가진 숫자 n 출력하기 else: heapq.heappush(heap, (abs(n), n))# 튜플 형태로 n의 절댓값과 n을 둘 다 넣어줌 2023. 2. 21.

힙(Heap) 응용방법 Goal 1. 힙의 응용 방법 알아보기 함수 heappop() 이용하기 중요한 점은 heapq.heappop(heap)은 항상 heap에서 가장 작은 값을 반환한다는 것이다. 작은 수 ➡️ 큰 수 아래와 같이 1에서 5까지의 숫자가 있을 때 heap을 이용하면 가장 작은 수부터 순서대로 뽑는 것은 간단하다. import heapq arr = [1, 2, 3, 4, 5] heap = [] for num in arr: heapq.heappush(heap, num) for i in range(len(heap)): print(heapq.heappop(heap))# 출력: 1 2 3 4 5 큰 수 ➡️ 작은 수 거꾸로 힙을 이용해서 큰 수부터 순서대로 뽑는 것도 가능하다. import heapq arr = [1,.. 2023. 2. 10.

우선순위 큐 Goal 1. 우선순위 큐 이해하기 2. 힙(Heap) 자료구조 이해하기 우선순위 큐란? 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다 파이썬에선 힙(heap)이라는 자료 구조로 구현이 가능하다 힙(heap)이란? 완전 이진 트리(Complete Binary Tree)로 루트 노드에 있는 값은 트리에서 최대값 (Max Heap) 혹은 최소값 (Min Heap)이다 부모 노드의 값이 자식 노드의 값보다 항상 크거나 (Max Heap) 항상 작다 (Min Heap) 2023. 2. 9.

이전 1 다음

티스토리툴바