나의 개발일지

문제 : 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/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/11000 그리디, 정렬, 우선 순위 큐 import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) lst = [list(map(int, input().split())) for _ in range(n)] # s에 시작 t에 끝나는 수업 [s, t] lst.sort() # 수업 시작 시간으로 정렬 room = [] heappush(room, lst[0][1]) # 첫 강의 끝 시간 for i in range(1, n): if lst[i][0] < room[0]: # 다음 수업 시작 시간이 현재 수업 종료 시간보다 작으면 (강의 중이면) h..

문제 : 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..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42627 힙(heap) 🔑 현재 시간에 작업할 수 있는 작업들 중 소요 시간이 적은 작업을 찾기 🔑 현재 시간에 작업할 수 있는 작업이 없으면 먼저 들어온 요청 시간을 현재 시간으로 업데이트 🔑 우선순위 큐인 heapq에 작업을 추가하면 소요 시간이 적은 작업 순으로 자동 정렬이 일어남 from heapq import * def solution(jobs): # 정답, 처리한 작업 수, 현재 시간 answer, cnt, time = 0, 0, 0 heap = [] # 우선순위 큐 jobs.sort() # 요청 시간 기준으로 오름차순 정렬 while True: while cnt < len(job..