개발노트

문제 정렬되지 않은 배열에서 K번째 큰 요소를 추출하라. 풀이 1. heapq 모듈 - heappush, heappop 함수 이용 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heap = list() for n in nums: ## - 부호 붙여서 의도적으로 max heap 으로 구성 heapq.heappush(heap,-n) for i in range(k-1): heapq.heappop(heap) ## 의도적으로 음수 만들어준것을 다시 원래 값으로 복원 return -heapq.heappop(heap) 풀이 2. heapq 모듈 - heapify 함수 이용 class Solution: def findKthLarges..

우선순위 큐란? 우선순위 큐는 먼저 들어온 데이터가 먼저 처리되는 일반적인 큐와 달리, 우선순위가 높은 데이터부터 처리되는 자료구조이다. 배열, 연결리스트, 힙(Heap)으로 모두 구현할 수 있지만 일반적으로는 시간복잡도가 적은 힙(Heap)을 사용한다. 힙(Heap) 힙(heap)은 힙의 특성(최소 힙에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조이다. 최솟값, 최댓값을 찾아내는 연산을 빠르게 할 때 사용한다. 힙은 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있다. 힙은 정렬된 구조가 아니다. 부모-자식 간의 관계만 정의할 뿐, 좌우에 대한 관계는 정의하지 않는다. - 최소 힙: 루트노드가 가장 작은 값을 가지며, 항상 부..