깊은 밤을 날아서

입출력 시간복잡도 줄이기 import sys # 입력값이 많을 경우 입력시간 줄이기 input = sys.stdin.readline # 출력값이 많을 경우 출력시간 줄이기, 단 아래 사용 시 개행 문자 사용하여 직접 컨트롤 해야 함. print = sys.stdout.write 재귀함수 호출 시 깊이 제한 늘리기 import sys sys.setrecursionlimit(10**6) 주요 라이브러리 중요도순으로 정리하였습니다. # deque from collections import deque dq = deque()# 선언하기 dq.append()# 오른쪽에 넣기 dq.popleft()# 왼쪽에서 꺼내기 dq# 비어있는지 확인하기 # 우선순위 큐 from queue import PriorityQueue ..

1. 다익스트라 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘 입니다. 특정 출발 노드에서 다른 노드로 가는 최단 거리를 모두 구하기 때문에 출발 노드가 고정되어 있을 때 사용 가능합니다. 추가적으로 에지들의 가중치 또한 항상 양수여야 합니다. 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수 O(ElogV) 구현 방법 간단하게 말하자면 BFS로 탐색을 진행하되, 다음 탐색 지점을 방문하지 않은 노드 들 중 가장 가까운 곳부터 선택하도록 하는 방법입니다. 위와 같이 항상 갈 수 있는 가장 최솟값인 경로만 택함으로써 결과적으로 각 노드는 출발 노드로부터 최단 경로만에 도달하게 됩니다.(간선의 가중치가 모두 양수가 아니라면 돌아올수록..