Data Structure : 최소비용신장트리 - Sollin's Algorithm (Boruvka's Algorithm)
Data Structure : 최소비용신장트리 - Sollin's Algorithm ( Boruvka's Algorithm ) Sollin의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 시작하면서 모든 정점을 Tree로 정의한다. ( Forest 상태 ) 하나의 Tree에 대해 외부의 Vertex와 연결 가능한 가장 비용이 작은 edge를 선택해 추가한다. edge가 중복되는 경우에는 하나만 추가한다. Tree가 하나로 이어질 때 까지 2를 반복한다. ( Forest 상태 X ) Sollin 알고리즘 모든 Vertex를 one-vertex Tree로 정의 while(tree가 하나가 아니면) { 모든 tree에 대해서 각각 T..
Data Structure : 최소비용신장트리 - Prim's Algorithm
Data Structure : 최소비용신장트리 - Prim's Algorithm Prim의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. 규칙 하나의 정점에서 시작함. 한번에 하나씩 Tree에 간선을 추가하고, 추가한 결과는 Tree를 이루어야 한다. Tree가 여러 개이면 Forest Tree에 추가한 간선이 Cycle을 구성하지 않도록, 간선을 고를 때 Tree에 속해있는 Vertex 하나와 속하지 않은 Vertex 하나가 만드는 간선을 골라야 한다. Tree에 속한 edge의 개수가 vertex 개수 - 1인 경우 ( Spanning Tree 조건을 만족 ) 또는 추가할 edge가 없는 경우 ( Spanning Tree X ) ..
Data Structure : 최소비용신장트리 - Kruskal's Algorithm
Data Structure : 최소비용신장트리 - Kruskal's Algorithm Kruskal의 알고리즘은 Greedy Strategy로, 각 스텝마다 가능한 최선의 선택지를 고르는 것을 반복하여 결과를 얻어낸다. Kruskal 알고리즘은 주어진 가중치 그래프에서 최소비용인 신장트리를 뽑아내는 것을 목표로 한다. ( 신장트리 : vertex를 모두 연결하면서 edge의 개수가 n-1개인 트리 ) 규칙 한 번에 하나씩 간선을 추가한다. 추가되는 간선의 순서는 비용의 크기를 기준으로 선택한다. 간선을 추가했을때 사이클이 형성되지 않는 간선만 추가 가능하다. 사이클이 형성되는가? 에 대해서는 'Union-Find'를 이용한다. 간선의 개수가 n-1인 경우 ( Spanning Tree 만족 ) 또는 남은 ..
희소행렬을 표현할 때 Structure를 이용해 현재 행렬에 들어있는 값들만을 row, column 순으로 오름차순으로 정렬해 Array로 표현하는 방법이 있다. 이렇게 나타낸 행렬을 덧셈 곱셈등의 연산에도 활용할 수 있는데, 전치행렬을 구하는 연산도 적용할 수 있다. 다양한 전치행렬을 만드는 알고리즘 중, Fast Transpose가 단번에 잘 이해가 되지 않아서 정리해보았다. ( matrix array는 (row, column ,value) structure를 순서대로 담아놓은 Array임 ) 이해가 잘 안된 부분은 StartingPosition이였다. 한 번 이해하고 나니 크게 어렵지 않게 코드를 작성할 수 있었다. 다른 (느린) 전치과정과 달리 Fast Transpose는 옮겨담는 matrix a..
