heapq
-
[자료구조] [python] [heapq] Minimum Average Waiting TimeData miner/Algorithm & Data structure 2021. 2. 17. 10:25
다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다. Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/minimum-average-waiting-time/problem Minimum Average Waiting Time | HackerRank Calculate the minimum average wait time of a person to receive his/her pizza? www.hackerrank.com 풀이 로직은 다음과 같다. 일단 어떤 작업이 끝난 시점에, 들어온 작업들 중에서 가장 작업량이 적은 주문을 선택해야, 전체의 평균 대기 시간을 줄일 수 ..
-
[자료구조] [python] [heapq] QHEAP1Data miner/Algorithm & Data structure 2021. 2. 9. 16:35
우선순위 큐(priority queue)는 각 항목에 우선순위가 있는 스텍/큐이다. 파이썬의 heapq 모듈에는 이를 구현 할 수 있는 힙heap 자료형이 있다. 힙(Heaps)는 이진트리이며, 부모노드가 자식노드보다 값이 작거나 같다. 루트인 heap[0]가 heap의 모든 요소들의 최소값이다. 배열, 리스트에서 가장 작은/큰 요소에 반복적으로 접근하는 작업에 유용하다. heapq.heapify(list) : 리스트를 힙으로 변환하는 시간 복잡도 O(n) heapq.heappop(list) : 가장 작은/큰 값 호출시 처리하는 시간 복잡도 O(1) heapq.heappush(list, item) : 값 조회, 새로운 값 추가, 수정시 처리하는 시간 복잡도는 O(log n) heapq.heappushpo..
-
[자료구조] [heap] 대기 시간 최소화Data miner/Algorithm & Data structure 2020. 3. 4. 21:02
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/minimum-average-waiting-time/problem Minimum Average Waiting Time | HackerRank Calculate the minimum average wait time of a person to receive his/her pizza? www.hackerrank.com 문제는 다음과 같다. 피자 가게에서 고객들의 대기시간을 최소화하는 것을 목표로 평균 대기시간을 구하는 것이다. 피자 만드는 시간은 각기 다르며, 주문이 들어올 때, 선입선출(First in, Fir..
-
[자료구조] [heap] 업데이트 되는 array값의 중앙값 구하기Data miner/Algorithm & Data structure 2020. 3. 3. 17:33
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/find-the-running-median/problem?h_r=internal-search Find the Running Median | HackerRank Find the median of the elements after inputting each element. www.hackerrank.com 연속적으로 주어지는 배열의 평균값들을 반복적으로 구하는 문제이다. [12,4,5,3,8,7]이 주어지면 앞에서부터 한 개씩 차례대로 추가하여 추가된 값들까지의 중앙값을 구하고, 이들이 포함된 리스트를 구하면 ..