์๊ณ ๋ฆฌ์ฆ14 11-3๊ฐ. ์ด์ง๊ฒ์ํธ๋ฆฌ (Binary Search Tree) ์ง๋ ๊ฐ์ ๊ณต๋ถ ๋ด์ฉ... ์ด์ง๊ฒ์ํธ๋ฆฌ์ ํ์, ์ฝ์ ์ด์ง๊ฒ์ํธ๋ฆฌ/์ด์งํ์ํธ๋ฆฌ์ ์ญ์ Case 1 : ์์๋ ธ๋๊ฐ ์๋ ๊ฒฝ์ฐ -> ํด๋น ๋ ธ๋๋ฅผ ๊ทธ๋ฅ ์ญ์ ํ๋ค. Case 2 : ์์๋ ธ๋๊ฐ 1๊ฐ์ธ ๊ฒฝ์ฐ -> ์์ ์ ์์๋ ธ๋๋ฅผ ์๋ ์์ ์ ์์น๋ก ๋ณด๋ธ๋ค. Case 3 : ์์๋ ธ๋๊ฐ 2๊ฐ์ธ ๊ฒฝ์ฐ -> ํด๋น ๋ ธ๋์ ์๋ฆฌ๋ ๊ทธ๋๋ก ๋๊ณ , ๋ฐ์ดํฐ๋ง ์ญ์ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ํด๋น ๋ ธ๋์ ๊ฐ์์ ๊ฐ๊น์ด ๊ฐ์ธ ๋ค๋ฅธ ๋ ธ๋๋ฅผ ํด๋น ์๋ฆฌ๋ก ๊ฐ์ ธ ์จ๋ค. ๊ทธ ๋ค๋ฅธ ๋ ธ๋๋ ์ญ์ ํ๋ ค๋ ๋ ธ๋์ successor์ด๋ค. ์ญ์ ํ๋ ค๋ ๋ ธ๋์ successor๋ ์ต๋ 1๊ฐ์ ์์๋ ธ๋๋ฅผ ๊ฐ์ง๋ค. TREE-DELETE(T, z)// z : ์ญ์ ํ ๋ ธ๋ { if left[z] == null or right[z] == null then y 2020. 11. 15. ์ 11-1๊ฐ. ์ด์ง๊ฒ์ํธ๋ฆฌ(Binary Search Tree) ์ด์ง๊ฒ์ํธ๋ฆฌ(Binary Search Tree) - ์ฌ๋ฌ ๊ฐ์ ํค(key)๋ฅผ ์ ์ฅ - ๋ค์๊ณผ ๊ฐ์ ์ฐ์ฐ๋ค์ ์ง์ํ๋ ์๋ฃ๊ตฌ์กฐ INSERT - ์๋ก์ด ํค์ ์ฝ์ SEARTCH - ํค ํ์ DELETE - ํค์ ์ญ์ ex) ์ฌ๋ณผํ ์ด๋ธ search insert delete ๋ฐฐ์ด ์ ๋ ฌ๋ ๊ฒฝ์ฐ O(logn) O(n) O(n) ์ ๋ ฌ๋์ง ์์ ๊ฒฝ์ฐ O(n) O(1) O(1) ์ฐ๊ฒฐ๋ฆฌ์คํธ ์ ๋ ฌ๋ ๊ฒฝ์ฐ O(n) O(n) O(1) ์ ๋ ฌ๋์ง ์์ ๊ฒฝ์ฐ O(n) O(1) O(1) ๋ค์ํ ๋ฐฉ๋ฒ๋ค - ์ ๋ ฌ๋, ํน์ ์ ๋ ฌ๋์ง ์์ ๋ฐฐ์ด ํน์ ์ฐ๊ฒฐ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํ ๊ฒฝ์ฐ INSERT, SEARCH, DELETE ์ค ์ ์ด๋ ํ๋๋ O(n) - ์ด์งํ์ํธ๋ฆฌ(Binary Search Tree), ๋ ๋-๋ธ๋ํธ๋ฆฌ(red-black tree), A.. 2020. 11. 10. ์ 10๊ฐ ํธ๋ฆฌ์ ์ด์งํธ๋ฆฌ ํธ๋ฆฌ (Tree) ๊ณ์ธต์ ์ธ ๊ตฌ์กฐ๋ฅผ ํํํ๋ ๋ฐ ์ฌ์ฉํ๋ค. ์๋ฅผ ๋ค๋ฉด ์กฐ์ง๋๋ ๋๋ ํ ๋ฆฌ์ ์๋ธ๋๋ ํ ๋ฆฌ์ ๊ตฌ์กฐ๋ฅผ ํํํ ๋, ๊ฐ๊ณ๋๋ฅผ ํํํ ๋ ์ด๋ค. ํธ๋ฆฌ๋ ๋ ธ๋(node) ๋ค๊ณผ ๋ ธ๋๋ค์ ์ฐ๊ฒฐํ๋ ๋งํฌ(link)๋ค๋ก ๊ตฌ์ฑ๋๋ค. ๋ฃจํธ(root) : ๋งจ ์์ ๋ ธ๋ ๋งํฌ(link) : ๋ ธ๋๋ค์ ์ฐ๊ฒฐํ๋ ์ (=edge, branch) ํธ๋ฆฌ์ ๋ถ๋ชจ-์์ ๊ด๊ณ ํธ๋ฆฌ ๊ตฌ์กฐ ์์์ ์๋์ ์ผ๋ก ์์ ์๋ ๋ ธ๋๋ฅผ ๋ถ๋ชจ ๋ ธ๋๋ผ ํ๊ณ , ์๋์ ์๋ ๋ ธ๋๋ฅผ ์์ ๋ ธ๋๋ผ ํ๋ค. ํธ๋ฆฌ์ ํ์ ๊ด๊ณ ๋ถ๋ชจ๊ฐ ๋์ผํ ๋ ธ๋๋ค์ ํ์ (sibling) ๊ด๊ณ๋ผ๊ณ ํ๋ค. ๋ฃจํธ ๋ ธ๋๋ฅผ ์ ์ธํ ํธ๋ฆฌ์ ๋ชจ๋ ๋ ธ๋๋ค์ ์ ์ผํ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๊ฐ์ง๋ค. ๋ฆฌํ๋ ธ๋ ์์์ด ์๋ ๋ ธ๋๋ค์ ๋ฆฌํ(leaf) ๋ ธ๋๋ผ ํ๋ค. ๋ฆฌํ๋ ธ๋๊ฐ ์๋ ๋ ธ๋๋ค์ ๋ด๋ถ(internal.. 2020. 11. 8. 9๊ฐ. Java์์์ ์ ๋ ฌ - Arrays ํด๋์ค๊ฐ primitive type์ ๋ฐ์ดํฐ๋ฅผ ์ํ ์ ๋ ฌ ๋ฉ์๋๋ฅผ ์ ๊ณตํ๋ค. int[] data = new int[capacity]; // data[0]์์ data[capacity-1]๊น์ง ๋ฐ์ดํฐ๊ฐ ๊ฝ ์ฐจ์๋ ๊ฒฝ์ฐ์๋ ๋ค์๊ณผ ๊ฐ์ด ์ ๋ ฌํ๋ค. Arrays.sort(data); //๋ฐฐ์ด์ด ๊ฝ ์ฐจ์์ง ์๊ณ , data[0]์์ data[size-1]๊น์ง size๊ฐ์ ๋ฐ์ดํฐ๋ง ์๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ ๋ ฌํ๋ค. Arrays.sort(data, 0, size); - int ์ด์ธ์ ๋ค๋ฅธ primitive type ๋ฐ์ดํฐ(double, char ๋ฑ..)์ ๋ํด์๋ ์ ๊ณตํ๋ค. Primitive type ๋ฐ์ดํฐ์ ๋ง์ฐฌ๊ฐ์ง๋ก Arrays.sort() ๋ฉ์๋๋ก ์ ๋ ฌ๋๋ค. // fruits๋ผ๋ ์ด๋ฆ์ ๋ฐฐ์ด ์ ์ธ๊ณผ .. 2020. 11. 5. 10. ํฉ๋ณ์ ๋ ฌ (merge sort) - ๋ถํ ์ ๋ณต์๊ณ ๋ฆฌ์ฆ(Divide and Conquer) ๊ทธ๋ฅ ๋ง ๊ทธ๋๋ก, ๋ฐฐ์ด์ ๋ถํ ํ๊ณ , ํด๊ฒฐํ๊ณ , ... ์ด๋ฅผ ๋ฐ๋ณตํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. 1. ๋ถํ : ํด๊ฒฐํ๊ณ ์ ํ๋ ๋ฌธ์ ๋ฅผ ์์ ํฌ๊ธฐ์ ๋์ผํ ๋ฌธ์ ๋ค๋ก ๋ถํ 2. ์ ๋ณต : ๊ฐ๊ฐ์ ์์ ๋ฌธ์ ๋ฅผ ์ํ์ ์ผ๋ก ํด๊ฒฐ 3. ํฉ๋ณ : ์์ ๋ฌธ์ ์ ํด๋ฅผ ํฉํ์ฌ(merge), ์๋ ๋ฌธ์ ์ ๋ํ ํด๋ฅผ ๊ตฌํจ ๋ํ์ ์ธ ๋ถํ ์ ๋ณต์๊ณ ๋ฆฌ์ฆ์๋ ํฉ๋ณ์ ๋ ฌ(merge sort)๊ณผ ํต์ ๋ ฌ(quick sort)์ด ์๋ค. ๋ถํ ์ ํ๋์ ํฐ ๋ฌธ์ ๋ฅผ ๊ฐ์ ์์ ๋ฌธ์ ๋ก ๋๋๋ ๊ฒ์ด๋ค. ์ด ๊ฐ๊ฐ์ ์์ ๋ฌธ์ ๋ค์ ์๋ ๋ฌธ์ ์ ๋์ผํ ๋ฌธ์ ์ฌ์ผ ํ๋ค. ์ ๋ณต์ด๋ผ๋ ์๋ฏธ๋ ๊ฐ๊ฐ์ ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๊ฒ์ด๋ค. ์์ ๊ทธ๋ฆผ์ ํฉ๋ณ์ ๋ ฌ์ ๊ฐ๋จํ๊ฒ ํํํ ์์ด๋ค. ์๋ฅผ ๋ค์ด ์์ ๋ฐฐ์ด์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ๋ฅผ .. 2020. 10. 15. ์ด์ 1 2 ๋ค์ ๋ฐ์ํ