๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๋ฐ˜์‘ํ˜•

๐Ÿ–ฅ Computer Science/Data Structure10

[Data Structure] Trie๋ž€? (feat. ์ด๋ก ) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์—ฐ๊ฒฐ๋œ ๋ฌธ์ž์—ด์„ ํšจ์œจ์ ์œผ๋กœ ์ €์žฅํ•ด ๊ฒ€์ƒ‰์„ ํšจ์œจ์ ์œผ๋กœ ๋„์™€์ฃผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ธ ํŠธ๋ผ์ด(Trie)์— ๋Œ€ํ•ด ์ •๋ฆฌํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ Trie๋ž€? ํŠธ๋ผ์ด(trie)๋Š” ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ผ์ข…์ด๋‹ค. ๋™์  ์ง‘ํ•ฉ์ด๋‚˜ ์—ฐ๊ด€ ๋ฐฐ์—ด์„ ์ €์žฅํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋˜๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ์ด๋‹ค. ์ฃผ๋กœ ๋ฌธ์ž์—ด์ด ํ‚ค์ธ ๊ฒฝ์šฐ๊ฐ€ ๋งŽ๋‹ค. ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์™€ ๋‹ฌ๋ฆฌ ํŠธ๋ฆฌ์˜ ์–ด๋–ค ๋…ธ๋“œ๋„ ๊ทธ ๋…ธ๋“œ ์ž์ฒด์™€ ์—ฐ๊ด€๋œ ํ‚ค๋Š” ์ €์žฅํ•˜์ง€ ์•Š๋Š”๋‹ค. ๋Œ€์‹  ๋…ธ๋“œ๊ฐ€ ํŠธ๋ฆฌ์—์„œ ์ฐจ์ง€ํ•˜๋Š” ์œ„์น˜๊ฐ€ ์—ฐ๊ด€๋œ ํ‚ค๋ฅผ ์ •์˜ํ•œ๋‹ค. ์ฆ‰, ํ‚ค์˜ ๊ฐ’์€ ์ž๋ฃŒ ๊ตฌ์กฐ ์ „์ฒด์— ๋ถ„์‚ฐ๋œ๋‹ค. ๋…ธ๋“œ์˜ ๋ชจ๋“  ์ž์†์€ ๋…ธ๋“œ์— ์—ฐ๊ด€๋œ ๋ฌธ์ž์—ด์˜ ๊ณตํ†ต ์ ‘๋‘์‚ฌ๋ฅผ ๊ณต์œ ํ•œ๋‹ค. ๋ฃจํŠธ๋Š” ๋นˆ ๋ฌธ์ž์—ด์— ์—ฐ๊ด€๋œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ํŠธ๋ฆฌ ํ˜•ํƒœ๋กœ ์—ฐ๊ฒฐ๋œ ๋ฌธ์ž์—ด์„ ์ฐจ๋ก€๋กœ ์ €์žฅํ•˜๋Š”.. 2022. 7. 29.
[Data Structure] B-Tree๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ๊ท ํ˜• ๋ํŒ์™• (์ด๋ฆ„ ์ž์ฒด๊ฐ€ Balanced - Tree)์ธ B-Tree์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ B-Tree์˜ ๋ฐฐ๊ฒฝ B-ํŠธ๋ฆฌ(B-tree)๋Š” ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์™€ ํŒŒ์ผ ์‹œ์Šคํ…œ์—์„œ ๋„๋ฆฌ ์‚ฌ์šฉ๋˜๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ผ์ข…์œผ๋กœ, ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ํ™•์žฅํ•ด ํ•˜๋‚˜์˜ ๋…ธ๋“œ๊ฐ€ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์ž์‹ ๋…ธ๋“œ์˜ ์ตœ๋Œ€ ์ˆซ์ž๊ฐ€ 2๋ณด๋‹ค ํฐ ํŠธ๋ฆฌ ๊ตฌ์กฐ์ด๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ์กฐ๊ธˆ ๋” ํšจ์œจ์ ์œผ๋กœ ํ™•์žฅํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์—์š”! ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ์ตœ์•…์˜ ๊ฒฝ์šฐ O(n)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ–๊ธฐ ๋•Œ๋ฌธ์— ๊ทธ๊ฒƒ์„ ์กฐ๊ธˆ ๋” ํšจ์œจ์ ์œผ๋กœ ๋งŒ๋“  ๊ฒƒ์ด O(logn)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ–๋Š” AVL ํŠธ๋ฆฌ์˜€์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ๋งŒ์•ฝ 2์ฒœ๋งŒ๊ฐœ์˜ ๋ฐ์ดํ„ฐ๊ฐ€ ์žˆ๋‹ค๋ฉด log20,000,000 = 24 ์ฆ‰, ์ตœ๋Œ€ 2.. 2021. 12. 6.
[Data Structure] AVL ํŠธ๋ฆฌ ๊ตฌํ˜„ํ•ด๋ณด๊ธฐ (feat. Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์ €๋ฒˆ ์‹œ๊ฐ„์— AVL ํŠธ๋ฆฌ๊ฐ€ ๋ญ”์ง€ ์ด๋ก ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์•˜๋Š”๋ฐ์š”. (ํ˜น์‹œ ์•ˆ๋ณด์‹  ๋ถ„๋“ค์€ ์—ฌ๊ธฐ ์—์„œ ํ™•์ธํ•ด์ฃผ์„ธ์š”!) ์˜ค๋Š˜์€ AVL ํŠธ๋ฆฌ๋ฅผ ์ง์ ‘ ๊ตฌํ˜„ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ AVLNode ๊ธฐ๋ณธ์ ์œผ๋กœ ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ์™€ ๋˜‘๊ฐ™์ง€๋งŒ ์™ผ์ชฝ๊ณผ,์˜ค๋ฅธ์ชฝ ์ž์‹์˜ ๋†’์ด์™€ ๋ฐธ๋Ÿฐ์Šค ํŒฉํ„ฐ๋ฅผ ์ธก์ •ํ•  ๋ณ€์ˆ˜๋ฅผ ๋”ฐ๋กœ ๋งŒ๋“ค์–ด์—ˆ์Šต๋‹ˆ๋‹ค. class AVLNode { var value:T var leftChild:AVLNode? var rightChild:AVLNode? var height:Int = 0 var leftHeight:Int { return leftChild?.height ?? -1 } var rightHeight:Int { return rightChild?.height ?? -1 } var.. 2021. 12. 6.
[Data Structure] AVL(Adelson-Velsky and Landis) ํŠธ๋ฆฌ๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์ €๋ฒˆ์— ์ •๋ฆฌํ–ˆ๋˜ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋ฅผ ๋” ์—…๊ทธ๋ ˆ์ด๋“œ(?)ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ธ AVL ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. (ํ˜น์‹œ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ๋Œ€ํ•ด ๋ชจ๋ฅด์‹œ๋Š” ๋ถ„๋“ค์€ ์—ฌ๊ธฐ ์—์„œ ๋ณด๊ณ  ์™€์ฃผ์„ธ์š”!) ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ AVL(Adelson-Velsky and Landis) ํŠธ๋ฆฌ๋ž€? ๐Ÿค” ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ AVL ํŠธ๋ฆฌ(๋ฐœ๋ช…์ž์˜ ์ด๋ฆ„์ธ Adelson-Velsky and Landis์—์„œ ๋”ฐ์˜จ ์ด๋ฆ„)๋Š” ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์ด๋‹ค. ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š” ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ ์ค‘ ์ฒ˜์Œ์œผ๋กœ ๋ฐœ๋ช…๋˜์—ˆ๋‹ค. AVL ํŠธ๋ฆฌ์—์„œ, ๋‘ ์ž์‹ ์„œ๋ธŒํŠธ๋ฆฌ์˜ ๋†’์ด๋Š” ํ•ญ์ƒ ์ตœ๋Œ€ 1๋งŒํผ ์ฐจ์ด๋‚œ๋‹ค. ๋งŒ์•ฝ ์–ด๋–ค ์‹œ์ ์—์„œ ๋†’์ด ์ฐจ์ด๊ฐ€ 1๋ณด๋‹ค ์ปค์ง€๋ฉด ์ด ์†์„ฑ์„ ์œ ์ง€ํ•˜๊ธฐ ์œ„ํ•ด์„œ ์Šค์Šค๋กœ ๊ท ํ˜•์„ ์žก๋Š”๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, .. 2021. 12. 1.
[Data Structure] ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree) ๊ตฌํ˜„ํ•ด๋ณด๊ธฐ (feat.Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์ €๋ฒˆ ์‹œ๊ฐ„์— ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๊ฐ€ ๋ญ”์ง€ ์ด๋ก ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์•˜๋Š”๋ฐ์š”. ์˜ค๋Š˜์€ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋ฅผ ์ง์ ‘ ๊ตฌํ˜„ํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ BSTNode ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๋ฅผ ๋งŒ๋“ค์–ด ์ฃผ๊ฒ ์Šต๋‹ˆ๋‹ค. ๋…ธ๋“œ๋Š” ๊ฐ’,์™ผ์ชฝ,์˜ค๋ฅธ์ชฝ ์ž์‹์˜ ๋…ธ๋“œ ์ •๋ณด๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. class BSTNode { var value:T var leftChild:BSTNode? var rightChild:BSTNode? init(value:T) { self.value = value } } Binary Search Tree ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์˜ ์ตœ์ƒ๋‹จ ๊ฐ’์„ ๊ฐ€์งˆ root๋ฅผ ํ”„๋กœํผํ‹ฐ๋กœ ์ •์˜ํ–ˆ์Šต๋‹ˆ๋‹ค. struct BinarySearchTree { var root:BSTNode? Insert public mutatin.. 2021. 11. 18.
[Data Structure] ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree)๋ž€? ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ ์ค‘ ํšจ์œจ์ ์ธ ๊ฒ€์ƒ‰,์‚ฝ์ž…,์‚ญ์ œ๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ์ด์ง„ ํŠธ๋ฆฌ(Binary Tree)๋ž€? ๐Ÿค” ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ์ด์ง„ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋จผ์ € ์ด์ง„ ํŠธ๋ฆฌ๊ฐ€ ๋ญ”์ง€์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๊ฐ๊ฐ์˜ ๋…ธ๋“œ๊ฐ€ ์ตœ๋Œ€ ๋‘ ๊ฐœ์˜ ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง€๋Š” ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ๋กœ, ์ž์‹ ๋…ธ๋“œ๋ฅผ ๊ฐ๊ฐ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์™€ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ๋ผ๊ณ  ํ•œ๋‹ค.... - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ๋…ธ๋“œ๋งˆ๋‹ค ์ž์‹์ด 2๊ฐœ ์ดํ•˜์ธ ํŠธ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. ์•„๋ž˜ ๊ทธ๋ฆผ์ฒ˜๋Ÿผ ์ด๋ฃจ์–ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. (์ž์‹์ด ์—†์–ด๋„ ๋˜๊ณ , ํ•˜๋‚˜์—ฌ๋„ ๋˜๊ณ , ๋‘ ๊ฐœ์—ฌ๋„ ๋ฉ๋‹ˆ๋‹ค.) ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ(Binary Search Tree)๋ž€? ๐Ÿง ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์†.. 2021. 11. 17.
[Data Structure] ํ•ด์‰ฌ ํ…Œ์ด๋ธ”(Hash Table) ๊ตฌํ˜„ํ•ด๋ณด๊ธฐ(feat. Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์ €๋ฒˆ ๊ธ€์—์„œ ํ•ด์‰ฌ ํ…Œ์ด๋ธ”์˜ ์ด๋ก ์— ์ด์–ด์„œ ์ง์ ‘ ๊ตฌํ˜„ํ•ด ๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! (ํ˜น์‹œ ์ €๋ฒˆ ๊ธ€์„ ์•ˆ๋ณด์…จ๋‹ค๋ฉด ์—ฌ๊ธฐ ๋ฅผ ํ†ตํ•ด์„œ ๋ณด๊ณ  ์™€์ฃผ์„ธ์š”~) ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ HashTable ๋จผ์ € ์ €๋Š” ํ•ด์‰ฌ ํ•จ์ˆ˜๋ฅผ Digit Folding ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด์„œ ๋งŒ๋“ค ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— key๊ฐ’์„ String์œผ๋กœ ์„ค์ •ํ–ˆ์Šต๋‹ˆ๋‹ค. ๋˜ํ•œ ์ถฉ๋Œ์ด ๋‚ฌ์„ ๋•Œ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์œผ๋กœ Chaining ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•˜์˜€์ง€๋งŒ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ ๋Œ€์‹  ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ–ˆ์Šต๋‹ˆ๋‹ค. ์•„๋ž˜์™€ ๊ฐ™์ด typealias๋กœ ๋ณ„์นญ์„ ์„ค์ •ํ•ด์ฃผ๊ณ  ๋ฒ„ํ‚ท์„ ์ด์ค‘๋ฐฐ์—ด๋กœ ์„ ์–ธํ–ˆ์Šต๋‹ˆ๋‹ค. public struct HashTable { public typealias Key = String private typealias Element = (key:Key,value:Val.. 2021. 11. 16.
[Data Structure] ํ•ด์‰ฌ ํ…Œ์ด๋ธ”(Hash Table)์ด๋ž€? (feat. ์ด๋ก ) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์˜ค๋Š˜์€ ์šฐ๋ฆฌ๊ฐ€ ์•„์ฃผ ํ”ํ•˜๊ฒŒ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ๋Š” ํ•ด์‰ฌ ํ…Œ์ด๋ธ”, Swift๋กœ ๋งํ•˜๋ฉด ๋”•์…”๋„ˆ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณผ ๊ฑฐ์—์š”! ์ด๋ฏธ ๊ตฌํ˜„๋˜์–ด ์žˆ๋Š” ์ฝ”๋“œ๋กœ ์‰ฝ๊ฒŒ ์‚ฌ์šฉํ–ˆ๋Š”๋ฐ ์ง์ ‘ ๊ตฌํ˜„ํ•˜๋ ค๊ณ  ํ•˜๋‹ˆ ์ง„์งœ ๋ณต์žกํ•˜๋”๋ผ๊ตฌ์š”. ๊ทธ๋ž˜์„œ ์˜ค๋Š˜์€ ํ•ด์‰ฌ ํ…Œ์ด๋ธ”์— ๋Œ€ํ•ด์„œ ์ •๋ฆฌํ•ด๋ณด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ํ•ด์‰ฌ ํ…Œ์ด๋ธ”(Hash Table)์ด๋ž€? ์ •์˜๋Š” ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. ํ•ด์‹œ ํ…Œ์ด๋ธ”์€ ์ปดํ“จํŒ…์—์„œ ํ‚ค๋ฅผ ๊ฐ’์— ๋งคํ•‘ํ•  ์ˆ˜ ์žˆ๋Š” ๊ตฌ์กฐ์ธ, ์—ฐ๊ด€ ๋ฐฐ์—ด ์ถ”๊ฐ€์— ์‚ฌ์šฉ๋˜๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ์ด๋‹ค. ํ•ด์‹œ ํ…Œ์ด๋ธ”์€ ํ•ด์‹œ ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ƒ‰์ธ(index)์„ ๋ฒ„ํ‚ท(bucket)์ด๋‚˜ ์Šฌ๋กฏ(slot)์˜ ๋ฐฐ์—ด๋กœ ๊ณ„์‚ฐํ•œ๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, key์™€ value๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค. key๊ฐ’์œผ๋กœ value๋ฅผ ํ•œ ๋ฒˆ์— ์ฐพ์„ .. 2021. 11. 15.
[Data Structure] ํž™(Heap)์ด๋ž€? (feat. Swift) ์•ˆ๋…•ํ•˜์„ธ์š” Foma ๐Ÿ’ป ์ž…๋‹ˆ๋‹ค! ์š”์ฆ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ณต๋ถ€ํ•˜๊ณ  ์žˆ๋Š”๋ฐ ๊ทธ ์ค‘ ํž™์†ŒํŠธ์— ๋Œ€ํ•ด ์•Œ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ํž™์†ŒํŠธ๋ฅผ ํ•˜๋ ค๋ฉด ํž™์ด๋ผ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ๊ฐ€ ํ•„์š”ํ•˜๋”๋ผ๊ตฌ์š”. ๊ทธ๋ž˜์„œ ํž™์ด ๋ฌด์—‡์ด๊ณ  ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„ํ•˜๋Š”์ง€์— ๋Œ€ํ•ด ์ •๋ฆฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค! ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ(Complete Binary Tree)๋ž€? โ›“ ๋จผ์ € ํž™์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๊ธฐ ์ „์— ์™„์ „์ด์ง„ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค. ์ด์œ ๋Š” ํž™์ด ์™„์ „์ด์ง„ํŠธ๋ฆฌ๋กœ ๋˜์–ด์žˆ๊ธฐ ๋–„๋ฌธ์ž…๋‹ˆ๋‹ค. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ์—์„œ, ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์„ ์ œ์™ธํ•˜๊ณ  ๋ชจ๋“  ๋ ˆ๋ฒจ์ด ์™„์ „ํžˆ ์ฑ„์›Œ์ ธ ์žˆ์œผ๋ฉฐ, ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ์˜ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๊ฐ€๋Šฅํ•œ ํ•œ ๊ฐ€์žฅ ์™ผ์ชฝ์— ์žˆ๋‹ค. ๋งˆ์ง€๋ง‰ ๋ ˆ๋ฒจ h ์—์„œ 1๋ถ€ํ„ฐ 2h-1 ๊ฐœ์˜ ๋…ธ๋“œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค. ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ๋Š” ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•ด ํšจ์œจ์ ์œผ๋กœ ํ‘œํ˜„ ๊ฐ€๋Šฅํ•˜๋‹ค. - ์œ„ํ‚ค ๋ฐฑ๊ณผ - ์ฆ‰, ๋งจ ๋งˆ์ง€๋ง‰.. 2021. 10. 15.
[Data Structure] ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์ž(Linked List) ์•ˆ๋…•ํ•˜์„ธ์š” Foma๐Ÿ‘Ÿ ์ž…๋‹ˆ๋‹ค. ์˜ค๋Š˜์€ ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค๊ณ  ํ•˜๋Š”๋ฐ์š”. ์–ผ๋งˆ ์ „์— 2021 ์นด์นด์˜ค ์ธํ„ด์‰ฝ์— ์ถœ์ œ๋˜์—ˆ๋˜ "ํ‘œํŽธ์ง‘" ์ด๋ผ๋Š” ๋ฌธ์ œ๋ฅผ ํ’€๊ฒŒ ๋˜์—ˆ๋Š”๋ฐ ํ•ด๋‹น ๋ฌธ์ œ๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๊ผญ ์‚ฌ์šฉํ•ด์•ผ ํšจ์œจ์„ฑ์„ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. ๊ทธ ๋™์•ˆ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด๋ณผ ์ผ์ด ๊ฑฐ์˜ ์—†์–ด์„œ ๊ตฌ์ฒด์ ์œผ๋กœ ์•Œ์•„๋ณธ ์ ์ด ์—†์—ˆ๋Š”๋ฐ ์ด๋ฒˆ ๊ธฐํšŒ์— ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ์˜ ์žฅ์ ๊ณผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ์ •๋ฆฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์‹œ์ž‘ํ• ๊ฒŒ์š”~ Linked List๋ž€? "์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ, ๋งํฌ๋“œ ๋ฆฌ์ŠคํŠธ(linked list)๋Š” ๊ฐ ๋…ธ๋“œ๊ฐ€ ๋ฐ์ดํ„ฐ์™€ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง€๊ณ  ํ•œ ์ค„๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ ๊ตฌ์กฐ์ด๋‹ค. ์ด๋ฆ„์—์„œ ๋งํ•˜๋“ฏ์ด ๋ฐ์ดํ„ฐ๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ๋…ธ๋“œ๋“ค์ด ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š”๋ฐ, ๋…ธ๋“œ์˜ ํฌ์ธํ„ฐ๊ฐ€ ๋‹ค์Œ์ด๋‚˜ ์ด์ „์˜ ๋…ธ๋“œ์™€์˜ ์—ฐ๊ฒฐ์„.. 2021. 8. 11.
728x90
๋ฐ˜์‘ํ˜•