그래프2

• 

  최소 신장 트리(MST) : 크루스칼(Kruskal) & 프림(Prim) 최소 신장 트리최소 신장 트리를 구하라라는 문장을 코딩테스트를 하면 많이 볼 수 있다.이 문장의 뜻은 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점을 연결하였을 때, 비용의 합이 최소가 되도록 함을 의미한다.- 각 시점에서 최선의 선택을 하는 알고리즘인 그리디(Greedy) 알고리즘 부류입니다. 신장트리- 모든 정점을 연결하는 간선의 집합. 크루스칼(Kruskal) 알고리즘- 크루스칼을 이용하여 최소 신장 트리를 구하는 방법은 다음과 같습니다. 1) 간선을 오름차순으로 정렬한 다음2) 간선 하나씩 선택하며 폐로(사이클)이 생기는지 확인한 뒤,3) 생기지 않으면 간선 리스트에 추가를, 생기면 간선 리스트에 접근 금지를 한다.반복하다보면 모든 정점이 연결될 것입니다. ex) 최소 신장 트리를 만들.. CS 지식/자료구조_알고리즘 2025. 1. 15.

• 

  그래프(Graph) : 너비우선탐색(BFS) & 깊이우선탐색(DFS) 그래프- 그래프란 노드(Node)와 간선(Edge)로 이루어진 연결 구조입니다.- 노드는 점을 의미하고, 간선은 노드간 연결되어 있는 선을 의미합니다.  가중 그래프- 가중 그래프는 간선에 숫자를 부여해서 무게나 비용을 의미하게 만든 그래프입니다. 방향 그래프- 방향 그래프는 간선에 방향을 부여해서 특정 방향으로만 이동할 수 있는 그래프입니다.- 방향 그래프가 아닌 그래프는 양방향그래프라고 생각하면 됩니다.- 가중 그래프처럼 비용, 무게를 부여할 수 있습니다.  너비 우선 탐색 (Breadth First Search)- 시작점에서부터 목표점까지 갈 수 있는지 탐색하는 알고리즘입니다.- 시작점에서 가까운 곳 부터 방문하는 알고리즘입니다.- 선입선출 구조로 Queue(큐)를 주로 이용합니다. ex) A에서 .. CS 지식/자료구조_알고리즘 2025. 1. 13.