๐ Algorithm (61) ์ธ๋ค์ผํ ๋ฆฌ์คํธํ ์๊ณ ๋ฆฌ์ฆ - Greedy (ํ์ ์๊ณ ๋ฆฌ์ฆ, ์์ฌ์์ด ์๊ณ ๋ฆฌ์ฆ), ์ต์ ํด ์ฐพ๊ธฐ Greedy Alogrithm Greedy๋ ์ฌ์ ์ ์ธ ์๋ฏธ๋ก 'ํ์์ค๋ฌ์ด', '์์ฌ๋ง์' ์ด๋ผ๋ ๋ป์ ๊ฐ์ง๊ณ ์๋ค. ํ์ ์๊ณ ๋ฆฌ์ฆ ๋๋ ์์ฌ์์ด ์๊ณ ๋ฆฌ์ฆ ๋ผ๊ณ ๋ ๋ถ๋ฆฐ๋ค. ๋ฏธ๋๋ฅผ ์๊ฐํ์ง ์๊ณ ์ ํ์ ์๊ฐ๋ง๋ค ๋น์ฅ ๋์์ ๋ณด์ด๋ ์ต์ ์ ์ ํ์ ํ๋ ๊ธฐ๋ฒ ๊ฐ ๋จ๊ณ์์ ์ต์ ์ ์ ํ์ ํ ๊ฒ์ด ์ ์ฒด์ ์ผ๋ก๋ ์ต์ ์ด๊ธธ ๋ฐ๋ผ๋ ์๊ณ ๋ฆฌ์ฆ ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ํด๊ฒฐ ๋ฐฉ๋ฒ ์ ํ : ํ์ฌ ์ํ์์ ์ต์ ์ ํด๋ต ์ ํ ์ ์ ์ฑ ๊ฒ์ฌ : ์ ํ๋ ๋ต์ด ๋ฌธ์ ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์ง ํ์ธ ํด๋ต ๊ฒ์ฌ : ์๋์ ๋ฌธ์ ๊ฐ ํด๊ฒฐ๋์๋์ง ๊ฒ์ฌํ๊ณ , ํด๊ฒฐ๋์ง ์์๋ค๋ฉด ์ ํ ์ ์ฐจ๋ก ๋์๊ฐ ์์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค. ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ ์กฐ๊ฑด ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฉํ๊ธฐ ์ํด์๋ 2๊ฐ์ง ์กฐ๊ฑด์ ์ฑ๋ฆฝํด์ผ ํ๋ค. 1. ํ์์ ์ ํ ์์ฑ (Greedy Choice Prop.. ์๊ณ ๋ฆฌ์ฆ - Sort ์ ๋ ฌ (Merge sort, Quick sort), Python ์ฝ๋ Merge Sort (๋ณํฉ์ ๋ ฌ) - ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํํ์ ๋ ์ด ์ ๋ ฌ์ ์์ ์ ๋ ฌ์ ์ํ๋ฉฐ, ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ ์ค์ ํ๋์ด๋ค. - ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ : ๋ฌธ์ ๋ฅผ ์์ 2๊ฐ์ ๋ฌธ์ ๋ก ๋ถ๋ฆฌํ๊ณ ๊ฐ๊ฐ์ ํด๊ฒฐํ ๋ค์, ๊ฒฐ๊ณผ๋ฅผ ๋ชจ์์ ์๋์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ์ ๋ต์ด๋ค. ๋๊ฐ ์ํํธ์ถ์ ์ด์ฉํ์ฌ ๊ตฌํํ๋ค. - ํ๋์ ๋ฆฌ์คํธ๋ฅผ ๋ ๊ฐ์ ๊ท ๋ฑํ ํฌ๊ธฐ๋ก ๋ถํ ํ๊ณ ๋ถํ ๋ ๋ถ๋ถ ๋ฆฌ์คํธ๋ฅผ ์ ๋ ฌํ ๋ค์, ๋ ๊ฐ์ ์ ๋ ฌ๋ ๋ถ๋ถ ๋ฆฌ์คํธ๋ฅผ ํฉํ์ฌ ์ ์ฒด๊ฐ ์ ๋ ฌ๋ ๋ฆฌ์คํธ๊ฐ ๋๊ฒ ํ๋ ๋ฐฉ๋ฒ์ด๋ค. - ๋ถํ (Divide): ์ ๋ ฅ ๋ฐฐ์ด์ ๊ฐ์ ํฌ๊ธฐ์ 2๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด๋ก ๋ถํ ํ๋ค. - ์ ๋ณต(Conquer): ๋ถ๋ถ ๋ฐฐ์ด์ ์ ๋ ฌํ๋ค. ๋ถ๋ถ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ์ถฉ๋ถํ ์์ง ์์ผ๋ฉด ์ํ ํธ์ถ ์ ์ด์ฉํ์ฌ ๋ค์ ๋ถํ ์ ๋ณต ๋ฐฉ๋ฒ์ ์ ์ฉํ๋ค. - ๊ฒฐํฉ(Com.. ์๊ณ ๋ฆฌ์ฆ - Sort ์ ๋ ฌ (Selection sort, Insertion sort, Bubble sort), Python ์ฝ๋ Sort (์ ๋ ฌ) n๊ฐ์ ์ซ์๊ฐ ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ก์ ๋, ์ด๋ฅผ ์ฌ์ฉ์๊ฐ ์ง์ ํ ๊ธฐ์ค์ ๋ง๊ฒ ์ ๋ ฌํ์ฌ ์ถ๋ ฅํ๋ ์๊ณ ๋ฆฌ์ฆ Sort ์๊ณ ๋ฆฌ์ฆ ์ข ๋ฅ Selection sort Insertion sort Bubble sort Merge sort Quick sort ๊ธฐ์ด์ ์ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ํ๊ท ์ ์ผ๋ก O(n^2)์ ์๊ฐ์ด ์์๋๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ - Selection sort (์ ํ์ ๋ ฌ) - Insertion sort (์ฝ์ ์ ๋ ฌ) - Bubble sort (๋ฒ๋ธ์ ๋ ฌ) ๊ณ ๊ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ํ๊ท ์ ์ผ๋ก O(nlogn)์ ์๊ฐ์ด ์์๋๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ - Merge sort (๋ณํฉ์ ๋ ฌ) - Quick sort (ํต์ ๋ ฌ) - Heap sort (ํ์ ๋ ฌ) Selection sort (์ ํ์ ๋ ฌ) - ์ ์๋ฆฌ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ - ํด๋น ์.. ์๊ณ ๋ฆฌ์ฆ - ์ต์ ์ ์ฅ ํธ๋ฆฌ(Minimum Spanning Tree), ํฌ๋ฃจ์ค์นผ(Kruskal), ํ๋ฆผ(Prim) Python ์ฝ๋ ์ต์ ์ ์ฅ ํธ๋ฆฌ (MST) MST : Minimum Spanning Tree ๊ฐ์ ์ ๊ฐ์ค์น๋ฅผ ๊ณ ๋ คํ์ฌ ์ต์ ๋น์ฉ์ Spanning Tree๋ฅผ ์ ํํ๋ ๊ฒ ์ ์ฅ ํธ๋ฆฌ (Spanning Tree) ๊ทธ๋ํ ๋ด์ ๋ชจ๋ ์ ์ ์ ํฌํจํ๋ ํธ๋ฆฌ ๊ทธ๋ํ์ ์ต์ ์ฐ๊ฒฐ ๋ถ๋ถ ๊ทธ๋ํ ์ด๋ค. ์ต์ ์ฐ๊ฒฐ์ด๋, ๊ฐ์ ์ ์๊ฐ ๊ฐ์ฅ ์ ์ ๊ฒ์ด๋ค. Spanning Tree์ ํน์ง - DFS, BFS์ ์ด์ฉํ์ฌ ๊ทธ๋ํ์์ ์ ์ฅ ํธ๋ฆฌ๋ฅผ ์ฐพ์ ์ ์๋ค - ํ๋์ ๊ทธ๋ํ์๋ ๋ง์ ์ ์ฅ ํธ๋ฆฌ๊ฐ ์กด์ฌํ ์ ์๋ค. - Spanning Tree๋ ํธ๋ฆฌ์ ํน์ํ ํํ์ด๋ฏ๋ก ๋ชจ๋ ์ ์ ๋ค์ด ์ฐ๊ฒฐ ๋์ด ์์ด์ผ ํ๊ณ ์ฌ์ดํด์ ํฌํจํด์๋ ์๋๋ค. MST (Minimum Spanning Tree) ๊ทธ๋ํ์์ ๋ชจ๋ ์ ์ ์ ์ฐ๊ฒฐํ๋, ์ฌ์ดํด์ด ์กด์ฌํ์ง ์๊ณ ๊ฐ์ ์.. ์๊ณ ๋ฆฌ์ฆ - DFS(๊น์ด ์ฐ์ ํ์) / BFS(๋๋น ์ฐ์ ํ์) Python ์ฝ๋ ๊ทธ๋ํ ํ์ ๊ธฐ๋ฒ ๊ทธ๋ํ : ์ ์ (node)์ ๊ทธ ์ ์ ์ ์ฐ๊ฒฐํ๋ ๊ฐ์ (edge)์ผ๋ก ์ด๋ฃจ์ด์ง ์๋ฃ๊ตฌ์กฐ์ด๊ณ , ๊ทธ๋ํ๋ฅผ ํ์ํ๋ ๊ฒ์ ํ๋์ ์ ์ ์ผ๋ก๋ถํฐ ์์ํ์ฌ ์ฐจ๋ก๋๋ก ๋ชจ๋ ์ ์ ๋ค์ ํ ๋ฒ์ฉ ๋ฐฉ๋ฌธํ๋ ๊ฒ์ ๋งํ๋ค. DFS(Depth First Search) : ๊น์ด ์ฐ์ ํ์ BFS(Breadth First Search) : ๋๋น ์ฐ์ ํ์ DFS(Depth First Search) ์ต๋ํ ๊น์ด ๋ด๋ ค๊ฐ ๋ค, ๋ ์ด์ ๊น์ด ๊ฐ ๊ณณ์ด ์์ ๊ฒฝ์ฐ ์์ผ๋ก ์ด๋ 1. ๋ชจ๋ ๋ ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ณ ์ ํ๋ ๊ฒฝ์ฐ์ ์ด ๋ฐฉ๋ฒ์ ์ ํํจ 2. ๊น์ด ์ฐ์ ํ์(DFS)์ด ๋๋น ์ฐ์ ํ์(BFS)๋ณด๋ค ์ข ๋ ๊ฐ๋จํจ 3. ๊ฒ์ ์๋ ์์ฒด๋ ๋๋น ์ฐ์ ํ์(BFS)์ ๋นํด์๋ ๋๋ฆผ ์ ์ฉ : ๋ฏธ๋ก, ๊ธธ ์ฐพ๊ธฐ, ๊ฒฝ๋ก์ ํน์ง์ ์ ์ฅํด์ผ ํ๋.. ์๊ณ ๋ฆฌ์ฆ - Binary Search Tree / Tree (์ด์ง ํ์ ํธ๋ฆฌ, ํธ๋ฆฌ, ์ด์ง ํธ๋ฆฌ, Python ์ฝ๋) ํธ๋ฆฌ (Tree) ํธ๋ฆฌ (Tree)๋ ๋ ธ๋๋ค์ด ๋๋ฌด ๊ฐ์ง์ฒ๋ผ ์ฐ๊ฒฐ๋ ๋น์ ํ ๊ณ์ธต์ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ํธ๋ฆฌ๋ ํธ๋ฆฌ ๋ด์ ๋ค๋ฅธ ํ์ ํธ๋ฆฌ๊ฐ ์๊ณ ๊ทธ ํ์ ํธ๋ฆฌ ์์๋ ๋ ๋ค๋ฅธ ํ์ ํธ๋ฆฌ๊ฐ ์๋ ์ฌ๊ท์ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ํธ๋ฆฌ (Tree)์์ ์ฌ์ฉํ๋ ์ฉ์ด - ๋ ธ๋ (Node) ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๊ณ ์๋ ๊ธฐ๋ณธ ์์ - ๊ฐ์ (Edge) ๋ ธ๋์ ๋ ธ๋ ๊ฐ์ ์ฐ๊ฒฐ์ - ๋ฃจํธ๋ ธ๋ (Root Node) ํธ๋ฆฌ ๊ตฌ์กฐ์์ ๋ถ๋ชจ๊ฐ ์๋ ์ต์์ ๋ ธ๋ - ๋ถ๋ชจ๋ ธ๋ (Parent Node) ์์ ๋ ธ๋๋ฅผ ๊ฐ์ง ๋ ธ๋ - ์์๋ ธ๋ (Child Node) ๋ถ๋ชจ ๋ ธ๋์ ํ์ ๋ ธ๋ - ํ์ ๋ ธ๋ (Sibling Node) ๊ฐ์ ๋ถ๋ชจ๋ฅผ ๊ฐ์ง๋ ๋ ธ๋ - ์ธ๋ถ ๋ ธ๋(external node, outer node), ๋จ๋ง ๋ ธ๋ (terminal node), ๋ฆฌํ .. ์ด์ 1 ยทยทยท 7 8 9 10 11 ๋ค์