heap 2

[Python] 19598. 최소 회의실 개수

문제 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 풀이 과정 1931번 회의실 배정 문제가 떠오르는 문제였다. 처음에는 회의실이 없다면 새로 만들고 회의실마다 시간을 비교해주면서 계산하는 2중 for문을 생각했는데 그렇게 하면 시간 초과가 날 것 같아 고민을 했다. 가장 먼저 끝나는 곳을 찾고 비교하는 것이 관건이었으므로 최솟값과 최댓값을 빠르게 찾는 heap이 생각나 이를 사용하여 해결할 수 있었다. 회의 끝나는 시간을 heap에 넣고..

Algorithm/Baekjoon 2022.11.15

[Python] 5177. 이진힙

tc = int(input()) for idx in range(1, tc+1): n = int(input()) # 목표 노드 node = [0] + list(map(int, input().split())) # 노드들 받아오기 answer = 0 # 위치 바꾸기 for i in range(1, n+1): while node[i//2] > node[i]: # 부모가 나보다 클때 바꿔주기 node[i//2], node[i] = node[i], node[i//2] i //= 2 # 다음 조상도 검토 # 조상 노드 다 더하기 p = n//2 # n의 부모부터 시작이니까 while p > 0: answer += node[p] p //= 2 print(node) print('#{} {}'.format(idx, ans..