1. 문제 E - Modulo MST (atcoder.jp) E - Modulo MST AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다 다행히 정점 N
1. 문제 1647번: 도시 분할 계획 (acmicpc.net) 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 풀이 입력 자체가 "임의의 두 집 사이에 경로가 항상 존재하는 입력이 주어진다"라고 되어있는데 맨 처음에는 모든 정점에 대하여 서로 연결된 하나의 그래프 집합이 주어지는데.. 여기서 몇개의 간선을 선택해서 두 집합으로 분리하라는 문제 이 때 선택된 간선의 가중치 합이 최소가 되도록 만들어야한다 최소 스패닝 트리 이전에 그냥 진짜 단순하게 생각해보면, 초기에..
1. 개요 가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘이 간선들을 선택해가면서 최소 신장 트리를 구성하는 반면에 프림 알고리즘은 정점을 선택하고, 인접한 정점 중에서 최소 비용을 가지는 간선을 하나씩 선택해가면서 최소 신장 트리를 구성하는 일종의 그리디 알고리즘이다. 다익스트라 알고리즘과 사실상 동일한 알고리즘이다. 참고로 다익스트라 알고리즘은 음수 가중치에서는 동작하지 않지만, 프림 알고리즘은 음수 가중치에서도 동작한다고 한다 2. 알고리즘 2-1) 임의의 정점을 하나 선택해서 최초의 트리를 구성 2-2) 선택한 정점과 트리에 포함된 정점들과 인접한 정점중 최소 비용의 간선이 존재하는 정점을 선택한다 2-3) 모든 정점이 선택될 때까지 위 과..
1. 신장트리(spanning tree) n개의 정점으로 이루어진 "무방향 그래프"에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이다. 그래서 이러한 그래프를 신장 트리라고 부른다. 위와 같은 그래프에서 신장 트리는 여러개 찾을 수 있다. 예를 들어 아래와 같은 그래프는 하나의 신장 트리이다. 하지만 다음 그림과 같은 그래프들은 신장 트리가 아니다. 구체적으로 다음은 노드 1을 포함하고 있지 않다 다음은 노드 4-6-7에서 사이클이 발생하므로 신장트리가 아니다. 2. 최소 신장 트리(Minimum spanning tree)..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
