๐ฎ ์จ-์์ค/๐ฆด ์๋ฃ๊ตฌ์กฐ
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 8: ์ด์ง ํ์ ํธ๋ฆฌ(Binary Search Tree)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 8: ์ด์ง ํ์ ํธ๋ฆฌ(Binary Search Tree)
2021.12.15์ด์ง ํ์ ํธ๋ฆฌ (BST) ์ด์ง ํ์ ํธ๋ฆฌ๋ ์ด์ง ํธ๋ฆฌ์ ๋ช๊ฐ์ง ์กฐ๊ฑด์ด ๋ ์ถ๊ฐ๋ ํธ๋ฆฌ์
๋๋ค. ์ด์ง ํ์ ํธ๋ฆฌ๋ ๋ค์ ์กฐ๊ฑด์ ๋ง์กฑํด์ผํฉ๋๋ค. 1) ์ด๋ค ๋ฃจํธ๋
ธ๋(์๋ธํธ๋ฆฌ์ ๋ฃจํธ ํฌํจ)์ ์ผ์ชฝ ์๋ธํธ๋ฆฌ์ ๋
ธ๋๋ค์ด ๊ฐ์ง ๊ฐ์ ๋ฃจํธ ๋
ธ๋๊ฐ ๊ฐ์ง ๊ฐ๋ณด๋ค ์์์ผํฉ๋๋ค. 2) ์ด๋ค ๋ฃจํธ๋
ธ๋์ ์ค๋ฅธ์ชฝ ์๋ธํธ๋ฆฌ์ ๋
ธ๋๋ค์ด ๊ฐ์ง ๊ฐ์ ๋ฃจํธ ๋
ธ๋๊ฐ ๊ฐ์ง ๊ฐ๋ณด๋ค ์ปค์ผํฉ๋๋ค. 3) ๋
ธ๋์ ๊ฐ์ผ๋ก ํธ๋ฆฌ ์ฐ์ฐ์ด ์ด๋ฃจ์ด์ง๊ธฐ ๋๋ฌธ์ ์ค๋ณต๋ ๋
ธ๋ ๊ฐ์ ํ์ฉํ์ง ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ์ด๋ฐ ํธ๋ฆฌ๋ ์ด์ง ํ์ ํธ๋ฆฌ๊ฐ ๋ ์ ์์ต๋๋ค. ๋ฃจํธ ๋
ธ๋์ธ 1๋ณด๋ค ํฐ ๊ฐ์ธ 2๊ฐ ์ผ์ชฝ ์์ ๋
ธ๋์ ์์นํด์๊ณ ์ผ์ชฝ ์์ ๋
ธ๋์ธ 4, 6๋ ๋ชจ๋ ์์ ์ ๋ถ๋ชจ ๋
ธ๋์ ๊ฐ๋ณด๋ค ํฌ๊ธฐ ๋๋ฌธ์
๋๋ค ๋ฐ๋ฉด์ ์ด๋ฐ ํธ๋ฆฌ๋ ์ด์ง ํ์ ํธ๋ฆฌ๊ฐ ๋ ์ ์์ต๋๋ค. ๋ฃจํธ๋
ธ๋์ธ ..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 7: ํธ๋ฆฌ์ ์ด์ง ํธ๋ฆฌ(Binary Tree)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 7: ํธ๋ฆฌ์ ์ด์ง ํธ๋ฆฌ(Binary Tree)
2021.12.15ํธ๋ฆฌ์ ์ ์ ๋จผ์ , ํธ๋ฆฌ์ ๋ํด์ ์ ์ํด๋ณด๋ฉด, ํธ๋ฆฌ๋ ๋ช๊ฐ์ง ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ทธ๋ํ์
๋๋ค. 1) ํธ๋ฆฌ์ ๊ฐ์ ์๋ ๋ฐฉํฅ์ด ์์ต๋๋ค. ์ฆ, ํธ๋ฆฌ๋ ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ์
๋๋ค. 2) ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๋ชจ๋ ๋
ธ๋๋ ์ฐ๊ฒฐ๋์ด ์๋ ์ฐ๊ฒฐ ๊ทธ๋ํ์
๋๋ค. ์ฐ๊ฒฐ๋ ๊ฐ์ ์ค ํ๋๋ง ์ญ์ ํด๋ ์ฐ๊ฒฐ ๊ทธ๋ํ๊ฐ ๊นจ์ง๋๋ค. -> ์ฌ๊ธฐ์ ์ฐ๊ฒฐ๊ทธ๋ํ๋ ๊ทธ๋ํ์ ์์์ ๋
ธ๋ ์ฌ์ด์ ํญ์ ๊ฒฝ๋ก๊ฐ ์กด์ฌํจ์ ์๋ฏธํฉ๋๋ค. ์ด๋ค ๋
ธ๋๋ก ๊ฐ๋ ๊ฒฝ๋ก๊ฐ ์์ด์ง๋ฉด ํด๋น ๋
ธ๋๋ ํธ๋ฆฌ์ ํฌํจ๋ ์ ์๊ฒ ์ฃ ? 3) ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๊ฐ์ ์ ๊ฐ์๋ ํญ์ ๋
ธ๋์ ๊ฐ์๋ณด๋ค ํ๋ ์ ์ต๋๋ค. ๋ฐ๋ผ์ ์ฌ์ดํด์ด ๋ฐ์ํ์ง ์์ต๋๋ค. ์ด์ง ํธ๋ฆฌ (Binary Tree) ์ด์ง ํธ๋ฆฌ๋ ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๊ฐ ๋
ธ๋๊ฐ ์ต๋ ๋ ๊ฐ์ ์์ ๋
ธ๋๋ฅผ ๊ฐ์ง๋ ํธ๋ฆฌ๋ฅผ ์๋ฏธํฉ๋๋ค. ์ด์ง ํธ๋ฆฌ์ ์ข
๋ฅ ์ด์ง ..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 6: ์ฐ์ ์์ ํ(Priority Queue)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 6: ์ฐ์ ์์ ํ(Priority Queue)
2021.12.15์ฐ์ ์์ ํ(Priority Queue) ์ฐ์ ์์ ํ๋ ํ์ ์ด์ฉํด์ ๊ฐ์ฅ ๋์ ์ฐ์ ์์์ ์๋ ์์๋ฅผ ํญ์ ์ ์ผ ์ฒ์์ ์์น์ํค๋ ํน๋ณํ ํ์
๋๋ค. ๊ฐ์ฅ ์ฐ์ ์์๊ฐ ๋์ ์์๊ฐ ํ์์ ์ ๊ฑฐ๋๋ฉด ๊ทธ ๋ค์ ์ฐ์ ์์์ ์๋ ์์๊ฐ ํ์ ์ฒซ ์์๋ก ์ด๋ํฉ๋๋ค. ์ฌ์ค ์ฐ์ ์์ ํ๋ ํ์ด ์ ๋ถ์ธ ์๋ฃ๊ตฌ์กฐ์ด๊ธฐ ๋๋ฌธ์ ํ์ ์์ง ๋ชจ๋ฅด์ ๋ค๋ฉด ์๋ ํฌ์คํธ๋ฅผ ๋จผ์ ์ฝ์ด์ฃผ์ธ์! ์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 5: ํ(Heap) ํ (Heap) ํ์ ์ด์งํธ๋ฆฌ๋ฅผ ์ฌ์ฉํด์ ๋ฐ์ดํฐ๋ค์ ๋ฐ์ ๋ ฌ ์ํ๋ก ์ ์งํ๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ํ์ ํธ๋ฆฌ์ ๋ฃจํธ ๋
ธ๋์ ๋ฐ์ดํฐ๋ค์ ์ต์๊ฐ ํน์ ์ต๋๊ฐ์ ์ ์ฅํ๋๋ฐ์, ์ต์๊ฐ์ ๋ฃจํธ์ ๋ ๋๋ jeonyeohun.tistory.com ์ฐ์ ์์ ์ค์ ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํ๊ธฐ ์ํด์๋ ์ด๋ค ๊ธฐ์ค์ผ๋ก ์ฐ์ ์์๋ฅผ ์ ..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 5: ํ(Heap)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 5: ํ(Heap)
2021.12.13ํ (Heap) ํ์ ์ด์งํธ๋ฆฌ๋ฅผ ์ฌ์ฉํด์ ๋ฐ์ดํฐ๋ค์ ๋ฐ์ ๋ ฌ ์ํ๋ก ์ ์งํ๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ํ์ ํธ๋ฆฌ์ ๋ฃจํธ ๋
ธ๋์ ๋ฐ์ดํฐ๋ค์ ์ต์๊ฐ ํน์ ์ต๋๊ฐ์ ์ ์ฅํ๋๋ฐ์, ์ต์๊ฐ์ ๋ฃจํธ์ ๋ ๋๋ ์ต์ํ, ์ต๋๊ฐ์ ๋ฃจํธ์ ๋๋ฉด ์ต๋ํ์ด๋ผ๊ณ ํฉ๋๋ค. ์์ ์ด์ง ํธ๋ฆฌ ์ด์ง ํธ๋ฆฌ๋ ํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๋ ๋ชจ๋ ๋
ธ๋๊ฐ ์ต๋ ๋ ๊ฐ์ ์์ ๋
ธ๋๋ฅผ ๊ฐ์ง๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ๊ทธ๋ฆฌ๊ณ ์์ ์ด์ง ํธ๋ฆฌ๋ ๊ฐ ๋์ด์ ์๋ ๋ชจ๋ ๋
ธ๋๊ฐ ์์ ๋
ธ๋๋ฅผ ๊ฐ์ ธ์ผ ๋ค์ ๋์ด์ ์ ๋
ธ๋๋ฅผ ์ถ๊ฐํ ์ ์๊ณ , ๊ฐ์ฅ ์ผ์ชฝ๋ถํฐ ์ฐจ๋ก๋๋ก ๋
ธ๋๋ฅผ ์ฑ์์ผํฉ๋๋ค. ์ด๋ฐ ์ด์ง ํธ๋ฆฌ๋ ๋ฐฐ์ด๋ก๋ ๊ตฌํ์ด ๊ฐ๋ฅํ๋ฐ์, ๋ฃจํธ ๋
ธ๋๋ฅผ ์ธ๋ฑ์ค 1๋ก ์ผ์ผ๋ฉด ์ด๋ค index ๋ฒ์งธ ๋
ธ๋์ ์ผ์ชฝ ์์ ๋
ธ๋๋ index * 2, ์ค๋ฅธ์ชฝ ์์ ๋
ธ๋๋ (index * 2) + 1 ๋ก ๊ตฌํ ์ ..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 4: ๋๋ธ ๋งํฌ๋ ๋ฆฌ์คํธ(Doubly Linked List)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 4: ๋๋ธ ๋งํฌ๋ ๋ฆฌ์คํธ(Doubly Linked List)
2021.12.13๋๋ธ ๋งํฌ๋ ๋ฆฌ์คํธ(Doubly Linked List) ๋๋ธ ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๋งํฌ๋ ๋ฆฌ์คํธ์ ๊ฐ๋
์ ๊ฐ์ง๋ง ๊ฐ ๋
ธ๋๊ฐ ์์ ์ ์ด์ ๋
ธ๋๊น์ง ์๊ณ ์๋ค๋ ์ ์์ ๋ค๋ฆ
๋๋ค. ๊ธฐ์กด ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๊ฐ ๋
ธ๋๊ฐ ๋ฐ๋ก ๋ค์ ๋
ธ๋์ ์ฐธ์กฐ ๊ฐ๋ง ์๊ณ ์์ง๋ง, ์ด๋ฒ์๋ ์์ ์ ์์ชฝ์ ๋
ธ๋๋ฅผ ๋ชจ๋ ์ฐธ์กฐํ๊ธฐ ๋๋ฌธ์ ์ญ์ ๋ ์ฝ์
์ฐ์ฐ์ ๊ตฌํ์ด ์กฐ๊ธ ๋ ์ฌ์์ง๋๋ค. ๋ผ๋ ๋ง๋ค๊ธฐ Node import Foundation class Node { let id: Int let data: T var next: Node? = nil var prev: Node? = nil init(id: Int, data: T) { self.id = id self.data = data } } ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ณ ๋ฆฌ์คํธ๋ฅผ ๊ตฌ์ฑํ ๋
ธ๋๋ ๊ฐ์ ์์ ์ id, ์ ์ฅ..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 3: ํ(Queue)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 3: ํ(Queue)
2021.12.13ํ (Queue) ํ๋ FIFO(First In First Out)์ ํน์ฑ์ ๊ฐ์ง๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ์ด๋ฆ์ฒ๋ผ ๊ฐ์ฅ ๋จผ์ ๋ฃ์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋จผ์ ๊บผ๋ด๋ ํน์ง์ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์ค์ํํธ์์๋ ๋ฐฐ์ด์์ removeFirst๋ฅผ ์ง์ํ๊ธด ํ์ง๋ง, ์ด๋ ๊ฒ ์๊ฐ๋ณต์ก๋๋ O(n)์ด๋ผ์, ๋์๋ง FIFO์ผ ๋ฟ, ์ญ์ ์ O(1)์ ๋ณด์ฅํ๋ ํ๊ฐ ๋ ์๋ ์์ต๋๋ค. ๊ทธ๋์ ์ด ํฌ์คํธ์์๋ ๋งํฌ๋ ๋ฆฌ์คํธ๋ฅผ ์ฌ์ฉํด์ ํ๋ฅผ ๊ตฌํํ๋๋ก ํ๊ฒ ์ต๋๋ค. ๋ผ๋ ๋ง๋ค๊ธฐ var list = TwoPointerLinkedList() init(_ elements: [T] = []) { for element in elements { list.add(node: Node(data: element)) } } var count : Int { retu..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 2: ๋งํฌ๋ ๋ฆฌ์คํธ(Linked List)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 2: ๋งํฌ๋ ๋ฆฌ์คํธ(Linked List)
2021.12.13๋งํฌ๋ ๋ฆฌ์คํธ (Linked List) ๋งํฌ๋ ๋ฆฌ์คํธ๋ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ง๊ณ ์๋ ๋
ธ๋๋ค์ ํฌ์ธํฐ๋ก ์ ํ์ ์ผ๋ก ์ฐ๊ฒฐํด ์ฌ์ฉํ๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ์ญ์ ์ ์ฝ์
์ O(1)์ ์๊ฐ๋ณต์ก๋๊ฐ ๊ฑธ๋ฆฌ๊ธฐ ๋๋ฌธ์(์ํ๋ ๋
ธ๋๊น์ง์ ํ์์๊ฐ ์ ์ธ) ๋น๋ฒํ๊ฒ ์ฝ์
๊ณผ ์ญ์ ๊ฐ ํ์ํ ์ํฉ์ ์ ์ฉํ๊ฒ ์ฌ์ฉํ ์ ์์ต๋๋ค. ํ์ง๋ง ๋์์ ๋ฐฐ์ด์ฒ๋ผ ์ธ๋ฑ์ค๋ฅผ ํตํ Random Access๊ฐ ๋ถ๊ฐ๋ฅํ๊ณ , ์ฒ์๋ถํฐ ์ํ๋ ๋ฐ์ดํฐ๊ฐ ๋์ฌ ๋๊น์ง ํ์์ ์งํํด์ผํ๊ธฐ ๋๋ฌธ์ ํ์์๋ O(N)์ ์๊ฐ๋ณต์ก๋๊ฐ ์๊ตฌ๋๋ค๋ ๋จ์ ์ด ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ํฌ์ธํฐ ๊ธฐ๋ฐ์ด๋ผ ๋๋ฒ๊น
์ด ์ด๋ ค์์ใ
๋ผ๋ ๋ง๋ค๊ธฐ Node ๋จผ์ ๋ฐ์ดํฐ๋ฅผ ์ค์ ๋ก ์ ์ฅํ๊ณ , ๋ค์ ๋
ธ๋์ ์ฐธ์กฐ๊ฐ์ ์ ์ฅํ ๋
ธ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ์ํฉ์๋ค! import Foundation class Node { let i..
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 1: ์คํ(Stack)
์ค์ํํธ๋ก ๊ตฌํํ๋ ์๋ฃ๊ตฌ์กฐ 1: ์คํ(Stack)
2021.12.12์คํ (Stack) ์คํ์ LIFO(Last In First Out)์ ํน์ง์ ๊ฐ์ง๋ ์๋ฃ๊ตฌ์กฐ์
๋๋ค. ์คํ์ ์๋ฃ๋ฅผ ์ ์ฅํ ๋, ๋จผ์ ๋ฃ์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋ง์ง๋ง์ ๊บผ๋ด๊ฒ ๋ฉ๋๋ค. ์ค์ํํธ์ ๋ฐฐ์ด์ ์คํ๊ณผ ๋์ผํ append, removeLast ๋ฉ์๋๋ฅผ ์ง์ํ๊ธฐ ๋๋ฌธ์ ๋ฐฐ์ด์ ํ ๋ฒ ๊ฐ์ธ์ฃผ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ตฌํํ๋ฉด ์ฝ๊ฒ ๋ง๋ค ์ ์์ต๋๋ค. ๋ผ๋ ๋ง๋ค๊ธฐ struct Stack { var elements: [T] = [] var count : Int { return elements.count } var isEmpty : Bool { return elements.isEmpty } } ๋จผ์ , ์ ๋ค๋ฆญ์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ๋ด์ ์ ์๋ ๋ฐฐ์ด ํ๋๋ฅผ ๋ง๋ค์ด์ค๋๋ค. ์คํ์ ๋ด๊ธด ๋ฐ์ดํฐ์ ๊ฐ์์ ์คํ์ด ๋น์ด์๋์ง ์ฌ๋ถ๋ ์ค์ํํธ์..