알고리즘/힙5 [Python] 백준 2841 외계인의 기타 연주 🧑💻 [Python] 백준 2841 외계인의 기타 연주 Silver 1 - 스택  코드 N, M = map(int, input().split()) stack = [[] for _ in range(7)] count = 0 for _ in range(N): l, p = map(int, input().split()) while stack[l] and stack[l][-1] > p: stack[l].pop() count += 1 if not stack[l] or stack[l][-1] < p: stack[l].append(p) count += 1 print(.. 2023. 3. 25. [Python] 백준 7662 이중 우선순위 큐 🧑💻 [Python] 백준 7662 이중 우선순위 큐 Gold 4 - Heapq 최소 힙과, 최대 힙을 사용하는 문제이다 두 개의 힙을 사용하면서, 숫자 관련된 참/거짓의 여부도 파악해야 한다 처음에는 두 힙에 숫자 하나가 모두 들어간다 그리고 숫자를 하나씩 뺄 때에는, 하나의 힙에는 그 숫자가 남게 된다 True의 경우는, 두 개의 힙에 동일한 숫자가 있을 경우를 True로 넣는다 I 는 힙에 숫자를 넣는 것 / D 1 최대 힙에서 숫자를 하나 빼는 것 / D -1 최소 힙에서 숫자를 하나 빼는 것 문제풀이 명령어 I 또는 D를 제일 먼저 확인 한다 I일 경우, 최대 힙과, 최소 힙에 숫자와 인덱스를 튜플로 넣는다 숫자 : 최대 힙과 최소 힙에서, 숫자들끼리 비교를 해야 함 인덱스 : True/Fal.. 2023. 1. 23. [Python] 백준 2109 순회강연 🧑💻 [Python] 백준 2109 순회강연 Gold 3 - 힙 강연을 하는데, 각 강연마다 강연료와 몇 일 안에 강연을 하는지 입력을 받는다 최대한 강연료를 많이 받을 수 있도록 코드를 짜야 한다 문제풀이 1 힙 리스트 안에, 강연료 기준으로 최대 힙으로 넣는다 즉 튜플 형태로 힘 리스트에 넣는 것 그리고 힙을 하나씩 빼면서, 강연을 해야하는 날이, False이면 True로 바꾼다 강연을 해야 하는 날이, True일 경우, 그 전날을 본다. 이것을 False를 찾을 때 까지 뒤로 탐색을 한다 만약 1일차까지 다 True일 경우는, 그 강연은 못 하는 것이다 문제풀이 2 일단 강의 날짜 기준으로 오름차순으로 정렬을 한다 그리고 강연료를 힙 안에 넣어준다 힙의 길이는 날짜와 같거나, 적어야 한다 넣었는데.. 2023. 1. 20. [Python] 백준 2696 - 중앙값 구하기 🧑💻 [Python] 백준 2696 - 중앙값 구하기 Gold 3 - heapq left와 right 힙 그리고 중간 값을 가지고 문제를 푸는 것이다 left는 최대 힙을 구하는 것이고, right은 최소힙을 구하는 것이다 middle은 제일 최근에 구한 중간 값이다 즉 수열의 원소가 middle보다 작으면 left로 들어가야 하고, 크면 right로 들어가야 한다 코드 import heapq import math T = int(input()) for _ in range(T): N = int(input()) nums = [] for _ in range(int(math.ceil(N / 10))): nums += list(map(int, input().split())) left, right = [], [].. 2023. 1. 17. 🧑💻 [Python] 백준 14235 - 크리스마스 선물 🧑💻 [Python] 백준 14235 - 크리스마스 선물 Silver 3 - Heap 입력된 값을 순회한다 입력된 값이 0이 아니면 선물을 충전하는 거점 0은 아이들의 집이다 문제풀이 입력 값들을 튜플로 받아서 리스트에 넣는다 그리고 for문을 순회하며 0인지 아닌지 구별한다 0이 아니면 선물을 충전하는 거점 즉 heap에 최대힙으로 선물에 대한 숫자를 넣는다 0이면, heap에 선물이 들어 있는지 없는지를 구별한다 heap에 숫자가 있으면, 제일 앞에 있는 숫자, 즉 제일 큰 숫자를 출력한다 없으면 해당 아이에게 줄 선물이 없다는 것. 즉 -1을 출력한다 코드 import heapq N = int(input()) stops = [] for _ in range(N): stops.append(tuple(.. 2023. 1. 16. 이전 1 다음
