[python] 코테 유형별 템플릿 모음

#stack

st = [] # 과거값 참조

for item in items:
	if st[-1] vs item:
    	st.pop()
    else:
    	st.append(item)

 

 

#priority-queue

import heapq

arr = []
# Q = heapq.heapify(arr)

for item in items:
	heapq.heappush(arr, item) # min-heap
	# heapq.heappush(arr, -item) # max-heap; 꺼낼 때 유의

while Q:
	poped = heapq.heappop(arr)
	# action

 

 

#graph #위상정렬

# n = vertex 개수
# edges: List[Tuple[int, int]]

from collections import defaultdict, deque

graph = defaultdict(list)
incoming = [0]*n

for s, e in edges:
	graph[s].append(e)
    incoming[e] += 1
    
Q = deque()
for i, cnt in enumerate(incoming):
	if cnt == 0:
    	Q.append(i)
 
while Q:
	poped = Q.pop()
	# action
    
    for near in graph[poped]:
        incoming[near] -= 1
        if incomint[near] == 0:
            Q.append(near)

 

 

# graph # dfs

def dfs(graph, start, visited = set()):
	visited.add(start)
  	# action
    
    for near in graph[start]:
    	if near not in visited:
        	dfs(graph, near, visited)

 

 

# graph # bfs

def bfs(graph, start):
	visited = set()
    Q = collections.deque([start])
    
    while Q:
    	poped = Q.popleft()
        visited.add(poped)
        
        for near in graph[poped]:
        	if near not in visited:
            	Q.append(near)

 

# binary search

"""
binary search
- target: 
- condition: 
- training: l->[something]<-r
"""

left, right # 범위 설정 중요
best_target # 정답

while l <= r:
	mid = (l+r)//2
    
    // simulation
    // training or check target 달성 및 update best_target
    
    
return best_target