희노애락앤롤

프림 알고리즘의 최적 여부 검증 Optimality Proof 프림 알고리즘은 매 결정을 할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 그리디 알고리즘에 기반한다. 그 순간의 선택은 그 당시에는 최적일 수도 있지만 순간순간 최적이라고 생각했던 해답을 모아서 최종적인 해답을 만들었을 때, 그 해답이 궁금적으로 최적이라는 보장이 없다. 따라서 그리디 알고리즘은 항상 최적의 해답인지 검증할 필요가 있다. 프림 알고리즘이 찾아낸 신장트리가 최소비용인지 검증해야 한다. 다시 말해서, 프림 알고리즘이 최적인지를 보여야 한다. 비방향성 그래프인 G = (V, E)가 주어진다. G는 가중치가 있는 그래프이고, 이것은 전체 정점의 집합V와 전체 간선의 집합E로 이루어져 있다. F는 방문한 간선이고 E..

프림 알고리즘 Prim's Algorithm이란? 최소 비용 신장 트리를 구현하는 알고리즘으로, 시작 정점에서부터 가중치의 합이 최소가 되도록 신장 트리를 확장해나가는 알고리즘이다. 프림 알고리즘의 동작 프림 알고리즘은 매번 최적의 선택을 하는 그리디 알고리즘에 기반하여 동작한다. 따라서 노드를 이동하는 순간순간마다 비용이 최소인 간선과 연결된 노드를 신장 트리 집합에 추가한다. 정점의 집합 = V 신장 트리(MST)에 추가되는 정점의 집합 = Y MST에 추가되는 간선의 집합 = F 1. 맨 처음에는 시작 정점만이 Y에 추가된다. 2. Y와 인접한 노드 중 가장 낮은 비용인 간선과 연결된 노드를 Y에 추가하고 해당 간선도 F에 추가한다. 이 때 사이클이 발생해서는 안 된다. 3. Y=V가 될 때까지 2..

연쇄적으로 행렬을 곱할 때, 어떤 행렬 곱셈을 먼저 수행하느냐에 따라서 다음 예시와 같이 필요한 기본적인 곱셈의 횟수가 달라진다.Minimum Multiplication 알고리즘은 곱셈 횟수의 최소치를 결정하고 그 최소치를 구하는 순서를 결정하는 알고리즘이다.1. Brute force로 풀어보기먼저 가능한 모든 순서를 모두 고려해보고 그 가운데에서 가장 최소인 경우를 선택하는 brute force로 문제를 풀어본다. n개의 행렬(A1, A2, ..., An)을 곱할 수 있는 모든 순서의 가짓 수를 $t_{n}$이라고 한다.만약 A1이 마지막으로 곱하는 행렬이라면 (ex. A1(A2A3))  행렬 A2부터 An을 곱하는 가짓수는 $t_{n-1}$일 것이다.만약 An이 마지막으로 곱하는 행렬이라면 (ex. ..