๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“š Computer Science20

[๋””์ž์ธ ํŒจํ„ด] ํŒฉํ† ๋ฆฌ ํŒจํ„ด (Factory Pattern) ํŒฉํ† ๋ฆฌ ๋ฉ”์„œ๋“œ ํŒจํ„ด (Factory Method Pattern) ๊ฐ์ฒด๋ฅผ ์ƒ์„ฑํ•˜๊ธฐ ์œ„ํ•œ ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ์ •์˜ํ•˜๋Š”๋ฐ, ์–ด๋–ค ํด๋ž˜์Šค์˜ ์ธ์Šคํ„ด์Šค๋ฅผ ๋งŒ๋“ค์ง€๋Š” ์„œ๋ธŒ ํด๋ž˜์Šค์—์„œ ๊ฒฐ์ •ํ•˜๊ฒŒ ๋งŒ๋“œ๋Š” ํŒจํ„ด ํด๋ž˜์Šค์˜ ์ธ์Šคํ„ด์Šค๋ฅผ ๋งŒ๋“œ๋Š” ์ผ์„ ์„œ๋ธŒํด๋ž˜์Šค์—๊ฒŒ ๋งก๊ธฐ๋Š” ๊ฒƒ ๋ถ€๋ชจ ์ถ”์ƒ ํด๋ž˜์Šค๋Š” ์ธํ„ฐํŽ˜์ด์Šค์—๋งŒ ์˜์กดํ•˜๊ณ  ์‹ค์ œ๋กœ ์–ด๋–ค ๊ตฌํ˜„ ํด๋ž˜์Šค๋ฅผ ํ˜ธ์ถœํ• ์ง€๋Š” ์„œ๋ธŒ ํด๋ž˜์Šค์—์„œ ๊ตฌํ˜„ ์ƒˆ๋กœ์šด ๊ตฌํ˜„ ํด๋ž˜์Šค๊ฐ€ ์ถ”๊ฐ€๋˜์–ด๋„ ๊ธฐ์กด Factory ์ฝ”๋“œ์˜ ์ˆ˜์ • ์—†์ด ์ƒˆ๋กœ์šด Factory๋ฅผ ์ถ”๊ฐ€ ๊ฐ€๋Šฅ ๊ฐ์ฒด์˜ ์ƒ์„ฑ์„ ๋‹ด๋‹นํ•˜๋Š” ํด๋ž˜์Šค๋ฅผ ํ•œ ๊ณณ์—์„œ ๊ด€๋ฆฌํ•˜์—ฌ ๊ฒฐํ•ฉ๋„๋ฅผ ์ค„์ด๊ธฐ ์œ„ํ•˜์—ฌ ํŒฉํ† ๋ฆฌ ํŒจํ„ด์ด ๋“ฑ์žฅ ๊ฒฐํ•ฉ๋„: ํ•œ ํด๋ž˜์Šค์— ๋ณ€๊ฒฝ์ ์ด ์–ผ๋งˆ๋‚˜ ๋‹ค๋ฅธ ํด๋ž˜์Šค์— ์˜ํ–ฅ์„ ์ฃผ๋Š”๊ฐ€๋ฅผ ์˜๋ฏธ ํŒฉํ† ๋ฆฌ ๋ฉ”์„œ๋“œ ํŒจํ„ด์˜ ์žฅ์  ๊ฐ์ฒด ๊ฐ„์˜ ๊ฒฐํ•ฉ๋„๋ฅผ ๋‚ฎ์ถœ ์ˆ˜ ์žˆ์Œ ๋‹จ์ผ ์ฑ…์ž„ ์›์น™์„ ๋”ฐ๋ฆ„ ํ”„๋กœ๊ทธ๋žจ์˜ ์ฝ”๋“œ.. 2023. 3. 17.
[๋””์ž์ธ ํŒจํ„ด] ์‹ฑ๊ธ€ํ†ค ํŒจํ„ด (Singleton Pattern) ์‹ฑ๊ธ€ํ†ค ํŒจํ„ด (Singleton Pattern) ํ•˜๋‚˜์˜ ํด๋ž˜์Šค์— ์˜ค์ง ํ•˜๋‚˜์˜ ์ธ์Šคํ„ด์Šค ๋งŒ ๊ฐ€์ง€๋Š” ํŒจํ„ด ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์—ฐ๊ฒฐ ๋ชจ๋“ˆ์— ๋งŽ์ด ์‚ฌ์šฉ ํ•˜๋‚˜์˜ ์ธ์Šคํ„ด์Šค๋ฅผ ๋งŒ๋“ค์–ด ๋†“๊ณ  ํ•ด๋‹น ์ธ์Šคํ„ด์Šค๋ฅผ ๋‹ค๋ฅธ ๋ชจ๋“ˆ๋“ค์ด ๊ณต์œ ํ•˜๋ฉฐ ์‚ฌ์šฉ ์ธ์Šคํ„ด์Šค ์ƒ์„ฑ ๋น„์šฉ์ด ์ค„์–ด๋“ฆ ๋™์‹œ์„ฑ(Concurrency) ๋ฌธ์ œ๋ฅผ ๊ณ ๋ คํ•ด์•ผ ํ•จ ์‹ฑ๊ธ€ํ†ค ํŒจํ„ด์„ ์‚ฌ์šฉํ•˜๋Š” ์ด์œ  ์ตœ์ดˆ ํ•œ ๋ฒˆ๋งŒ ์ธ์Šคํ„ด์Šค๋ฅผ ์ƒ์„ฑํ•˜์—ฌ ๊ณ ์ •๋œ ๋ฉ”๋ชจ๋ฆฌ ์˜์—ญ์„ ์‚ฌ์šฉํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„ ๋ฐฉ์ง€ ์ด๋ฏธ ์ƒ์„ฑ๋œ ์ธ์Šคํ„ด์Šค๋ฅผ ํ™œ์šฉํ•ด ์†๋„๊ฐ€ ๋น ๋ฆ„ ์‹ฑ๊ธ€ํ†ต ์ธ์Šคํ„ด์Šค๊ฐ€ ์ „์—ญ์œผ๋กœ ์‚ฌ์šฉ๋˜๊ธฐ ๋•Œ๋ฌธ์—, ๋‹ค๋ฅธ ํด๋ž˜์Šค ๊ฐ„์— ๋ฐ์ดํ„ฐ ๊ณต์œ ๊ฐ€ ์‰ฌ์›€ ์ธ์Šคํ„ด์Šค๊ฐ€ ์ ˆ๋Œ€์ ์œผ๋กœ ํ•œ ๊ฐœ๋งŒ ์กด์žฌํ•˜๋Š” ๊ฒƒ์„ ๋ณด์ฆํ•˜๊ณ  ์‹ถ์€ ๊ฒฝ์šฐ์— ์‚ฌ์šฉ ์‹ฑ๊ธ€ํ†ค ํŒจํ„ด์˜ ๋‹จ์  ์‹ฑ๊ธ€ํ†ค ์ธ์Šคํ„ด์Šค๊ฐ€ ํ˜ผ์ž ๋„ˆ๋ฌด ๋งŽ์€ ์ผ์„ ํ•˜๊ฑฐ๋‚˜, ๋งŽ์€ ๋ฐ์ดํ„ฐ๋ฅผ ๊ณต์œ ์‹œํ‚ฌ ๊ฒฝ์šฐ์— ๋‹ค๋ฅธ .. 2023. 3. 16.
[์ž๋ฃŒ๊ตฌ์กฐ] ํ•ด์‹œ ํ…Œ์ด๋ธ”(Hash Table) ํ•ด์‹œ ํ…Œ์ด๋ธ”(Hash Table) ํ•ด์‹œ ํ…Œ์ด๋ธ”์€ (Key, Value)์‹์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ํ•ด์‹œํ•จ์ˆ˜(Hash Function)๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋ณ€ํ™˜ํ•œ ๊ฐ’์„ index๋กœ ์‚ผ์Œ ํ•ด์‹œ ํ•จ์ˆ˜(Hash Function)๋ฅผ ์‚ฌ์šฉํ•ด Key ๊ฐ’์„ ์ƒ‰์ธ(index)์œผ๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๊ณผ์ •์„ ํ•ด์‹ฑ(Hashing)์ด๋ผ๊ณ  ํ•จ ๋Œ€ํ‘œ์ ์ธ ์˜ˆ๋กœ ํŒŒ์ด์ฌ์˜ dictionary, ๋ฃจ๋น„์˜ Hash, ์ž๋ฐ”์˜ Map ๋“ฑ์ด ์žˆ์Œ ํ•ด์‹œ ํ…Œ์ด๋ธ”์˜ ํŠน์ง• ๊ธฐ๋ณธ ์—ฐ์‚ฐ์œผ๋กœ๋Š” search, insert, delete๊ฐ€ ์žˆ์Œ ์ˆœ์ฐจ์ ์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜์ง€ ์•Š์Œ key๋ฅผ ํ†ตํ•ด์„œ value๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์Œ => ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ๋‚˜ ๋ฐฐ์—ด์— ๋น„ํ•ด ์†๋„๊ฐ€ ๋น ๋ฆ„ ์ปค๋‹ค๋ž€ ๋ฐ์ดํ„ฐ๋ฅผ ํ•ด์‹œํ•ด์„œ ์งง์€ ๊ธธ์ด๋กœ ์ถ•์•ฝํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ๋ฅผ ๋น„๊ตํ•  ๋•Œ ํšจ์œจ์  value๋Š” ์ค‘๋ณต ๊ฐ€๋Šฅํ•˜.. 2023. 3. 15.
[์ž๋ฃŒ๊ตฌ์กฐ] ์šฐ์„ ์ˆœ์œ„ ํ(Priority Queue) ์šฐ์„ ์ˆœ์œ„ ํ(Priority) ์ˆœ์„œ์— ์ƒ๊ด€์—†์ด ์šฐ์„ ์ˆ˜์œ„๊ฐ€ ๋†’์€ ๋ฐ์ดํ„ฐ๊ฐ€ ๋จผ์ € ๋‚˜๊ฐ€๋Š” ํ˜•ํƒœ์˜ ์ž๋ฃŒ๊ตฌ์กฐ ์šฐ์„ ์ˆœ์œ„ ๋Œ€๊ธฐ์—ด์ด๋ผ๊ณ ๋„ ํ•จ ๋Œ€๊ธฐ์—ด์—์„œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ์š”์†Œ๊ฐ€ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋‚ฎ์€ ์š”์†Œ๋ณด๋‹ค ๋จผ์ € ์ œ๊ณต๋˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ ์ผ๋ฐ˜์ ์œผ๋กœ ํž™(Heap)์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ตฌํ˜„ ๋ชจ๋“  ํ•ญ๋ชฉ์—๋Š” ์šฐ์„ ์ˆœ์œ„๊ฐ€ ์žˆ์Œ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ ์š”์†Œ๋Š” ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋‚ฎ์€ ์š”์†Œ๋ณด๋‹ค ๋จผ์ € ํ์—์„œ ์ œ์™ธ ๋‘ ์š”์†Œ์˜ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ™์€ ๊ฒฝ์šฐ ํ์˜ ์ˆœ์„œ์— ๋”ฐ๋ผ ์ œ๊ณต ์šฐ์„ ์ˆœ์œ„ ํ ๊ตฌํ˜„ ๋ฐฉ๋ฒ• ๋ฐฐ์—ด, ์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ, ํž™์„ ์ด์šฉํ•˜์—ฌ ๊ตฌํ˜„ ๊ฐ€๋Šฅ ๊ตฌํ˜„ ๋ฐฉ๋ฒ• ์‚ฝ์ž… (enqueue) ์‚ญ์ œ (denqueue) ๋ฐฐ์—ด (unsorted array) O(1) O(N) ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ (unsorted linked list) O(1) O(N) ์ •๋ ฌ๋œ ๋ฐฐ์—ด (sorted array) O(N) O(1) .. 2023. 3. 13.
[์ž๋ฃŒ๊ตฌ์กฐ] ํž™(Heap) ํž™(Heap) ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ ๊ธฐ๋ฐ˜์˜ ์ž๋ฃŒ๊ตฌ์กฐ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๊ฐ’๋“ค ์ค‘์—์„œ ์ตœ๋Œ“๊ฐ’์ด๋‚˜ ์ตœ์†Ÿ๊ฐ’์„ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„๋‚ด๋„๋ก ๋งŒ๋“ค์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์œ„ํ•ด ๋งŒ๋“ค์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ ๋ฐ˜์ •๋ ฌ์ƒํƒœ(๋А์Šจํ•œ ์ •๋ ฌ์ƒํƒœ) ์œ ์ง€ ํฐ ๊ฐ’์ด ์ƒ์œ„์— ์žˆ๊ณ  ์ž‘์€ ๊ฐ’์ด ํ•˜์œ„์— ์žˆ๋Š” ์ •๋„ ์ค‘๋ณต๋œ ๊ฐ’ ํ—ˆ์šฉ ํž™์˜ ์ข…๋ฅ˜ ์ตœ๋Œ€ ํž™(max heap) ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ์ž์‹๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์€ ์™„์ „ ์ด์ง„ํŠธ๋ฆฌ ์ตœ์†Œ ํž™(min heap) ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’์ด ์ž์‹ ๋…ธ๋“œ์˜ ํ‚ค ๊ฐ’ ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ด์ง„ํŠธ๋ฆฌ ํž™์˜ ํ™œ์šฉ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ์‹œ์Šคํ…œ ๋„คํŠธ์›Œํฌ ํŠธ๋ž˜ํ”ฝ ์ œ์–ด ์šด์˜ ์ฒด์ œ์—์„œ์˜ ์ž‘์—… ์Šค์ผ€์ฅด๋ง ์ˆ˜์น˜ ํ•ด์„์ ์ธ ๊ณ„์‚ฐ ํž™์˜ ๊ตฌํ˜„ ํž™์„ ์ €์žฅํ•˜๋Š” ํ‘œ์ค€์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ๋ฐฐ์—ด ๊ตฌํ˜„์„ ์‰ฝ๊ฒŒ ํ•˜๊ธฐ ์œ„ํ•ด ๋ฐฐ์—ด์˜ ์ฒซ ๋ฒˆ์งธ ์ธ๋ฑ์Šค์ธ 0์€ ์‚ฌ์šฉ๋˜์ง€ ์•Š์Œ ํŠน์ • ์œ„์น˜์˜ ๋…ธ๋“œ ๋ฒˆํ˜ธ๋Š” ์ƒˆ๋กœ์šด.. 2023. 3. 13.
[์ž๋ฃŒ๊ตฌ์กฐ] ํŠธ๋ฆฌ(Tree) ํŠธ๋ฆฌ(Tree) ๋…ธ๋“œ๋“ค์ด ๋‚˜๋ฌด ๊ฐ€์ง€์ฒ˜๋Ÿผ ์—ฐ๊ฒฐ๋œ ๋น„์„ ํ˜• ๊ณ„์ธต์  ์ž๋ฃŒ๊ตฌ์กฐ ๊ณ„์ธต์ ์ธ ์ž๋ฃŒ๋ฅผ ํ‘œํ˜„ํ•˜๋Š”๋ฐ ์ด์šฉ ๋…ธ๋“œ(node)๋“ค๊ณผ ๋…ธ๋“œ๋“ค์„ ์—ฐ๊ฒฐํ•˜๋Š” ๊ฐ„์„ (edge)๋“ค๋กœ ๊ตฌ์„ฑ ํ•˜๋‚˜์˜ ๋ฃจํŠธ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง ํŠธ๋ฆฌ์™€ ๊ด€๋ จ๋œ ์šฉ์–ด ๋…ธ๋“œ(node) ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๊ณ  ์žˆ๋Š” ๊ธฐ๋ณธ์š”์†Œ ๋…ธ๋“œ์—๋Š” ํ‚ค ๋˜๋Š” ๊ฐ’๊ณผ ํ•˜์œ„ ๋…ธ๋“œ์— ๋Œ€ํ•œ ํฌ์ธํ„ฐ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์Œ ๊ฐ„์„ (edge) ๋…ธ๋“œ์™€ ๋…ธ๋“œ ๊ฐ„์˜ ์—ฐ๊ฒฐ์„  (link, branch๋ผ๊ณ ๋„ ๋ถ€๋ฆ„) ๋ฃจํŠธ ๋…ธ๋“œ(root node) ๋ถ€๋ชจ๊ฐ€ ์—†๋Š” ์ตœ์ƒ์œ„ ๋…ธ๋“œ, ํŠธ๋ฆฌ๋Š” ํ•˜๋‚˜์˜ ๋ฃจํŠธ ๋…ธ๋“œ๋งŒ์„ ๊ฐ€์ง (A) ๋ถ€๋ชจ ๋…ธ๋“œ(parent node) ์ž์‹  ๋…ธ๋“œ๋ฅผ ๊ฐ€์ง„ ๋…ธ๋“œ (H, I์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋Š” D) ์ž์‹ ๋…ธ๋“œ(child node) ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ํ•˜์œ„ ๋…ธ๋“œ (๋…ธ๋“œ D์˜ ์ž์‹ ๋…ธ๋“œ๋Š” H, I) ํ˜•์ œ ๋…ธ๋“œ(sibling node) ๊ฐ™์€.. 2023. 3. 9.
๋ฐ˜์‘ํ˜•