힙

힙이란? 힙은 이진트리구조이다. 최대힙과 최소힙이 있으며 자식노드로 올수록 커지면 최소힙, 작아지면 최대힙이라 할 수 있겠다. 최소힙기준으로 설명을 하자면 양 자식노드의 값은 루트노드보다 작아야한다. 힙 구현 힙은 배열형태로 구현할 수 있다. 부모노드 인덱스 * 2가 왼쪽자식, 부모노드 인덱스*2+1이 오른쪽 자식 되시겠다. 삽입 힙의 삽입은 배열로 구현할 경우, 배열의 마지막 인덱스에 요소를 추가하는 것으로 시작된다. 그리고 해당 인덱스와 부모노드를 인덱스값이 작을떄까지(클때까지) 비교하며 둘의 위치를 조정한다. 루트까지 진행한다. add(value) { this.heap.push(value); let currentIndex = this.heap.length - 1; let parentIndex = M..

힙 그자체인 문제 import heapq n=int(input()) 결과=0 힙=[] for _ in range(n): heapq.heappush(힙, int(input())) while len(힙)!=1: 임시=heapq.heappop(힙) if 힙: 임시=임시+heapq.heappop(힙) 결과+=임시 heapq.heappush(힙,임시) print(결과)

괜히 힙 두개쓸려다가 개같이 멸망했던 문제 남은 숫자를 새 단위로 힙에 넣는걸 생각하지 못해서 굉장히 고민했다. 이번엔 특별히 한글 코드로 작성했다. 사랑해요 연예가중계 import heapq n,m=map(int,input().split()) # 24*n시간 후 시작 time=24*n # m과목 a=list(map(int,input().split())) b=list(map(int,input().split())) 결과=0 힙=[] for x in range(m): heapq.heappush(힙, [-b[x],a[x]]) while 힙: 힙에서뽑은거=heapq.heappop(힙) 단위,점수=-힙에서뽑은거[0],힙에서뽑은거[1] while 단위+점수0: 점수+=단위 time-=1 else: break if ..

각각 역에 대한 출발시간을 heap에 저장한다. 각 역은 save라는 heap을 가지며, 해당 heap보다 출발시간의 heap이 큰 경우, count가 커지지 않는다. 해당 heap의 출발시간이 save보다 작은경우, count는 커진다. heap에서 꺼낸 시간의 도착시간에 회차시간을 더한뒤에 상대편 역의 save에 push 한다. 코드가 매우 더럽다. 내일중으로 정리해서 업데이트 할 예정 import heapq from collections import deque from tracemalloc import start def function_a(a,acount,asave,bsave): now_a=heapq.heappop(a) start_hour,start_minutes=now_a[0].split(":")..

맥주파뤼~~ heap은 알콜이 낮은 순서로,. answer에는 prefer가 낮은대로 각각 두개의 heap을 사용했다. 입력된 값을 바로 heap에 넣어서 알콜도수가 낮은순대로 저장하고, 이들의 수가 n에 도달했을때, 만족도를 넘기지 못하면 answer의 값 중 가장 만족도가 낮은 것을 뺀다. 이때 만약 알콜이 가장 높은 것이면 두번째로 알콜값이 높은 값을 가장 높은 값으로 바꿔준다. 이걸 heap이 존재할때까지 반복하고, 없으면 -1를 출력하게 했다. 문제가 있었던 점은 second_alchol을 사용하지 않고, answer에서 반복문을 찾아서 maxalchol을 찾으려고 했더니 시간초과가 났다는 점이다. 시간초과가 난 코드 import heapq n,m,k=map(int,input().split())..

힙을 사용했다. 근데 동시에 가져올때 상민이 것(B)가 먼저 나와야하므로 임시 배열에 저장한 다음, B인 것 부터 힙에 넣어줬다. import heapq heap=[] tmpl=[] B=[] R=[] a,b,n=map(int,input().split()) for _ in range(n): t,c,m=map(str,input().split()) t=int(t) m=int(m) time=t first=1 for _ in range(m): if not first: if c=='B': time=time+a elif c=='R': time=time+b tmpl.append([time,c]) first=0 for x in tmpl: if x[1]=='B': heapq.heappush(heap,x) for x in ..