heap3 [프로그래머스] 야근 지수 / 파이썬 / Python / heap 💡 solutions 💬 야근 피로도를 최소한으로 만들기 위해서는 주어진 N시간 동안 works 리스트 안의 작업량 요소들을 가장 큰 값부터 -1씩 줄여나가는 과정이 필요하다. 💬 works와 n의 크기를 고려했을 때, 효율성을 통과하기 위해서는 값을 비교하는 로직을 위해 heaq 자료 구조를 사용해야 한다. 💬 주어진 예제 중에 3번과 같이 주어진 N시간 동안에 모든 작업량을 모두 끝마칠 수 있는 경우에는 0을 바로 리턴할 수 있도록 조건을 추가해야 한다. 👨💻 code import heapq def solution(n, works): answer = 0 if sum(works) 2021. 12. 26. [프로그래머스] 디스크 컨트롤러 / 파이썬 / Python / heapq 사용 💡solutions ) 💬 참고 : 디스크 컨트롤러 문제에서 요구하는 작업 처리 방식은 FIFO(First In First Out)가 아니라 SJF(Shortes Job First)방식이다. 즉, 요청된 작업들 중 가장 짧은 작업시간을 요구하는 작업부터 우선적으로 처리하는 방식이다. -> 이런 방식으로 진행하면 각각의 요청된 작업들의 대기 시간을 줄일 수 있다는 장점이 있다. (비선점형 스케줄링 방식에서 평균 대기 시간이 가장 짧다) 💬 heapq 모듈을 통해 최소 힙 사용하였음 -> heap에 작업의 소요시간, 작업이 요청되는 시점 순서로 값을 넣으면 (이번 예제에선 heap = [[3, 0], [6, 2], [9, 1]] 순으로 들어가는 셈) -> heappop할 때 작업의 소요시간을 기준으로 가장 .. 2021. 10. 29. [백준] 최단경로 / 1753번 / 파이썬 / Python / Dijkstra 💡solutions ) 💬 이번 문제는 최단 경로를 풀 때 가장 대표적인 다익스트라 알고리즘을 통해 해결했다. 💬 heap 자료구조 사용하여 heappop()을 했을 때 가장 최단 경로가 나오게 한다. 🎫code ) import heapq import sys input = sys.stdin.readline def dijkstra(v, s, adj): dist = [INF] * (v + 1) # 최단경로 리스트 dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) # 최소힙 이용 for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c h.. 2020. 10. 9. 이전 1 다음
