Heap3 [python]2696_중앙값 구하기 1 사용한 자료구조 및 개념 : heap 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ heap을 사용하여 중앙값을 구한다. 2️⃣ max_heap에는 중앙값을 포함한 왼쪽 부분을 저장하고, min_heap에는 오른쪽 부분을 저장한다. 3️⃣ 배열은 0번부터 시작이니 짝수번째에서 중앙값을 구한다. 4️⃣ (배열의)짝수번째일 때, 숫자가 min_heap의 최솟값보다 크다면 min_heap에 추가하고, 작다면 max_heap에 추가한다. min_heap에 추가했다면 max_heap에서 숫자 하나를 pop하여 min_heap에 추가한다. → 이때, 중앙값은 정렬한 수열에서 항상 가운데 있다. 따라서 중앙값을 효율적으로 찾기 위해 max_heap의 크기는 min_heap의 크기보다 1만큼 크거나 같아.. 2023. 8. 23. [python] 힙(heap)과 힙큐(heapq)란? 힙(heap) 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조 완전 이진트리 힙 property A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다. 최소 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 된다. 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 키 값의 대소 관계 부모/자식 노드 ⭕ 형제노드 ❌ 시간복잡도 O(log n) 최소힙(heapq 모듈을 사용하지 않고 구현) # 최소힙 # 힙 삽입 연산 def heap_push(item): heap.append(item) child = len(heap) -.. 2023. 8. 11. [python]11286_절대값 힙 1 사용한 자료구조 및 개념 : heap 💡 문제풀이 아이디어 및 어려웠던 점 💫 아이디어 1️⃣ 입력된 x 값이 0이 아닌 경우, x 값을 추가한다. 2️⃣ 절대값이 작은 순서대로, 그리고 실제 값이 작은 순서대로 정렬시킨다. 3️⃣ 입력된 x 가 0인 경우, 힙에서 값을 추출하고 출력한다. 4️⃣ heapq.heappop 은 힙에서 가장 작은 값을 제거하고 그 값을 반환한다. 5️⃣ 튜플 형태로 저장하기 때문에 [1] 인덱스를 사용한다. 6️⃣ 힙이 비어 있다면 0을 출력한다. Solution Code & 주석 import heapq import sys # 입력받을 연산의 개수 N = int(input()) # 힙 초기화 heap = [] for _ in range(N): x = int(sys.std.. 2023. 8. 11. 이전 1 다음