영최의 개발켈로그

✅ 위상정렬 기본 문제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:..

✅ 이문제 처음 접근할 때 친구-친구(2점) -> G[a][b]==G[b][c] ; O(n^3)...친구-친구-친구-친구-친구-친구(5점) -> G[a][b]==G[b][c]==G[c][d]==G[d][e]==G[e][f] ; O(n^6)이렇게 생각해서 뭐야 플로이드워셜로 풀면 시간 오류 뜨겠는데 생각해서 1) 다익스트라를 N번 돌려서 풀었는데 ,2) 플로이드워셜을 DP랑 같이 사용해서 풀 수도 있는 문제였다. ✅ 처음 다익스트라로 풀때 실수했던 부분:처음 시작점을 지나고 나서 distance[start][nv] = nddistance[nv][start] = nd -> 이부분까지 갱신을 해줬는데 그러면 안된다.왜냐면 Dijkstra의 알고리즘에서 거리는 특정 시작 노드에서 다른 노드까지 한 방향으로만 계..

✅ 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. => 바로 플로이드 워셜 점화식 떠올림✅ 플로이드 워셜에서 주의할 점 a!=b여야함 명심 N = int(input())G = [list(input()) for _ in range(N)]V = [[0]*N for _ in range(N)]for k in range(N): for a in range(N): for b in range(N): if a == b: continue if G[a][b]=="Y" or (G[a][k]=="Y" and G[k][b]=="Y"): V[a][b]=1answer = 0for row in V:..

✅ 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..