Algorithm3 유니온 파인드 Union Find 그래프 알고리즘으로,특정 원소가 속한 집합의 루트(대표자)를 찾고, 두 개의 집합을 합치는 기능을 한다.이를 통해 두 노드가 같은 그래프에 속하는지 판단할 수 있다. 크게 다음의 3가지 과정을 거치게 된다.1. Initialization 초기화각 노드가 각각의 집합에 포함되도록 초기화하는 과정이다. 2. Find 찾기특정 노드의 부모를 찾는다.즉, 해당 노드가 속한 집합의 루트를 반환한다. 3. Union 합치기두 노드 A와 B를 한쪽으로 합칠 때,2번 과정을 통해 찾은 B의 루트 트리를 A의 루트 트리에 연결함으로써 합칠 수 있다. 1. Initialization 각 노드가 자기 자신만을 자신의 집합에 속하도록 배열을 만든다. 2. Find이 배열에 저장된 값들은 각각 자신의 부모 노드를 가르키고 .. 2025. 2. 28. 그리디 greedy 보호되어 있는 글 입니다. 2024. 1. 16. Graph / DFS / BFS Graph그래프는 여러 노드들이 개수 제한 없이 서로 연결된 상태를 말하며,각 노드들은 계층구조를 갖지 않는다트리는 그래프의 한 모델이지만 다음과 같은 차이를 보인다. GraphTree비순환 or 순환 방식directed or undirected네트워크 모델비순환 방식항상 directed계층 모델 그래프는 다음과 같이 크게 세 종류로 나뉜다.방향 그래프 (Directed graph)무방향 그래프 (Undirected graph)가중 그래프 (Weighted graph) - 이 경우 ( _ , 가중치) 형태로 행렬 or 리스트에 저장한다. Graph representation그래프를 구현하는 방법에는 두 가지가 있다. 인접 행렬 (Adjacency Matrix) 두 vertex의 연결 여부, 즉 edge.. 2024. 1. 14. 이전 1 다음
