최단 거리 알고리즘 - 다익스트라 다익스트라 알고리즘은 흔히 알고있듯, 최단 거리를 구하는 데 초점이 맞춰진 알고리즘이다.우리가 아는 유명한 최단 거리 알고리즘이 무엇이 있을까? 아마 BFS가 떠오를 것인데, BFS와의 차이점은 거리(가중치)가 1이 아니라는 점이다.즉, BFS는 현재 칸에서 다음 칸으로 이동하면 거리(가중치)가 1이 증가하는데 반해 다익스트라는 임의의 가중치가 존재한다. 학문적으로는 가중치가 있는 그래프에서 하나의 시작 정점으로부터 모든 정점들까지의 최단 거리를 구하는 알고리즘이라고 설명할 수 있겠다. 또 다른 이야기를 해보자면, 이전에 업로드했었던 Prim 알고리즘과도 다소 유사한 모습을 보인다.프림 알고리즘와 다익스트라 알고리즘 모두 PriorityQueue를 사용하고 다소 그리디하..

최소 신장 트리 - MST(Minimum Spanning Tree) 최소 신장 트리의 개념은 아래 글의 초입에 서술되어 있다.2025.09.11 - [Algorithm] - [JAVA] 최소 신장 트리 - Kruskal 알고리즘 " data-og-description="최소 신장 트리 - MST(Minimum Spanning Tree)최소 신장 트리란, 여러 스패닝 트리 중 간선들의 가중치의 총합이 가장 작은 트리를 이야기한다. 그렇다면 최소 신장 트리를 알려면 신장 트리(Spanning Tree)" data-og-host="bitbard-dongni.tistory.com" data-og-source-url="https://bitbard-dongni.tistory.com/47" data-og-url="h..

최소 신장 트리 - MST(Minimum Spanning Tree)최소 신장 트리란, 여러 스패닝 트리 중 간선들의 가중치의 총합이 가장 작은 트리를 이야기한다. 그렇다면 최소 신장 트리를 알려면 신장 트리(Spanning Tree)를 알아야 하는데, 스패닝 트리(신장 트리)란 모든 정점을 연결했을 때 간선의 수가 V - 1개이고 사이클이 존재 하지 않는 무방향 그래프를 의미한다. 모든 정점이 연결되었고, 5개의 정점에 대해서 4개의 간선만을 가지고 있으며, 사이클이 존재하지 않는 무방향 그래프임을 볼 수 있다.간선에 적혀있는 숫자들은 간선의 가중치를 의미한다. 위 그림의 경우, 기존에 1번 정점과 3번 정점을 연결하는 가중치 3의 간선대신 2번 정점과 3번 정점을 연결하는 가중치 2의 간선을 선택해서 ..

유니온 파인드 알고리즘유니온 파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set Union, DSU) 자료구조를 이용해 원소들이 같은 집합에 속하는지 판별하거나, 두 집합을 하나로 합치는 연산을 효율적으로 처리하는 알고리즘이다.서로소 집합여러 개의 집합이 있을 때, 어떤 두 집합도 공통 원소를 갖지 않는 경우를 말함.즉, 집합끼리 겹치는 부분이 전혀 없는 상태{1, 2}, {3, 4}, {5, 6} 유니온 파인드 알고리즘 적용 예시그래프 이론 관련최소 신장 트리 (MST) - 크루스칼 알고리즘사이클 판별간선을 하나씩 추가하면서 두 정점이 이미 같은 집합인지 확인(Union) -> 같은 집합이면 사이클 존재연결 요소 찾기그래프에서 분리된 그룹 개수 세기이렇게 말해도 사실상 와닿지 않..

위상 정렬 알고리즘 위상 정렬(Topological Sort)은 방향을 가진 그래프에서 간선으로 주어진 정점간의 선후 관계를 위배하지 않도록 나열하는 정렬 방법이다. 정점간의 선후 관계를 알기 위해서는 그래프의 개념 중 진입 차수(Indegree)와 진출 차수(OutDegree)를 잘 알고있어야 하는데, 간단하게 설명해보자면 우선 그래프에는 차수라는 개념이 있다. 차수란, 그래프 상에 존재하는 정점과 그들 사이의 간선이 있을 때, 특정 정점에 연결된 간선의 개수를 의미한다.따라서 차수는 다음 2가지로 나눌 수 있다.진입 차수: 해당 정점으로 들어오는 간선의 개수진출 차수: 해당 정점에서 다른 정점으로 뻗어나가는 간선의 개수 자, 이제 차수에 대해서 간단하게 알아보았으니, 이 차수로 정점간의 선후 관계를..

BFS 알고리즘 BFS는 Breadth-First Search의 약어로 그래프나 트리와 같은 자료 구조에서 노드들을 탐색하는 알고리즘 중 하나입니다. 주로 두 노드 사이의 최단 경로를 찾거나, 그래프 내의 모든 노드를 방문할 때 사용되는 알고리즘입니다. BFS 동작 원리 BFS 알고리즘의 동작 원리는 총 4단계로 구성되어 있습니다. 시작 노드를 큐(Queue)에 추가하고 방문 표시를 합니다. 큐에서 노드를 하나 꺼내서 그 노드와 인접해 있고 방문하지 않았던 모든 노드들을 큐에 추가합니다. 노드에서 꺼낸 하나의 해당 칸을 보았을 때, 이전에 방문했다면 다음 칸을 탐색하고 해당 칸을 이전에 방문하지 않았다면 방문 표시를 합니다. 큐가 빌 때까지 2~3 과정을 반복합니다. 코드 전문 #include using..