깊은 밤을 날아서

입출력 시간복잡도 줄이기 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 ..

개요 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다. 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행합니다. 특징은 아래와 같습니다. N진 트리: 문자 종류의 개수에 따라 N이 결정됩니다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성됩니다. 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지합니다. 구현 방법 루트 노드는 공백을 유지한 채 첫 단어에 해당하는 노드를 생성합니다. 아래 과정을 각 단어에 대해 반복하여 단어들을 모두 트리에 입력합니다. 현재 위치한 글자에 대해 루트 자식노드 중 해당 글자가 공백 상태가 아니면 해당 글자로 이동합니다. 공백 상태라면 글자를 추가하고 그곳으로 이동합니다. 백준..

파이썬 코딩테스트 정복기 3탄입니다. 파이썬 코딩에 대해 기본적인 지식이 필요합니다. 각 단원마다 개념을 모두 포함하는 예제 한 문제만 풀이할 예정이니 참고해주세요. 1. 스택 + DFS + 이분 그래프 2. 큐 + BFS + 트리의 지름 3. 우선순위 큐와 그리디 4. 유니온 파인드 + 최소 신장 트리 5-1. 최단 거리 찾기[1] - 다익스트라 알고리즘 5-2. 최단 거리 찾기[2] - K번째 최단 거리 5-3. 최단 거리 찾기[3] - 벨만 포드 5-4. 최단 거리 찾기[4] - 플로이드 워 셜 6. 이진 탐색 + 트라이 7. 투포인터 + 슬라이딩 윈도우 8. 구간 합 + 세그먼트 트리 9. 에라토스 테네스의 체 + 오일러 피 함수 10. 유클리드 호제법 + 확장 유클리드 호제법 11. 조합 + 다..

개요 그래프에서 최단거리를 구하는 알고리즘입니다. 특징은 아래와 같습니다. 모든 노드 간의 최단 거리 구하기 가능 음수 가중치 에지가 있어도 수행 가능 동적 계획법의 원리를 이용해 알고리즘을 구성 시간복잡도는 O(V^3) 구현 방법 시작 노드에서 도착 노드까지의 최단 경로를 구할 때 그 중간에 있는 노드 K가 존재한다면 시작 노드→K, K → 도착노드와 같은 부분 경로도 최단 경로라는 원리입니다. sp_list[S][E] = min(sp_list[S][E], sp_list[S][K] + sp_list[K][E]) 인접 행렬로 구현하는 방법입니다. 리스트 선언 및 초기화 sp_list[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 리스트 S와 E가 같은 칸은 0, 다른 칸은 무한으로 초기화 최단 ..