📚전공/알고리즘 (19) 썸네일형 리스트형 [알고리즘] MCST - Kruskal's Algorithm (크루스칼 알고리즘) Spanning Tree (신장 트리) Graph의 모든 Vertex를 포함하는 Sub Graph이자 Tree 모든 정점들이 연결되어 있어야 한다. 사이클이 없어야 한다. (트리니까) Edge의 개수는 N-1개이다. (N: Node의 수) MCST (최소 비용 신장 트리) Minimun Cost Spanning Tree Graph의 신장 트리 중 Edge의 가중치 합이 최소인 신장 트리 MCST - Kruskal's Algorithm 1. Edge들을 가중치 기준으로 오름차순 정렬 (가중치 작은 거 -> 큰 거) 2. 가중치가 작은 Edge들부터 시작하여 다음을 반복 1) 선택된 Edge의 양 끝 Node들이 속한 집합을 확인한다. (Find) 2) 같은 집합에 속하지 않다면 : 두 Node가 속한 집합.. [알고리즘] Time Complexity & Space Complexity (시간 복잡도 & 공간 복잡도) 알고리즘의 성능을 분석하는 방법에는 시간 복잡도와 공간 복잡도가 있다. - 시간 복잡도 : 프로그램을 완료할 때까지 실행해야 하는 컴퓨터 시간 - 공간 복잡도 : 프로그램을 완료할 때까지 실행해야 하는 memory의 양 시간 복잡도 프로그램 P가 취하는 time T(P)는 compile time과 run time의 합이다. 시간 복잡도를 고려할 때는 프로그램의 tuntime만 생각한다. 프로그램이 수행하는 operations들의 수를 세면 된다. 프로그램 단계(step)는 실행 시간이 instance 특성과는 무관한 구문론적 또는 의미론적으로 의미 있는 프로그램 segment다. float temp_sum=0;은 temp_sum이라는 변수를 선언함과 동시에 temp_sum에 0을 대입했으므로 의미 있다... Permutation Algorithm (순열 알고리즘) 수업을 들을 때도 개념적으로는 이해가 쉽게 되었지만 코드로 구현하려니까 쉽지가 않았어서 정리하려고 한다. 순열은 재귀를 통해서 구현할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; /* 순열 알고리즘 */ void Perm(char *list, int Start, int End) { int j, temp; if (Start == End) { for (j=0; j 이전 1 2 3 다음
