나의 개발일지

문제 : https://www.acmicpc.net/problem/1202 🔑 힙, 우선순위 큐 1. 입력받은 보석들을 무게 기준 오름차순 정렬 2. 가방도 오름차순 정렬 3. 가장 작은 가방부터 시작해서 이 가방에 담을 수 있는 보석이면 힙에 보석 가격을 담는다. (음수로 담는다. 최대힙) 4. 담긴 보석이 있으면 가장 비싼 보석을 선택한다. 3, 4번 과정을 가방 개수만큼 반복한다. 크기가 작은 가방부터 담기 때문에 보석을 모두 담고 뽑아내는 게 가능하게 된다. 크기가 2인 가방에 담을 수 있는 보석이면 크기가 3인 가방에도 담을 수 있다. 가방 크기 = [2, 10] 보석 = [(1, 65), (2, 99), (5, 23)] 가방 크기 2일 때 힙 = [-99, -65] -99를 뽑아서 정답으로 올..

문제 : https://www.acmicpc.net/problem/1715 🔑 최소 힙 힙에서 가장 작은 수 두 개를 뽑는다. heappop 두 번 뽑아낸 두 수를 더해서 힙에 다시 넣고 합한 값만큼 정답을 올려준다. from heapq import heappop, heappush import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): heappush(heap, int(input())) answer = 0 while len(heap) >= 2: x = heappop(heap) + heappop(heap) heappush(heap, x) answer += x print(answer)

문제 : https://www.acmicpc.net/problem/1927 🔑 최소 힙 from heapq import heappop, heappush import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): x = int(input()) if not heap and x == 0: print(0) elif x > 0: heappush(heap, x) else: print(heappop(heap))

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12927 🔑 최대 힙 works의 값들을 최대 힙으로 만든다. 최대 힙은 가장 큰 값이 가장 왼쪽에 있도록 한다. 최대 힙으로 만들려면 값들을 음수로 변경해서 힙에 추가하면 된다. works = [2, 4, 3] 일 때 이 값들을 음수로 바꿔서 힙에 넣으면 (heappush) [-4, -3, -2] 이렇게 가장 큰 값이 왼쪽에 있을 수 있다. heappop을 사용해서 가장 왼쪽 값을 빼낸 다음 1시간 작업한다. 4는 3이 돼야 하는데 현재 값은 -4로 되어있기 때문에 +1을 했다. 1시간 작업을 하고 빼낸 작업을 다시 힙에 넣는다. 이 작업을 n번 반복 후 야근 지수를 구하면 끝 ✨ from..

문제 : https://www.acmicpc.net/problem/15903 🔑 그리디, 우선 순위 큐 카드들을 heap에 담고 가장 작은 카드를 두 개 뽑아낸다. 뽑아낸 카드 두 개를 합쳐서 두 번 집어넣는다. 이 과정을 m번 반복하고 힙에 남은 카드들의 전체 합계를 구한다. 끝 ✨ from heapq import heapify, heappop, heappush n, m = map(int, input().split()) card = list(map(int, input().split())) heapify(card) for _ in range(m): x = heappop(card) y = heappop(card) heappush(card, x+y) heappush(card, x+y) print(sum(ca..

문제 : https://www.acmicpc.net/problem/1655 🔑 최대 힙과 최소 힙을 함께 사용 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) num = int(input()) print(num) minHeap, maxHeap = [],[-num] for i in range(n-1): num = int(input()) if num > -maxHeap[0]: heappush(minHeap, num) else: heappush(maxHeap, -num) if len(minHeap) > len(maxHeap): temp = heappop(minHeap) heappush(maxHea..

문제 : https://www.acmicpc.net/problem/1417 그리디, 최대 힙 사용 from heapq import heapify n = int(input()) dasom = int(input()) heap = [-int(input()) for _ in range(n-1)] # 최대 힙 구현을 위해 -를 붙여 저장 cnt = 0 heapify(heap) if n == 1: print(0) exit() while dasom

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42628 힙(heap) 🔑 최솟값 제거는 heappop()을 사용 🔑 최댓값 제거를 위해 pop()을 했으나 힙 자료구조는 모든 원소를 정렬하지 않기 때문에 마지막 값이 최댓값이라는 보장이 없다. 🔑 그래서 최댓값을 구할 때는 sort()로 새롭게 정렬을 해주고 pop()을 했다. (정답 리턴 때도 마찬가지) from heapq import * def solution(operations): heap = [] for i in operations: if i[0] == "I": heappush(heap, int(i[2:])) # 숫자 부분만 슬라이싱, 형 변환 후 힙에 추가 elif i == "D..