영최의 개발켈로그

1️⃣  위상정렬✅ 언제 사용? 유향 그래프의 모든 그래프를 방향성을 지키면서 순서대로 나열할때✅ 시간복잡도:  O(V+E) 노드와 간선을 모드 확인✅ 원리 : 1) 진입차수가 0인 노드를 큐에 넣는다.2) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거3) 새롭게 진입차수가 0이 된 노드를 큐에 넣음큐가 빌때까지 2)-3)반복(진입차수란? 특정한 노드로 들어오는 간선의 개수)✅ 주의: 1) 큐에 들어가는 원소가 2개 이상이면 정답이 여러개 존재함2) 모든 원소를 방문하기 전에 큐가 비면 사이클이 존재함✅ 기본 코드:from collections import deque# 노드의 개수와 간선의 개수를 입력 받기v, e = map(int, input().split())# 모든 노드에 대한 ..

0️⃣  MST( 최소신장트리, Minimum Spanning Tree)✅ 정의: 무방향 그래프에서 최소의 비용으로 모든 노드를 연결하면서 사이클이 발생하지 않는 트리✅ 사용되는 알고리즘: 크루스칼, 프림 ✅ 간적쿠간만프: 간선 적으면 크루스칼 간선이 많으면 프림 사용1️⃣  크루스칼✅ 언제 사용? 간선이 적을때✅ 시간복잡도(개선된) :  O(ElogE) (100만 정도) - 간선 정렬✅ 원리 :1) 간선 데이터를 비용에 따라 오름차순으로 정렬 2) 사이클이 발생하지 않는 경우 최소신장 트리에 포함시킴 (반복)✅ 서로소 집합 부모 찾기 최적화:parent[x] = find_parent(parent, parent[x]): 처음에는 parent[x] != x에서 parent[x] == x 까지 재귀를 돌면서..

1️⃣ 다익스트라✅ 언제 사용? 음의간선 없을때 한지점에서 특정지점까지 최단거리 구할 때 사용✅ 시간복잡도(개선된) :  O(elogv) (100만 정도) (경우에 따라 BFS로도 풀 수 있음; 인접리스트: O(e+v),인접행렬  O(v^2))✅ 원리 :1) 출발노드 선정 -> 2) 최단거리 테이블 ∞로 초기화 (출발노드는 0으로) -> 3) 방문하지 않은 노드 중 최단 거리가 짧은 노드 선택 (처음엔 출발노드, 최단 거리가 0이니까)-> 4) 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 갱신-> 3),4) 반복✅ 최적화: 힙 사용(거리 가장 짧은 노드), 방문처리 대신 테이블에 기록된 거리와 비교하여 큰 경우 PASS✅ 기본 코드:import heapq# sys.stdin.rea..