Dalin's Archive

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 예전 코드(시간 초과) import heapq as hq N=int(input()) a = [] for _ in range(N): n = int(input()) if n == 0: if len(a) == 0: print(0) else: tmp=-hq.heappop(a) # 루트 노드 값 print(tmp) else: hq.heappush(a, -n) -> 잘 짜서 놀랐다(??)..

문제 보러가기! 풀이 🌷 지문이 웹툰 내용 같고 재미있었다 ㅋㅋ 핵심은 슬라임 에너지가 적은 슬라임을 두 개씩 합성하는 것이다!! 그걸 파악한 후에는 카드 정렬하기 문제와 비슷하게 풀었다. 카드 정렬하기 문제에서는 더하기라면, 이 문제에서는 곱하기라는 점 정도만 다른 것 같다. 아래와 같이 풀었다. 처음 슬라임을 리스트로 받은 후에 heapify하기 청구될 전기 에너지 초기값은 1로 시작하기(곱의 항등원은 1이므로) 힙의 길이가 2 이상일 동안은(즉, 슬라임이 두 개 이상일 때) 힙에서 슬라임 에너지가 적은 슬라임을 두 개 꺼낸다. 각각 슬라임 에너지가 A, B 라고 하자. 그 둘을 곱하면 슬라임 에너지가 AXB인 슬라임이 되고, 그걸 힙에 넣는다. 또 청구될 전기 에너지에 A X B한 값을 곱한다. 힙..

문제 보러 가기! TMI 내 기억 상 처음으로 푸는 영어 문제이다. 풀이 🦄 문제 이해를 돕기 위한 설명용 그림..ㅎㅎ 처음에 1번 섬에서 무조건 시작하고, 그 병력을 가지고 시작한다. 지배한 섬과 이어진 섬은 공격 후보가 된다. 이어진 섬의 병력이 우리(spanning nation) 병력보다 적을 때만!! 그 섬을 지배한다. 우선순위 큐를 활용하면 된다. 우선순위 큐, q에 공격할 수 있는 후보들(섬)을 집어 넣었다. 인접 리스트로 섬들의 연결 관계를 저장한다. 각 섬의 병력을 island_army 리스트에 저장한다. 각 섬을 공격할 수 있는 후보(q)에 넣었는지 여부를 저장하는 visited 리스트를 만든다. 1번 섬에서 시작한다. 우리 병력(spanning_army_cnt)를 1번 섬의 병력으로 업..

문제 보러 가기! 내 근황 (TMI..) 꺄~ 싸피 공통 PJT를 잘 마무리하고 돌아왔다 ~~!! 마지막 열흘 정도는 PJT에 집중하느라고 PS를 못하다가 오랜만에 문제를 풀었다 !! 내가 좋아하는 heapq를 이용하면 되는 문제였다. 설명 카드 묶음 여러 개가 있는데, 두 묶음씩 골라서 합쳐나간다. 합칠 때는 그 두 묶음의 개수만큼 비교를 해야 한다. 최소 몇 번의 비교가 필요한가? -> 적은 것부터 합치는 게 좋다 !!라는 걸 파악하고 heapq를 사용하면 됐다. 비교 개수를 담을 변수인 cnt를 0으로 초기화하고 시작했다. q에 숫자 카드 묶음 각각의 크기를 넣었다. heapify를 이용해서 q를 우선순위 큐로 만들어줬다. 그리고 q의 크기가 1이 될 때까지, 가장 적은 것 두 개씩을 더해서 다시 ..

문제 보러 가기! 처음 풀이- 시간 초과 🎇 가방 많이 넣을 수 있는 것부터 하나씩 보면서, 보석을 가격 비싼 순(가격 같으면 무거운 순)으로 봤다. 그 가방에 보석을 넣을 수 있으면, 보석 없애고 가방도 없애고.. 그 가격을 정답에 더했다. 그 가방에 그 보석을 못 넣으면 그냥 보석을 없앴다. (어차피 이후 가방에도 그 보석이 무거워서 못 넣으니까) 예제는 맞기는 한데,, 그랬더니 시간 초과 ㅠ 코드는 이랬다. import sys, heapq input= sys.stdin.readline N,K = map(int,input().split()) jewelries = [] backpacks = [] for _ in range(N): m, v = map(int,input().split()) jewelries..

문제 보러 가기! NXN의 표에 수가 채워져있고, 모든 수는 자기 한 칸 위의 수보다 크다. N번째 큰 수를 찾는 문제이다. (N은 1~1500이다.) 처음 - 메모리 초과 처음에는 extend를 이용해서 1차원 리스트로 N^2개의 값을 다 받았다. 이 문제에서 N번째로 '큰!!" 수를 찾아야 하므로 최대 우선순위 큐로 쓰려고 했다. 그래서 -1을 곱해서 넣어줬다. 그 후, 그 리스트를 우선순위 큐로 만들었다. heapq.heappop을 N번해서 N번째값을 출력했다. -1를 곱해서 넣어줬으니까, 출력할 때 -1을 곱한 후에 출력했다. 예제는 맞는데, 메모리 초과가 나왔다.. 1500 X 1500 = 2250000 개를 리스트로 만들고 힙으로 만드는 게 너무 힘든가.. import sys, heapq in..

문제 보러 가기! 문제 🤔 버스가 종점에 들어온다. 종점에 와서는 정비를 해야 하기 때문에, 버스 정비 공간에 가야 한다. 버스가 종점에 들어오는 시각, 종점에서 나가는 시각이 주어진다. 버스 정비 공간이 최소로 몇 개 필요한지 계산하는 문제 즉, 한번에 종점에 버스가 최대 몇 개까지 있는지를 계산하는 문제이다! (단, 같은 시각에 종점에 들어오는 버스- 나가는 버스가 있으면 먼저 나간 후에 출발한다) 아이디어 😍 일단은 버스가 들어오고 나가는 시각이 복잡하게 들어오기 때문에(HH:MM:SS.sss) 편하게 바꿔줬다. 다행히도 들어오는 숫자의 자릿수는 늘 같으니까, 시각에 곱하기 천만 + 분에 곱하기 십만 + 초에 곱하기 천+ 밀리초는 그대로 받아왔다. 그러면 하나의 숫자가 되어서 다루기 편하다. 그리고..