🗒️ 우선순위 큐
- 큐는 먼저 들어온 데이터가 먼저 처리되는 자료구조이지만, 우선 순위 큐는 우선 순위가 높은 데이터부터 처리하는 자료구조이다. 배열, 연결리스트, 힙으로 모두 구현할 수 있지만 보통 시간복잡도가 적은 힙을 사용한다.💡 우선순위큐
from queue import PriorityQueue
q = PriorityQueue()
# 삽입
q.put(3)
q.put(2)
q.put(1)
# 삽입시 우선순위 지정
q.put((5,"banana"))
q.put((1,"apple"))
q.put((3,"FINE"))
# 반환
print(q.get()) # 1
print(q.get()) # 2
print(q.get()) # 3
# 사이즈
print(q.qsize())
# 튜플 값만
print(q.get()[1]) # apple
🗒️ 힙(heap)
- heap은 쌓아 놓음, 쌓아 놓은 더미라는 뜻이다. 기본적인 정의는 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리이다. 반대로 '부모의 값이 자식의 값보다 항상 작다' 도 힙이 될 수 있다.
- 최솟값, 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리의 자료구조이다. 힙은 최대 힙과 ,최소 힙으로 나타 낼 수 있다.💡 힙 구현
import heapq
q = []
heapq.heappush(q,3)
heapq.headpush(q,2)
heapq.headpush(q,1)
heapq.headpop(q) # 1
heapq.headpop(q) # 2
heapq.headpop(q) # 3
루트를 삭제하고 힙을 재구성 하는 모습
가운데를 말해요
from sys import stdin as s
import heapq
leftHeap = []
rightHeap = []
s= open('input.txt','rt')
n = int(s.readline())
arr = list(map(int,s.readlines()))
for i in range(n):
if len(leftHeap) > len(rightHeap):
heapq.heappush(rightHeap,arr[i])
else :
heapq.heappush(leftHeap,-arr[i])
if len(leftHeap) != 0 and len(rightHeap) != 0 and -leftHeap[0] > rightHeap[0] :
left = -heapq.heappop(leftHeap)
right = heapq.heappop(rightHeap)
heapq.heappush(leftHeap,-right)
heapq.heappush(rightHeap,left)
print(-leftHeap[0])
사냥꾼
from sys import stdin as s
s = open('input.txt','rt')
M, N, L = list(map(int,s.readline().split()))
arr = list(map(int, s.readline().split()))
arr.sort()
count = 0
def bina(start,end,bf,af):
global count
if start > end:
return False
mid = (start+end)//2
if arr[mid] < bf:
return bina(mid+1,end,bf,af)
elif arr[mid] > af :
return bina(start,mid-1,bf,af)
else :
count+=1
return
for i in range(N):
x, y = list(map(int,s.readline().split()))
if y > L :
continue
else :
temp = L-y
bina(0,len(arr)-1,x-temp,x+temp)
print(count)처음에 for문으로 했는데 시간초과떠서 해당 범위를 넘겨서 해당 범위안에 속할 때만 카운트하고 범위 벗어나면 이분탐색으로 반복 수를 줄이니까 100점으로 통과했다.
💪"자, 다음"
❗️Tip
코딩테스트 문제를 풀 때 PriorityQueue를 쓰게 되면 PriorityQueue가 연산하는 속도 때문에 시간초과가 뜨기도 한다. 그래서 가급적 Heapq를 쓰자.
브루트 포스 문제 리스트
| NO | LV | 유형 | 제목 | 비고 |
|---|---|---|---|---|
| 1655 | G2 | 큐 | 가운데를 말해요 | mid를 따로 둔다 생각하고 계속 문제를 풀었는데 라인 수만 엄청 길어지고 답은 안나와서 결국 leftHeap의 루트를 mid로 생각하고 문제를 푸니까 바로 해결되었음 - 다시 풀어 보는게 좋을 듯 |
| 2110 | G4 | 이분탐색 | 공유기 설치 | 이분탐색으로 직접 공유기를 설치해가면서 찾아야 답이 나옴 |
| 2470 | G5 | 이분탐색 | 두 용액 | 이분 탐색으로 안 풀고 투 포인터로 품 |
| 8983 | G4 | 이분탐색 | 사냥꾼 | 처음에 for문으로 풀었다가 60점 받아서 중간 탐색 부분 다시 이분 탐색으로 해결함 |
불안은 어디에서 오는가
" 수심이 가득한 사람을 볼 때마다 나는 자신에게 묻는다네, 저들이 바라는 것은 무엇일까? 만약 저들이 능력밖에 있는 것을 원하지 않는다면, 저토록 걱정에 사로잡혀 고통 받을 필요가 있을까? "
- 에픽테토스, 대화록, 2.13.1
걱정의 대부분은 자신이 원하는 대로 통제할 수 없는 상황이 변하기를 바란다는 점이다. 통제 밖의 것을 바라지 말라. 걱정에 사로잡힐 때 스스로 질문을 던져라. 나의 불안은 통제할 수 있는 것인가? 그리고 이렇게 다시 물어라. 지금 이 불안이 나에게 조금이라도 도움이 되는가?
냉혹한 운명을 넘어서는 법
" 감정에 휩싸이지 말라. 모든 충동을 정의의 명령 앞에 굴복시켜라. 모든 현상에 맞서 당신의 신념을 보호하라. "
- 마르쿠스 아우렐리우스, 명상록, 4222
충동은 인간을 향해 밀려들어 온다. 우리의 임무는 이것들을 통제할 수 있느냐 없느냐 하는 것일 뿐이다.
행동하기 전에 생각해야 한다. 그리고 스스로 질문을 던져라. 누가 이것을 통제하고 있는가? 나를 안내할 원칙은 무엇인가?
절대 궁지에 몰리지 않는 법
" 그래서 누가 천하무적인가? 합리적인 선택 영역 밖에 있는 것들에 분노하지 않는 자가 천하무적이다 "
- 에픽테토스, 대화록, 1.18.21
고대 스토아 철학자들처럼 궁지에 몰렸을 때, 공격자들을 향해 이렇게 말할 수 있어야 한다. "자, 다음 분!"
지금까지 읽은 내용 중에서 오늘 내용들이 제일 와닿고 재밌는 것 같다.
- 통제할 수 없는 상황에 대해 걱정하지 말고 불안해 하지말자.!
- 공격적이고 자극적인 질문이 날아오더라도 움찔하지 않고, 과도한 반응도 자제한다.
- "자, 다음"
