hyunkookim 님의 블로그

142. Linked List Cycle II 이 문제는 Linked List Cycle Detection 문제 중 하나로,**Floyd's Cycle Detection Algorithm (Tortoise and Hare)**를 활용하여 해결할 수 있습니다.아래는 단계별 풀이 방법입니다.1. Floyd’s Cycle Detection Algorithm두 포인터(Tortoise와 Hare)를 사용하여 Linked List를 순회합니다.속도 차이를 이용해 두 포인터가 같은 노드에 도달하면 사이클이 있음을 확인할 수 있습니다.사이클이 발견되면, 사이클의 시작 노드를 찾는 추가 작업을 수행합니다.2. 단계별 풀이1단계: 사이클 존재 여부 확인slow 포인터는 한 번에 한 노드씩 이동합니다.fast 포인터는 한 ..

997. Find the Town Judge class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: # 1. 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(1, n + 1)} # 신뢰 관계 for a, b in trust: adj[a].append(b) # a가 b를 신뢰 # 2. 판사 후보 선정 # 판사는 누구도 신뢰하지 않아야 하므로, 신뢰 관계가 없는 노드를 후보로 선정 candidates = [i for i in range(1, n + 1) if not adj[i]] if..

1971. Find if Path Exists in Graph class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: # 양방향 그래프를 인접 리스트로 생성 adj = {i: [] for i in range(n)} for n1, n2 in edges: adj[n1].append(n2) adj[n2].append(n1) # 방문한 노드를 추적하기 위한 집합 visit = set() # DFS 함수 정의 def dfs(i): ..

261. Graph Valid Tree https://youtu.be/bXsUuownnoQ?si=hDkFB87rMA-fL6M4 class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: # 만약 노드의 개수가 0이라면, 빈 트리로 간주되므로 True 반환 # If there are no nodes (n == 0), it's considered a valid empty tree. if not n: return True """ 유효한 트리가 되기 위한 조건 (Valid Tree Conditions): 1. 노드 개수 - 1 == 간..

위상 정렬(Topological Sort)란?위상 정렬은**유향 비순환 그래프(DAG, Directed Acyclic Graph)**에서 노드들을 선행 관계에 따라 순서대로 정렬하는 알고리즘입니다.특징선행 관계를 보장:노드 A에서 B로 가는 간선이 있다면, 정렬 결과에서 A는 항상 B보다 먼저 나옵니다.**DAG(Directed Acyclic Graph)**에서만 수행 가능:싸이클이 있는 그래프에서는 위상 정렬이 불가능합니다.예제입력 그래프:간선: [[1, 0], [2, 0], [3, 1], [3, 2]]설명: 0은 1과 2의 선행 조건이고, 1과 2는 3의 선행 조건입니다.위상 정렬 결과:가능한 정렬: [0, 1, 2, 3] 또는 [0, 2, 1, 3]위상 정렬 알고리즘Kahn's Algorithm:진..