시작하며

시험 기간과 이것저것.. 집중하지 못했슨..
다시 시작해보겠슨

deque (collections.deque)

# 양쪽에서 O(1)로 삽입/삭제 가능 — 스택, 큐 모두 구현 가능
from collections import deque

dq = deque([1, 2, 3])
dq.append(4)        # 오른쪽 추가 → [1, 2, 3, 4]
dq.appendleft(0)    # 왼쪽 추가 → [0, 1, 2, 3, 4]
dq.pop()            # 오른쪽 제거 (4 반환)
dq.popleft()        # 왼쪽 제거 (0 반환)
dq[0]               # 맨 앞 요소 접근
dq[-1]              # 맨 뒤 요소 접근

heapq: 자동 정렬된 우선순위 큐 — O(logN) 삽입/삭제

import heapq

hq = []
heapq.heappush(hq, 3)
heapq.heappush(hq, 1)
heapq.heappush(hq, 2)
heapq.heappop(hq)   # 1 반환 (가장 작은 값)
min_val = hq[0]     # 최소값 확인만 하기 (제거 X)

# 최대 힙처럼 쓰려면 음수로 저장
heapq.heappush(hq, -x)  # push
x = -heapq.heappop(hq)  # pop

우선순위 큐 + DP 문제 풀기

우선순위 큐

import heapq

pq = []  # 우선순위 큐(최소 힙) 초기화

# 리스트 형태의 요소들을 하나씩 넣기
heapq.heappush(pq, [3, 'C'])
heapq.heappush(pq, [1, 'A'])
heapq.heappush(pq, [2, 'B'])

print(pq)
# 내부 구조 예: [[1, 'A'], [3, 'C'], [2, 'B']]  (힙 구조)

# heappop()을 하면 첫 번째 원소(0번째 인덱스 기준)가 작은 리스트가 나옴
print(heapq.heappop(pq))  # [1, 'A']
print(heapq.heappop(pq))  # [2, 'B']
print(heapq.heappop(pq))  # [3, 'C']

직접 문제 풀어보기

1781 컵라면

• 풀이 링크 : 🔗 개인 노션 링크
• 한줄 정리 : 범위에 따른 DP를 할때는 이전 조건이 이후 조건의 넓은 범위를 유지하도록 해, 우선순위 큐 내부의 적합성을 유지하자
  

1202 보석 도둑

• 풀이 링크 : 🔗 개인 노션 링크

• 한줄 정리 : 어떤 구조일때 이전 조건이 이후 조건에도 만족할 수 있는지를 따져보자

  	보석 무게 ≤ 1 을 만족할 수 있는건 이후 보석무게 ≤2를 만족한다. ✅