최소 스패닝 트리최소 스패닝 트리(MST) ?최소 스패닝 트리는(MST)는 가중치 그래프에서 모든 정점들을 연결하는 최소 비용의 연결 부분 그래프이다.MST 조건모든 정점이 연결되어 있어야 한다 !사이클이 없어야 한다 !가중치의 합이 최소여야 한다 !💡 핵심 개념 - 스패닝 트리스패닝 트리는 주어진 그래프의 모든 정점을 포함하는 연결 그래프이며, 간선의 수는 V(정점의 수)-1이다. → 여러 스패닝 트리 중 가중치의 합이 최소인 트리가 MST이다.💡 핵심 개념 - MST를 구하기 위한 알고리즘크루스칼 알고리즘: 간선을 정렬한 뒤, 최소 가중치 간선을 하나씩 선택하면서 사이클이 생기지 않도록 트리를 구성한다.프림(Prim) 알고리즘: 하나의 정점에서 시작하여 인접한 간선 중 최소 가중치를 선택하며 트리..
위상정렬 알고리즘위상정렬(Topology Sort) ?위상정렬 알고리즘은 사이클이 없는 그래프에서 노드의 순서를 찾는 정렬 알고리즘이다.그래프 내의 노드들 간의 선후 관계를 결정하여, 어떤 작업들이 먼저 수행되어야 하는지 순서를 정하는 것이 목표이다. → 작업의 선후 관계를 결정해야 하거나 특정 순서로 작업을 처리해야 하는 문제에서 사용된다 !💡 위상정렬 핵심 개념 - 유향 비순환 그래프(DAG)위상정렬은 반드시 사이클이 없는 유향 그래프에서만 적용 가능하다 ! → 그 이유는 당연하게도 사이클이 있다면, 노드 간의 선행 관계를 정의할 수 없기 떄문에 ! 💡선행 관계 ?간선(u → v)이 있을 때, u는 항상 v보다 앞에 와야 한다는 의미이다. 💡 위상정렬 핵심 개념 - 진입 차수(In-degree)..
유니온 파인드 알고리즘유니온 파인드 (Union-Find) ?유니온 파인드(Union-Find)는 그래프의 연결성을 판별하기 위한 효율적인 자료구조이다. → 이를 통해 서로소 집합(Disjoint Set)을 관리하며, 다음과 같은 두 가지 주요 연산을 제공한다.Union: 두 집합을 합친다.Find: 특정 원소가 속한 집합(대표 원소)을 찾는다.여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 사용한다.💡 유니온 파인드 핵심 개념 - 루트(대표원소)각 집합은 고유한 루트 노드를 갖고 있으며, 모든 원소는 해당 루트를 참조한다.두 원소가 같은 집합에 속하는지는 Find 연산으로 확인한다.💡 유니온 파인드 - 구현초기화 : 유니온 파인드 자료구조를 위한 새로운 집합을 ..
다익스트라 알고리즘다익스트라(Dijkstra) ?다익스트라 알고리즘은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다.해당 노드까지의 최단 경로를 찾는 과정에서 다른 모든 정점까지의 경로값도 계산해주면서 각 정점까지의 최단 경로도 모두 찾게 된다 !가중치가 양수일 때만 사용 가능하다 !💡 다익스트라 핵심 개념 - Greedy다익스트라는 그리디(Greedy) 알고리즘의 일종으로, 매 단계마다 **가장 최적의 선택(현재 최단 거리를 가진 정점)**을 한다. → 즉, 아직 방문하지 않은 정점 중에서 최단 거리의 정점을 선택해 탐색한다. 💡방문 여부도 체크해야 하나 ?따로 체크할 필요가 없다 ! → 노드는 한 번 방문했을 때 최단 거리값으로 갱신되기 때문에, 아래처럼 거리를 ..
DFSDFS ?그래프 완전 탐색이 필요할 때, 즉 모든 노드를 방문해야 할 때 DFS를 주로 사용한다.말 그대로 그래프의 시작 노드에서 탐색할 분기를 하나 정하게 되면 그 분기의 최대 깊이까지 탐색을 마친 후 다른 분기로 이동하여 다시 최대 깊이까지 탐색을 수행하는 알고리즘이다.Stack과 재귀함수를 이용하여 구현한다.💡 DFS 핵심 개념 - 방문 여부 체크DFS는 한 번 방문한 노드를 재방문하면 안되기 때문에, 각각의 노드에 대한 방문 여부를 체크할 수 있는 배열이 필요하다 !💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도노드의 수 = V, 간선의 수 = E인접 리스트를 이용한 방법 - O(V + E)모든 노드 방문 - O(V) → DFS는 모든 노드를 한 번씩 방문하기 때문..
BFSBFS ?루트 노드(혹은 다른 임의의 노드)에서 시작해서 시작 노드로부터 가까운 노드들부터 먼저 탐색하는 알고리즘이다.무방향 그래프나 가중치가 동일한 그래프에서 최단 경로를 보장하지 때문에, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.그래프나 트리의 모든 정점을 특정 레벨 순서로 탐색할 때 적합하다 !💡 BFS 핵심 개념 - 방문 여부 체크DFS와 동일하게 방문 여부를 체크해야 한다.💡 DFS 핵심 개념 - 그래프 구현 방법에 따라 달라지는 시간 복잡도노드의 수 = V, 간선의 수 = E인접 리스트를 이용한 방법 - O(V + E)모든 노드 방문 - O(V) → BFS는 모든 노드를 한 번씩 방문하기 때문에 O(V) 시간 복잡도가 요구된다.간선 탐색 - O(..