one Book a Day

강의실의 갯수N = queue의 방의 갯수. 최소 heap을 사용해 가장 빨리 돌아오는 수업 종료시간보다 시작해야하는 수업이 빠르면 방 하나 증가 적으면 끝난수업빼고 새수업 넣는다. 즉 최대 필요한 room의갯수가 계속유지된다. 최솟값, 최댓값을 계속 뽑아내야 할때는 heapq.. 잘 생각해보자 import heapq import sys N = int(input()) timeTable = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] timeTable.sort(key=lambda x: x[0]) queue = [] heapq.heappush(queue,timeTable[0][1]) for i in range(1,N): # last_tim..

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다. 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달. 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다. 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다. 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다. 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 ..