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

---

Part 2. 알고리즘 이론

Ch 20. 그래프 고급 탐색 알고리즘

04. 최소 신장 트리의 이해와 크루스칼 알고리즘 (1)

05. 최소 신장 트리의 이해와 크루스칼 알고리즘 (2)

---

• 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리
• 최소 신장 트리 : 그래프의 한 종류로, 전체 노드/정점을 간선으로 연결하되 사이클이 형성되지 않은 트리 + 간선의 가중치 합이 최소인 트리
• 크루스칼 알고리즘 : 대표적인 최소 신장 트리 알고리즘의 한 종류. 당장 최소 비용을 선택하여 결과적으로 최적의 해를 찾는 탐욕 알고리즘을 바탕으로 함
• Union-Find 알고리즘: Disjoint Set(서로소 집합 자료구조)를 표현할 때 사용하는 알고리즘으로 트리구조를 활용하는 알고리즘. 노드 중 연결된 노드를 찾거나 노드들을 연결할 때 사용
• 크루스칼 알고리즘 구조 : 전체 노드/정점을 모두 잇는다. - 가중치가 낮은 간선부터 연결한다. - 가중치가 낮은 간선부터 높은 간선까지 순서대로 연결하되 사이클이 생기면 연결한 노드를 지운다.

오늘은 최소 신장 트리와 그 대표적인 예시인 크루스 칼 알고리즘에 대해 공부했다. 글 쓰는 스타일을 좀 바꿔보기로 했다. 내가 궁극적으로 챌린지에 참가하는 이유는 앞으로 개발자로서 공부하는 습관을 기르고 내가 공부한 걸 흔적으로 위해서다. 하지만 독후감과 비슷한 느낌을 가장한 후기일 뿐 정보가 없다는 생각이 들었다. 아무래도 하루에 학습하는 내용이 강의 두 편, 많으면 서 너편정도인데 그걸 공백을 제외하고 500자로 채우기 어렵다. 이 모든 부족한 점을 보완하기 위해 이렇게 저렇게 보완하다 보니 오늘의 형태를 갖추게 되었다. 오늘 첫 출근 후 챌린지를 진행하기 위해 강의를 듣고, 후기까지 쓰려니 시간이 촉박했다. 게다가 Union-Find 알고리즘은 이해가 되지 않자 앞으로 미션에 성공할 수 있을까 걱정이 된다. 하지만 아직 일어나지 않은 일에 걱정하지 말고 일단 열심히 해보자고 생각했다.

 

 

 

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

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