λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

μ•Œκ³ λ¦¬μ¦˜14

15-1κ°•. μ΅œμ†ŒλΉ„μš©μ‹ μž₯트리(Minimum spanning tree) μ΅œμ†ŒλΉ„μš©μ‹ μž₯트리 (Minimum Spanning Tree) - μž…λ ₯ : n 개의 λ„μ‹œ, λ„μ‹œμ™€ λ„μ‹œλ₯Ό μ—°κ²°ν•˜λŠ” λ„λ‘œ λΉ„μš© - 문제 : μ΅œμ†Œμ˜ λΉ„μš©μœΌλ‘œ λͺ¨λ“  λ„μ‹œλ“€μ΄ μ„œλ‘œ μ—°κ²°λ˜κ²Œ ν•œλ‹€. ν•΄κ°€ μœ μΌν•˜μ§€λŠ” μ•Šλ‹€.. 예) (b, c) λŒ€μ‹ μ— (a, h)κ°€ λ˜μ–΄λ„ λœλ‹€. -> λΉ„μš©μ΄ κ°™κ³ , λ‹€ μ—°κ²°λ˜κΈ° λ•Œλ¬Έμ΄λ‹€. * μ΅œμ†ŒλΉ„μš©μ‹ μž₯트리의 닡은 항상 νŠΈλ¦¬κ°€ λœλ‹€. μ™œ? (트리 : 싸이클이 μ—†λŠ” μ—°κ²°λœ(connected) 무방ν–₯ κ·Έλž˜ν”„) : cycle이 μžˆλ‹€λŠ” 말은 이μͺ½ λ°©ν–₯으둜 가도 μ €μͺ½ λ°©ν–₯으둜 가도 λ˜λŠ”λ°, 이 경우 ν•œ μͺ½μ˜ 길이 λŠμ–΄μ Έλ„ λ°˜λŒ€ λ°©ν–₯으둜 갈 수 있게 λœλ‹€. λ”°λΌμ„œ μš°λ¦¬λŠ” μ΅œμ†ŒλΉ„μš©μ„ μ›ν•˜λ―€λ‘œ cycle이 μžˆλŠ” κ·Έλž˜ν”„λŠ” 이 κ²½μš°μ—μ„œ μ œμ™Έν•œλ‹€. - μ–΄λ–€ MST(Minimun Spanning Tree)의.. 2020. 12. 11.
14-4κ°•. DAG와 μœ„μƒμˆœμ„œ DAG (Directed Acyclic Graph) : λ°©ν–₯ 사이클(directed cycle)이 μ—†λŠ” λ°©ν–₯ κ·Έλž˜ν”„. (자기 μžμ‹ μœΌλ‘œ λŒμ•„μ˜€μ§€ μ•ŠλŠ” λ°©ν–₯κ·Έλž˜ν”„..) 예) μž‘μ—…λ“€μ˜ μš°μ„ μˆœμœ„ μœ„μ˜ κ·Έλž˜ν”„μ—μ„œ bκ°€ 되기 μœ„ν•΄μ„œλŠ” aκ°€ λ°˜λ“œμ‹œ μ„ ν–‰λ˜μ–΄μ•Ό ν•œλ‹€! μœ„μƒμ •λ ¬ (topological ordering) - DAGμ—μ„œ λ…Έλ“œλ“€μ˜ μˆœμ„œν™”(sorting) .. v1, v2, ..., vn. 단 λͺ¨λ“  에지(vi, vj)에 λŒ€ν•΄μ„œ i < jκ°€ λ˜λ„λ‘! μœ„μ˜ κ·Έλž˜ν”„μ—μ„œ μœ„μƒμ •λ ¬μ„ ν–ˆμ„ λ•Œ, μ™Όμͺ½μ—μ„œ 였λ₯Έμͺ½ λ°©ν–₯으둜 μ •λ ¬ν–ˆμ„ λ•Œ, a-g-... λ˜λŠ” a-b-... 인데, μ—­λ°©ν–₯으둜 κ°€λ©΄ μ•ˆ λœλ‹€. (였λ₯Έμͺ½μ—μ„œ μ™Όμͺ½μœΌλ‘œ κ°€λ©΄ μ ˆλŒ€ μ•ˆ λœλ‹€.) μ–΄λ–€ λ…Έλ“œμ— λŒ€ν•΄μ„œ λ“€μ–΄μ˜€λŠ” λ…Έλ“œμ˜ 갯수λ₯Ό in-degree, λ‚˜κ°€λŠ” λ…Έλ“œμ˜ .. 2020. 12. 8.
14-3κ°•. κ·Έλž˜ν”„μ—μ„œμ˜ DFS DFS(Depth-First Search) 깊이 μš°μ„  탐색 level order traversal (BFS) inorder traversal (DFS) pre-order traversal (DFS) post-order traversal (DFS) 1. 좜발점 sμ—μ„œ μ‹œμž‘ν•œλ‹€. 2. ν˜„μž¬ λ…Έλ“œλ₯Ό visited둜 markν•˜κ³ , μΈμ ‘ν•œ λ…Έλ“œλ“€ 쀑 unvisited λ…Έλ“œκ°€ μ‘΄μž¬ν•˜λ©΄ κ·Έ λ…Έλ“œλ‘œ κ°„λ‹€. 3. 2λ²ˆμ„ 계속 λ°˜λ³΅ν•œλ‹€. 4. λ§Œμ•½ unvisited인 μ΄μ›ƒλ…Έλ“œκ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ” λ™μ•ˆ κ³„μ†ν•΄μ„œ 직전 λ…Έλ“œλ‘œ λ˜λŒμ•„ κ°„λ‹€. 5. λ‹€μ‹œ 2λ²ˆμ„ λ°˜λ³΅ν•œλ‹€. 6. μ‹œμž‘λ…Έλ“œ s둜 λŒμ•„μ˜€κ³ , 더이상 갈 곳이 μ—†μœΌλ©΄ μ’…λ£Œν•œλ‹€. 이 κ·Έλž˜ν”„μ—μ„œλŠ” 1-3-7-8-7-3-5-2-4-2-5-6 μˆœμ„œλ‘œ κ°„λ‹€.. (ν•˜μ§€λ§Œ μˆœμ„œλŠ” λ°”λ€” 수.. 2020. 12. 6.
14-1κ°•. κ·Έλž˜ν”„(Graph) κ°œλ…κ³Ό ν‘œν˜„ (무방ν–₯) κ·Έλž˜ν”„. G = (V, E) - V : λ…Έλ“œ(node) ν˜Ήμ€ 정점(vertex) - E : λ…Έλ“œ μŒμ„ μ—°κ²°ν•˜λŠ” 에지(edge) ν˜Ήμ€ 링크(link) - 개체(object)λ“€ κ°„μ˜ 이진관계λ₯Ό ν‘œν˜„ - n = |V|, m = |E| λ°©ν–₯κ·Έλž˜ν”„(Directetd Graph). G=(V, E) - 에지(u, v)λŠ” uλ‘œλΆ€ν„° v둜의 λ°©ν–₯을 가짐 κ°€μ€‘μΉ˜ (weighted) κ·Έλž˜ν”„ - μ—μ§€λ§ˆλ‹€ κ°€μ€‘μΉ˜(weight)κ°€ 지정 κ·Έλž˜ν”„μ˜ ν‘œν˜„ - 인접행렬 (adjacency matrix) - μΈμ ‘λ¦¬μŠ€νŠΈ (adjacency list) μœ„μ˜ κ·Έλ¦Όμ—μ„œ m은 μ—£μ§€μ˜ 갯수λ₯Ό λ‚˜νƒ€λ‚Έλ‹€.. n(:λ…Έλ“œμ˜ 갯수) + 2m(:λ…Έλ“œ 갯수) μ΄μ–΄μ„œ μ €μž₯곡간은 O(n+m)이닀. λ°©ν–₯κ·Έλž˜ν”„λ₯Ό ν‘œν˜„ν•˜λŠ” 방법 κ°€μ€‘μΉ˜ κ·Έλž˜ν”„μ˜ 인접행렬 ν‘œν˜„ .. 2020. 12. 1.

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”