영최의 개발켈로그

✅ 위상정렬 기본 문제from collections import dequeN,M = map(int,input().split())G = [[] for _ in range(N+1)]indegree = [0]*(N+1)for _ in range(M): a,b = map(int,input().split()) G[a].append(b) indegree[b]+=1q = deque()for i in range(1,N+1): if indegree[i]==0: q.append(i)while q: v = q.popleft() print(v, end=" ") for nv in G[v]: indegree[nv]-=1 if indegree[nv]==0:..

✅ X,Y,Z마다 정렬하는게(3번) 힙을 각각 X,Y,Z마다 만들고 빼는것보다 빠름 정렬 사용) 총 시간 복잡도: O(N) + O(N log N) + O(N) = O(N log N)힙 사용) 총 시간 복잡도: O(N log N) + O(N log N) + O(N) = O(N log N)아무래도 힙을 넣는데서 더 오래걸리는 것 같음  ✅ 통과 코드 (정렬 사용)from heapq import heappop,heappushN = int(input())hangsungs = [list(map(int,input().split()))+[i] for i in range(N)]q = []visited = [0]*(N)G = [[] for _ in range(N)]for i in range(3): hangsungs..

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 까지 재귀를 돌면서..