위상정렬 알고리즘위상정렬(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(..
그래프와 구현 방법그래프 ?아래와 같은 자료구조를 그래프라고 한다. 대표적인 구현 방식으로 3가지가 있다.엣지 리스트인접 행렬인접 리스트엣지 리스트이름에서 알 수 있듯이 엣지(Edge; 간선)를 중심으로 그래프를 표현한다. → 즉 그래프의 모든 간선을 리스트 형태로 저장한다 !가중치 X → 두 정점(출발지, 도착지)가중치 O → 두 정점(출발지, 도착지), 가중치List edgeList = new ArrayList();edgeList.add(new Edge(1, 2, 5)); // 간선 (1 -> 2), 가중치 5edgeList.add(new Edge(2, 3, 3)); // 간선 (2 -> 3), 가중치 3장점간선의 개수가 적을 때 메모리를 절약할 수 있다 !구현이 간단하고, 특정 알고리즘(ex: 크루..
