최소힙

[python3] 백준 11000 (강의실 배정, 최소힙, 그리디)

1~3시, 2~4시, 3~5시의 강의가 존재할때 최소 몇개의 강의실이 필요한지 구해야한다. 보통 강의실 문제는 그리디로 하나의 강의실이 존재할때 몇개의 수업이 가능한지는 물어보는 문제가 많았던거 같은데 이번에는 강의가 존재할때 몇개의 강의실이 필요한지 구해야한다. 처음에는 갈피를 못잡았다. 그리디 같은 느낌이 들어서 정렬을 해보고 구하려고 했는데 잘 구해지지 않았다. 그래서 알고리즘 분류를 보니 예상도 못한 우선순위 큐가 존재했다. 우선순위 큐를 사용해야한다는 힌트를 보자 바로 풀이가 떠올랐다. 우선 우선순위 큐에 들어가야하는것은 강의실이 될 수 있다. 즉, 해당 강의실을 몇시부터 몇시까지 쓰는 큐가 된다. 처음에는 1-3시에 강의실을 사용할 것이기 때문에 큐에 A(1-3)으로 넣는다. 2-4강의는 A(..

백준 1655 풀이 (가운데를 말해요, 우선순위 큐)

이 문제는 우선순위 큐를 이용하여 중간에 존재하는 값을 출력하면 된다. 방법은 우선순위 큐를 2개 만들어서 푸는 문제이다. 최대 힙과 최소 힙을 사용하여 정렬을 유지하면 된다. 왜 이런 방식을 사용해야 하냐 만약 우선순위 큐에 값을 넣으면 저렇게 배열이 된다. 그래서 저 상태로는 중간값을 뽑을 수가 없다. 그런데 최대힙과 최소힙을 사용하면 중간값을 찾을 수 있다. 우선 최대힙의 [0]위치에는 최댓값 4를 가지고 최소힙의 [0]위치에는 최솟값 7을 가진다. 따라서 모든 힙이 정렬되지 않아도 중간값이 4라는 것을 알 수 있다. 따라서 새로운 입력에 대해서 최대힙의 개수와 최소힙의 개수를 동일한 비율로 맞춰주면 문제가 없다. 그러나 새롭게 입력되는 값이 -99인경우 최소힙에 3개의 값이 들어있기 때문에 -99..

백준 11286 풀이 (절댓값 힙, 최소 힙, heapq)

이번 문제는 새로운 기준으로 우선순위 큐를 만드는 문제였다. 힙에 값이 존재할때 절댓값을 기준으로 가장 작은 값을 뽑는다. 만약 절대값이 같은 수가 있다면 그중 가장 작은 수를 뽑는다. 처음에는 힙이 미리 값을 넣어놓은 상태에서 힙을 어떻게 탐색해야할지 고민을 했다. 그런데 생각해 보니, 애초에 절댓값과 실제 값을 같이 넣어도 되지 않을까 라는 생각을 하게 되었다. 그래서 절댓값과 실제값을 튜플로 넣고 출력하면 되지 않을까 싶었다. import sys import heapq n = int(input()) heap=[] for _ in range(n): t = int(sys.stdin.readline()) if t == 0: if len(heap) == 0: print(0) else: print(heapq..