학부 수업 정리 (43) 썸네일형 리스트형 [알고리즘] 3. MST - Kruskal 알고리즘 1. Kruskal 알고리즘의 Idea 모든 Edge들을 weight가 작은 순서부터 대입하기 (No Cycle) Spanning Tree가 될때까지 이 과정을 반복 (최종적으로 node $n$개 - edge $n-1$개가 되어야 함) 2. Kruskal 알고리즘의 정당성 증명 - 입력 그래프: $G = (V, E)$ - Edge Set인 $T_{mst}$ 는 정답 중 하나라고 가정 - 알고리즘이 끝난 후 Prim 알고리즘이 가지고 있는 edge set $T$는 $T_{mst}$가 될 것이다. ※ 주의사항: $T_{mst}$는 증명 중간에 바뀔 수 있기 때문에 미리 잡고 시작할 수 없다. 하지만 정답이라는 사실은 항상 유지된다! $\exists\ T_{mst} \rightarrow T \subseteq .. [알고리즘] 2. MST - Prim 알고리즘 1. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프를 의미한다. (단, 사이클을 생성하지 않아야 한다.) 2. Prim 알고리즘의 Idea 아무 노드 중 하나의 노드를 가진 트리에서 시작 트리에 인접한 edge들 중에서 가장 작은 weight를 가진 edge를 추가 (단, 사이클을 만들지 않아야 함) Spanning Tree가 될때까지 이 과정을 반복 (최종적으로 node $n$개 - edge $n-1$개가 되어야 함 3. Prim 알고리즘의 정당성 증명 - 입력 그래프: $G = (V, E)$ - Edge Set인 $T_{.. [알고리즘] 1. 수학적 귀납법과 재귀 1. 수학적 귀납법 $P(1)$ 이 참이고, $P(n-1) \xrightarrow{} P(n)$ 이 참이면 $P(n)$ 은 모든 자연수 $n$ 에 대해서 참이다. $P(n-1)$ 이 참이라고 가정하는 이유: $P(n-1)$ 이 거짓이면 $P(n-1) \xrightarrow{} P(n)$ 전체가 Vacuously True 이므로 할 말이 없다. 2. Recursive Sum Function int sum(int x) { if (x x) return search(a, m-1, x); else { int r = search(a+m+1, n-m-1, x); if (r == -1) return -1; else return r + m + 1; } } For some i, if $a[i] = x$, search() .. 이전 1 ··· 3 4 5 6 다음
