안녕

앞서 보았듯이 시간 복잡도는 다음과 같습니다. Prim's Algorithm : \(T(n)\,\epsilon\,\theta(n^2)\) Kruskal's Algorithm : \(W(m, n)\,\epsilon\,\theta(mlgm) \, or \, \theta(n^2lgn)\) 또한 \(n-1 \leq m \leq \frac{n(n-1)}{2}\)이 성립합니다. 따라서 프림 알고리즘과 크루스칼의 알고리즘은 다음과 같은 상황에서 비교할 수 있습니다. For a Sparse Graph edge의 개수인 m이 n-1과 가까운 희소 행렬의 경우에는 Kruskal's Algorithm is \(\theta(nlgn)\)이므로, Prim's Algorithm 보다 빠릅니다. For a Dense Graph e..

문제)

최소 비용 신장 트리를 풀기 위한 또 다른 알고리즘은 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 각 vertex마다 본인만 포함하는 서로소 집합 (disjoint set)을 만드는 것부터 시작합니다. 이후, 가중치가 작은 것부터 차례대로 edge를 검사합니다. 만약 edge가 서로소 부분 집합들에 있는 두 개의 vertex를 연결한다면 edge를 추가하고, 두 개의 부분 집합을 하나의 집합으로 합칩니다. 이 반복은 모든 disjoint set이 하나의 set이 될 때까지 반복합니다. 슈도 코드로 작성하면 다음과 같습니다. F = 0 create disjoint set of V sort the edges in E in nondecreasing order while the instance is not so..

문제)

Prin's Algorithm은 Minimum Spanning Tree를 찾는 가장 기초적인 알고리즘입니다. 1. Minimum Spanning Tree란? 우선, Minimum Spanning Tree를 알아보겠습니다. G(graph)에 대한 Spanning Tree는 G의 모든 vertex를 포함하고, 트리인 connected 된 그래프입니다. 만약 G = (V, E)로 이루어져 있다면, Spanning Tree인 T = (V, F)가 되어야 합니다. 이때 F는 V-1과 같습니다. 만약 F가 V-1보다 크다면 cycle이 생겨서 Tree가 되지 않습니다. 아무튼 우리가 찾아야 하는 (V, F)는 Edge의 weight의 합이 최소가 되는 집합을 찾아야 합니다. edge의 weight가 최소가 되는 S..

1. 탐욕 알고리즘이란? 탐욕 알고리즘이란 각 순환마다 '가장 좋은' 선택을 합니다. 탐욕 알고리즘은 DP와 마찬가지로 최적화 문제를 푸는데 주로 사용됩니다. 또한 상대적으로 DP보다 알고리즘을 설계하기 더 쉽습니다. DP는 재귀 관계식을 세워서 큰 instance를 작은 instance로 분할해서 문제를 풉니다. 하지만 탐욕법은 instance를 분할하지 않습니다. 단지 순서대로 가장 좋아 보이는 답을 선택해서 모읍니다. 즉, 어떤 선택이든지 선택할 당시에는 최적입니다. (locally optimal) 하지만 이게 곧 전체에서 최적인 해 (globally optimal)를 구한다는 보장은 없습니다. 따라서 탐욕법은 해당 알고리즘이 최적의 해답을 얻는지 확인하는 절차를 반드시 거쳐야 합니다. DP는 최적..

문제)

1. BST (Binary Search Tree)란? 아마 자료구조 시간에 다 배웠으실 텐데요. BST는 ordered set (순서 가능한 집합)에 속한 원소(key)로 이루어진 이진 트리이고, 다음의 조건을 만족합니다. 각각의 노드는 하나의 unique한 key를 갖고 있다. node의 left subtree는 node의 key보다 작거나 같다. node의 right subtree는 node의 key보다 크거나 같다. 생각보다 간단하죠? 우리의 목적은 BST에서 검색하는 key와 같은 원소를 찾는 average time을 최소화하는 데 있습니다. 만약에 각 원소가 검색될 확률이 모두 동일하다면, 트리의 높이는 낮을 수록, 그리고 좌우의 높이 차가 덜 클수록 효율적입니다. 하지만 만약에 각 원소가 검색..

문제)

우선 2x3 행렬과 3x4 행렬을 곱해봅시다. 결과물은 2x4 행렬이 나오겠죠? 또한 곱셈의 횟수는 2 x 3 x 4 = 24입니다. 즉 i x j 행렬과 j x k행렬의 곱의 횟수는 i x j x k가 됩니다. 또 다른 예시를 들어봅시다. A X B X C X D이고, A = 20 x 2, B = 2 x 30, C = 30 x 12, D = 12 x 8입니다. 행렬 곱셈은 결합 법칙이 성립하므로, 곱셈의 순서는 결과에 영향을 미치지 않습니다. 즉, (AB)(CD) = (A(B(CD))와 같습니다. 이때 4개의 행렬은 총 5개의 다른 순서로 곱할 수 있습니다. A(B(CD)) : 3680 A((BC)D) : 1232 (AB)(CD) : 8880 ((AB)C)D : 10320 (A(BC))D : 3120 ..