패스트캠퍼스 챌린지 18일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 10일 오늘의 강의

 

신장트리

출처 : 잔재미 코딩

 

Spanning Tree라 불리우기도 한다. 원래의 그래프의 모든 노드가 연결되어 있으면서도 트리의 속성을 만족하는 그래프이다. 본래의 그래프의 모든 노드를 포함해야하며 모든 노드는 서로 연결되어 있다. 하지만 사이클이 존재하지 않아야 한다.

 

최소 신장 트리

출처 : 잔재미 코딩

 

Minimum Spanning Tree, MST라고 불리운다. 가능한 Spanning Tree 중, 간선의 가중치 합이 최소인 Spanning Tree를 의미한다.

 

최소 신장 트리 알고리즘

그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 

 

크루스칼 알고리즘

가중치 그래프에서 최소 가중치를 가진 최소 신장 트리를 찾는 알고리즘이다. 가장 적은 가중치부터 찾아가며 싸이클을 이루지 않게 가중치를 연결해나간다. 이때 모든 정점을 독립적인 집합으로 만들고, 모든 간선을 비용을 기준으로 정렬한다. 이는 탐욕 알고리즘을 기초로 하고 있다.

 

Union Find 알고리즘

Disjoint Set은 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 초기화와 두 개별 집합을 하나의 집합으로 합치는 Union, 여러 노드가 존재할 때 두 개의 노드를 선택해서 서로 같은 그래프에 속하는지 판별하기 위한 Find로 찾는다.

 

트리의 이슈로 링크드 리스트와 같은 형태가 될 경우, 계산량이 O(n)이 될 수 있으므로 서로 다른 트리는 union by rank 기법을 통해 각 노드들의 높이에 따라 트리를 연결해준다.

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.