깊은 밤을 날아서

입출력 시간복잡도 줄이기 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, 다른 칸은 무한으로 초기화 최단 ..

1. 벨만-포드 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘. 다익스트라 알고리즘과 달리 에지의 가중치가 음수여도 사용할 수 있으며, 이로 인해 음수 사이클 존재 여부 확인 문제에서 많이 사용 다익스트라 알고리즘의 시간복잡도(O(ElogV))에 비해 표에 보이는 것과 같이 노드가 그대로 곱해지므로 음수 가중치 에지가 있거나 음수 사이클의 존재 여부를 판단할 때 사용하는 것이 좋음. 구현 방법 특징: 그래프를 에지 번호에 따라 출발 노드, 종료 노드, 가중치로 이루어진 에지 리스트로 구현함. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 최단 경로 리스트의 경우 출발 노드를 0, 나머지 노드를 무한대로 초기화 정답 리스트 업데이트하기 모든 에지를 확인해 sp[src_node]가 무한이 ..

K번째 최단 거리 찾기 개요 다익스트라 알고리즘을 이용하여 K번째 최단 거리를 구합니다. 구현 방법 최단 경로 리스트를 2차원 리스트로 설정하여 내부를 K개의 최단 경로로 채웁니다. K번째 경로를 찾기 위해서 여러 번 노드가 쓰일 수도 있으므로 방문 리스트는 따로 적용하지 않습니다. 위의 내용을 기억하며 아래의 최단 거리 리스트 채우기 규칙을 따릅니다. 최단 경로 리스트 및 그래프 인접 리스트를 초기화합니다. 우선 순위 큐에서 연결된 노드와 가중치 데이터를 가져옵니다. 연결 노드의 K번째(마지막) 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 K번째 경로에 값을 업데이트합니다. 이때 경로가 업데이트되는 경우 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가합니다. 큐가 비워질때까지 ..

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

1. 유니온 파인드 개요 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘 union, find 연산을 완벽히 이해하는 것이 핵심 union 연산: 각 노드가 속한 집합을 1개로 합치는 연산. 노드 a, b가 a { A, b { B일 때 union(a,b)는 A U B를 말함. find 연산: 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산. 노드 a가 a { A 일때 find(a)는 집합의 대표 노드를 반환 구현 방법 1차원 리스트 이용 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨. 1차원 리스트를 자신의 인덱스값으로 초기화. union 연산 각..

우선순위 큐 개요 우선순위를 가지는 queue. 정해진 우선순위가 높은 개체가 먼저 Get. 위 그림은 이해를 돕기위한 그림. 구현 방법 1. 일반적인 pq사용 from queue import PriorityQueue # 생성 방법 myque = PriorityQueue() # myqueue를 우선순위 큐로 생성 # 기본 함수 put(data) # 원소 추가 get() # 큐에서 데이터 꺼내기 qsize() # 큐 사이즈 가져오기 empty() # 큐가 비어 있는지 확인 put 연산의 경우 내부에 들어가는 튜플이나 리스트의 원소의 차례대로 우선순위를 가짐. 맨 앞에 있는 것으로 정렬 후 두번째 요소로 정렬 가능. EX) pq.put([2, 3]) pq. put([2, 1]) pq. get() -> [2,..

1. 큐(queue) 개요 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조 파이썬 구현 방법 collections에 deque 사용하여 간단하게 구현 가능 from collections import deque q = deque() 연산(이름이 q일 때) q.append(data): rear 부분에 새로운 데이터를 삽입하는 연산 q.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산 s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산 2. 너비 우선 탐색(BFS, breadth-first search) 개요 그래프 완전 탐색 방법 중 하나. 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘. 시간 복잡도(노드 수: V..