그래프 썸네일형 리스트형 플로이드-와샬 알고리즘 플로이드-와샬 알고리즘은 그래프에서 최단거리를 구하는 알고리즘 중 하나입니다. 플로이드 알고리즘, 플로이드-워셜 알고리즘 등으로 불리기도 합니다. 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다른 최단거리 알고리즘과 다르게 모든 정점들 사이의 최단거리를 구할 수 있습니다. 정점의 수를 $V$라고 할 때 시간복잡도는 $O(V^3)$으로 꽤 높지만, 상수가 매우 작아 시간복잡도에 비해 빠르며 코드가 간단하다는 장점이 있어 모든 쌍 사이의 최단거리를 구하는 매우 효율적인 알고리즘입니다. 조금 응용하면 최단경로(최단거리인 경로에 속한 정점들) 또한 구할 수 있습니다. 편의를 위해 그래프의 정점의 개수를 $V$라고 부르겠습니다. 또한 이 글을 쉽게 읽으려면 그래프의 정점, 최단거리, 표현 방식 등 기.. 더보기 그래프 기초(의미, 분류, 구현 방법) 기초소개 그래프는 자료구조의 일종으로, 배열과 달리 데이터간의 관계를 나타낼 수 있는 자료구조입니다. 형태에 따라 각기 다른 특성을 가지고 있기 때문에 여러 세부 분류로 나뉘기도 합니다. 그래프란? 데이터에 해당하는 정점과 정점을 이으며 정점끼리의 관계를 나타내는 간선으로 이루어진 자료구조입니다. 위 그림처럼 생긴 자료구조입니다. 이 그래프는 무엇을 나타내는 그래프일까요? 정점을 사람, 간선을 친구 관계로 표현한다면 집단에서 친구인 사람들을 표현하는 그래프가 됩니다. 정점을 도시, 간선을 길으로 생각한다면 지도처럼 도시 사이를 이동하는 경로를 표시하는 그래프가 됩니다. 이처럼 정점과 간선을 적절히 설정한다면 그래프가 많은 것들을 나타내도록 할 수 있습니다. 간선의 방향 방향은 일방 통행 도로처럼 간선에서.. 더보기 백준 13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 풀이 마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다. 쿼리 1 : 0 b 원래 명령과 반대.. 더보기 이전 1 다음
