🏫학부 공부/알고리즘4 [알고리즘] 최소신장트리 (작성중) # 가중 그래프 : 간선에 가중치 (weight)를 가지는 그래프 예) 거리, 비용, 시간 # 최소신장트리 - 신장 부그래프 : 그래프의 모든 정점들을 포함하는 부그래프 - 신장트리 : 트리인 신장 부그래프 - 최소신장트리(Minumum Spanning Tree, MST) : 간선 무게가 최소인 신장트리 # 최소신장트리의 속성 ## 1. 사이클 속성 T: 가중그래프 G의 최소신장트리 e: 최소신장트리 T에 존재하지 않는 G의 간선 C: e를 T에 추가하여 형성된 사이클 => C의 모든 간선 f에 대해, weight(f) e를 포함하는 최소신장트리가 반드시 존재 # 탐욕법 (그리디) ### [ 요소 ] 1. 구성: 다양한 선택, 모음, 찾아야할 값들 2. 목표: 구성에 할당된 점수를 최대화, 최소화하는 것.. 2023. 11. 23. [알고리즘] 방향그래프 방향그래프 - 모든 간선이 방향간선 방향그래프의 속성 - 모든 간선은 한 방향으로만 - G가 단순(간선이 많지 않음) : M v인 방향경로가 존재하면, "u는v에 도달한다" , "v는 u로부터 도달 가능하다" 강연결성 어느 두 정점 u, v 간에 u에서 v 도달가능 이고 v에서u 로 도달가능이면 강연결 강연결 검사 알고리즘 1. 임의 정점 v 선택 2. v에서 DFS 실행 3. 간선들 방향을 역행시킨 그래프 G'을 얻음 4. G'에서 v에서부터 DFS 수행 -> O(n+m) 강연결 요소 - 최대한 모든 정점을 도달할 수 있는 부그래프 a->f로 간다고 하면, a로 다시 올 수 없음. 이행적폐쇄 다음 성질을 만족. 1. G'은 G와 동일한 정점들로 구성 2. G의 u에서 v(v!=u)로의 경로가 존재하면 .. 2023. 11. 21. 이진탐색트리 - 내부 노드에 (key, value)로 저장하는 이진트리로 다음 성질을 만족함. p, l(p의 왼쪽), r(p의 오른쪽) 일 때, l.key n->key) return treeSearch(n->l,target); else return treeSearch(n->r, targt); } // 탐색 결과 void findElement(Tree* t, int target) { Node* res = treeSearch(t->root, target); if (isExternal(res)) printf("No such key\n"); else printf("target: %d\n", res->key); } 삽입 - treeSearch()를 통해.. 2023. 10. 8. 합병 정렬과 퀵정렬 모두 Divide and Conquer로 구현 가능하다. Recursion을 이용해서 구현해보자. 합병 정렬 기본 개념 1. 하나의 리스트를 두 개의 리스트로 분할 (리스트 사이즈가 2일 때까지) 2. 분할된 리스트를 각각 순회하면서 작은 순서대로 새로운 리스트에 추가 3. Recursion을 빠져나오면서 정렬된 리스트들끼리 계속 2번 진행 4. 최종적으로 정렬된 리스트를 반환 의사코드 Alg mergeSort(list L) if(L.size > 1) // divide L1, L2 = partition(L) // recursion L1 = mergeSort(L1) L2 = mergeSort(L2) // Conquer L = merge(L1, L2) return L merge Alg merge(L1, L2.. 2023. 10. 4. 이전 1 다음
