나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/142085🔑 우선순위 큐 (hqepq)먼저 무적권 횟수만큼 라운드를 클리어하고 큐에 적 정보를 저장한다. (heappush)무적권을 다 사용했으면 클리어 한 라운드 중 가장 적이 적었던 라운드를 무적권이 아닌 병사로 처리한다. (heappop)병사로 처리했으므로 무적권을 다시 사용할 수 있음위 방법으로 무적권을 효율적으로 사용해서 라운드를 최대한 클리어할 수 있다. from heapq import heappush, heappopdef solution(n, k, enemy): answer = 0 hq = [] for i in range(len(enemy)): ..

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

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42626 heapq 모듈 사용 heapq는 이진 트리 기반의 최소 힙 자료구조를 제공 최소 힙으로 항상 오름차순 정렬되어 있다. 정렬된 상태를 유지해야 할 때 계속 정렬할 필요가 없어 속도가 빠르다. heapity() : 리스트를 heap으로 변환, O(N) heappush() : heap에 원소 추가, O(log(n)) heappop() : heap에서 가장 작은(0번 인덱스) 원소 삭제, O(log(n)) from heapq import heapify, heappush, heappop def solution(scoville, K): answer = 0 heapify(scoville) # ..