Table of Contents 개요프림 알고리즘O(V^2) 알고리즘O(V^2) 코드O(E log V) 알고리즘O(E log V) 코드문제프림 알고리즘의 정당성 1. 개요 프림 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘과 같은 용도이지만, 응용 상황에서 두 알고리즘의 효율성이 달라질 수 있기 때문에 둘 모두 알아두는 것이 좋습니다. 최소 스패닝 트리에 대한 개념을 모른다면 크루스칼 알고리즘을 먼저 보고 오시는 걸 추천합니다. 2. 프림 알고리즘 프림 알고리즘은 MST를 찾기 위한 그리디 패러다임의 알고리즘입니다. 이 알고리즘을 따라가면 최소 스패닝 트리를 구할 수 있습니다. step 0) 임의의 정점을 선택하여 비어있..
Table of Contents 개요방법 1 - 동적계획법방법 1 코드방법 2 - 탐욕법방법 2 코드방법 2 의 정당성방법 2 로 far 배열 찾기문제 1. 개요 트리의 지름이란, 트리 내에서 가장 먼 두 정점 사이의 거리를 뜻합니다. 이 글에서는 트리의 지름을 구하는 2가지 방법에 대해 소개합니다. 참고로 이 두 가지 방법은 모두 시간 복잡도를 늘리지 않는 선에서 'far [ v ] = 정점 v와 v에서 가장 먼 정점 사이의 거리'를 모든 정점에 대해 구할 수 있습니다. far 배열을 구하면 지름 = MAX(far [ v ])로 쉽게 구할 수 있으며, 지름만 구할 때 보다 더 다양한 상황에 쓸 수 있게 됩니다. 때문에 이 문서에서는 far [ v ] 을 구하는 방법까지 소개하도록 하겠습니다. 방법 1은..
Table of Contents 개요최소 스패닝 트리 ( minimum spanning tree )크루스칼 알고리즘 ( Kruskal's algorithm )크루스칼 알고리즘의 구현크루스칼 알고리즘 코드문제크루스칼 알고리즘의 정당성 1. 개요 크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, '최소 스패닝 트리' 라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 사용하므로, 해당 자료구조를 모른다면 유니온 파인드 설명을 보고 오시는 걸 추천합니다. 2. 최소 스패닝 트리 ( minimum spanning tree ) 스패닝 트리란, 해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜻합니다. 왼쪽의 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽의 ..
Table of Contents 개요초기화간단한 방법최적화 단계 1최적화 단계 2 - 유니온 파인드 트리유니온 파인드 트리 - 코드문제 1. 개요 유니온 파인드는 집합을 관리하는 자료구조로서, disjoint set 이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 사용할 수 있습니다. 연산 1) 요소 A와 요소 B가 같은 집합에 속하는 지 확인.연산 2) 요소 A가 속한 집합과 요소 B가 속한 집합을 병합. 유니온 파인드 연산의 이해를 위해 일단, 위와 같이 4개의 요소가 있다고 해보겠습니다. 초기 상태는 아직 병합을 한 번도 안 한 상태이기 때문에 각자 다른 집합에 속합니다. 이 상태에서 1번 연산, 예를 들어 요소 1과 요소 2가 같은 집합 인지에 대한 질의가 들어오면 이 자료..