๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์ž๋ฃŒ๊ตฌ์กฐ (2)

kingsubin

์ž๋ฃŒ๊ตฌ์กฐ ์ •๋ฆฌ

์ „์ฒด์ ์œผ๋กœ ํฌ๊ฒŒ ๋‚˜๋ˆ„์ž๋ฉด ๋‹จ์ˆœ๊ตฌ์กฐ, ์„ ํ˜•๊ตฌ์กฐ, ๋น„์„ ํ˜• ๊ตฌ์กฐ๋กœ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋‹จ์ˆœ๊ตฌ์กฐ๋Š” ๊ธฐ๋ณธํ˜• ํƒ€์ž…์˜ ๊ตฌ์กฐ๋ฅผ ๋งํ•˜๋ฉฐ ์ •์ˆ˜, ์‹ค์ˆ˜, ๋ฌธ์ž, Boolean ํƒ€์ž…์ด ์žˆ๋‹ค. ๊ธฐ๋ณธํ˜• ํƒ€์ž…์„ ์ œ์™ธํ•˜๋ฉด ์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์™€ ๋น„์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๊ฐ€ ์žˆ๋Š”๋ฐ ์–ด๋–ค ์ ์ด ๋‹ค๋ฅผ๊นŒ ? ์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์™€ ๋น„์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ์˜ ์ฐจ์ด ์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ - ๋ฐ์ดํ„ฐ ์š”์†Œ๊ฐ€ ์ด์ „ ๋ฐ ๋‹ค์Œ ์ธ์ ‘ ์š”์†Œ์— ์—ฐ๊ฒฐ๋˜์–ด์žˆ์œผ๋ฉฐ ์ˆœ์ฐจ์ ์œผ๋กœ ๋˜๋Š” ์„ ํ˜•์œผ๋กœ ๋ฐฐ์—ด๋˜๋Š” ๊ตฌ์กฐ - ๋‹จ์ผ ์‹คํ–‰์„ ๋ชจ๋“  ์š”์†Œ๋ฅผ ํšก๋‹จํ•  ์ˆ˜ ์žˆ๋‹ค. - ๊ตฌํ˜„ํ•˜๊ธฐ ์‰ฝ๋‹ค. - ์˜ˆ๋กœ๋Š” Array, Stack, Queue, LinkedList ๊ฐ€ ์žˆ๋‹ค. ๋น„์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ - ๋ฐ˜๋Œ€๋กœ ๋ฐ์ดํ„ฐ ์š”์†Œ๊ฐ€ ์ˆœ์ฐจ์ ์œผ๋กœ ๋˜๋Š” ์„ ํ˜•์œผ๋กœ ๋ฐฐ์—ด๋˜์ง€ ์•Š์€ ๊ตฌ์กฐ๋ฅผ ๋น„์„ ํ˜• ๋ฐ์ดํ„ฐ ๊ตฌ์กฐ๋ผ๊ณ  ํ•œ๋‹ค. - ๋‹จ์ผ ์‹คํ–‰์œผ๋กœ ๋ชจ๋“  ์š”..

Algorithm 2021. 1. 26. 22:55
ํŠธ๋ฆฌ ์ •๋ฆฌ

ํŠธ๋ฆฌ (tree) ์ž๋ฃŒ๊ตฌ์กฐ์˜ ์ผ์ข… ์‚ฌ์ดํด์ด ์—†๋Š” ์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„ ์ •์ ์˜ ๊ฐœ์ˆ˜ : V ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ : V-1 ์ •์  V, ๊ฐ„์„  V ๊ฐœ ๋ผ๋ฉด ์‚ฌ์ดํด์ด 1๊ฐœ ์žˆ๋‹ค. ์ •์  V, ๊ฐ„์„  V-1 ๊ฐœ๋ผ๋ฉด ํŠธ๋ฆฌ๋ผ ํ•  ์ˆ˜ ์žˆ์„๊นŒ ? ์•„๋‹ˆ๋‹ค. ์™œ๋ƒ๋ฉด ์—ฐ๊ฒฐ์ด ๋˜์–ด์žˆ์ง€ ์•Š๋‹ค. ์ •์  V, ๊ฐ„์„  V-1 ๊ฐœ ๋ผ๋Š”๊ฒƒ์€ ํŠธ๋ฆฌ์˜ ์„ฑ์งˆ์ด๋‹ค. ํŠธ๋ฆฌ๊ฐ€ ๋งž์„๋ ค๋ฉด ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋‹ค๋Š” ์กฐ๊ฑด์ด ์ถ”๊ฐ€๋˜์–ด์•ผ ํ•œ๋‹ค. ํŠธ๋ฆฌ๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ์š”์†Œ - node - edge root - ํŠธ๋ฆฌ์˜ ๊ฐ€์žฅ ์œ—๋ถ€๋ถ„์— ์œ„์น˜ํ•˜๋Š” ๋…ธ๋“œ - ํ•˜๋‚˜์˜ ํŠธ๋ฆฌ์—๋Š” ํ•˜๋‚˜์˜ ๋ฃจํŠธ๊ฐ€ ์กด์žฌ reaf (terminal node, external node) - ํŠธ๋ฆฌ์˜ ๊ฐ€์žฅ ์•„๋žซ๋ถ€๋ถ„์— ์œ„์น˜ํ•˜๋Š” ๋…ธ๋“œ - ๋” ์ด์ƒ ๋ป—์–ด๋‚˜๊ฐˆ ์ˆ˜ ์—†๋Š” ๋งˆ์ง€๋ง‰ ๋…ธ๋“œ Parent - Parent๊ฐ€ ์—†๋Š” V๋ฅผ Root๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. Ch..

Algorithm 2020. 9. 7. 16:58