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

๐Ÿ’พ Algorithm/- ์ž๋ฃŒ๊ตฌ์กฐ ์ด๋ก 16

[์ž๋ฃŒ๊ตฌ์กฐ] ๋…ธ๋“œ๋กœ ์ด๋ฃจ์–ด์ง„ ํŠธ๋ฆฌ ๊ตฌํ˜„ํ•˜๊ธฐ (By Java) ์˜ค๋Š˜์€ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํŠธ๋ฆฌ๋ฅผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋Œ€ํšŒ๋‚˜ ๋ฌธ์ œ์—์„œ ํ’€๊ธฐ ์‰ฝ๊ฒŒ ํ•œ ๋ฒˆ์— ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณผ ๊ฒƒ์ด๋‹ค. ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์ง€๋‚œ ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ(1)-๊ธฐ๋ณธ ํŠธ๋ฆฌ ์šฉ์–ด ๋ฐ ๊ฐœ๋… ํŒŒํŠธ์—์„œ ์„ค๋ช…ํ–ˆ์œผ๋ฏ€๋กœ ์ƒ๋žตํ•˜๊ณ  ๋ฐ”๋กœ ๊ตฌํ˜„์„ ํ•ด๋ณด๋„๋ก ํ•˜๊ฒ ๋‹ค. ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ•ต์‹ฌ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ์˜ ํ•ต์‹ฌ์€ ๋ฐ”๋กœ ๋…ธ๋“œ์ด๋‹ค. ์—ฌ๊ธฐ์„œ ๋…ธ๋“œ๋ž€ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ  ์žˆ๋Š” ํ•˜๋‚˜ ํ•˜๋‚˜์˜ ์›์†Œ์ธ ์…ˆ์ด๋‹ค. ๋…ธ๋“œ๋Š” ํฌ๊ฒŒ Data Field์™€ Link Field๋กœ ๋‚˜๋‰˜์–ด์ ธ ์žˆ๋‹ค. ์ €๊ธฐ ์œ„์—์„œ ๋ณด๋ฉด ๊ฐ๊ฐ์˜ ์ˆซ์ž์— ํ•ด๋‹นํ•˜๋Š” ๋ถ€๋ถ„์ด Data Field์ด๋ฉฐ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฐ„์„ ์€ Link Field์ด๋‹ค. ๊ทธ๋ ‡๋‹ค๋ฉด ์œ„์—์„œ ๋ง ํ–ˆ๋“ฏ์ด ๋…ธ๋“œ๋Š” Data Field์™€ Link Field๊ฐ€ ํ•ฉ์ณ์ง„ ๊ตฌ์กฐ์ด๋ฏ€๋กœ ์ด๋ฅผ ๊ทธ๋ฆผ์œผ๋กœ ๊ทธ๋ฆฐ๋‹ค๋ฉด ์•„๋ž˜์™€.. 2020. 9. 23.
[์ž๋ฃŒ ๊ตฌ์กฐ] Java๋กœ ๊ทธ๋ž˜ํ”„ ๊ตฌํ˜„ํ•˜๊ธฐ :: ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•œ ๊ทธ๋ž˜ํ”„ To Do ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ž€? ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ ์ง€๋‚œ ์‹œ๊ฐ„์— ์šฐ๋ฆฌ๋Š” ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ๊ฐ€์กŒ๋‹ค. ์˜ค๋Š˜์€ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆฌ๋Š” ๋˜ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์ธ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ ค๋ณด์ž. ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ Adjancency List ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋Š” ํ•œ ๋…ธ๋“œ์— ์—ฐ๊ฒฐ ์ƒํƒœ๋ฅผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•œ ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ์šฐ๋ฆฌ๊ฐ€ ์•„๊นŒ ์œ„์—์„œ ๋งŒ๋“ค์–ด ๋†จ๋˜ ์ž„์˜์˜ ๊ทธ๋ž˜ํ”„๋ฅผ ํ† ๋Œ€๋กœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ๋งŒ๋“ค์–ด๋ณด์ž. ๋…ธ๋“œ๊ฐ€ 6๊ฐœ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ด€๊ณ„๋ฅผ ์ฐพ์•„๋ณด์ž 1 -> 2 2 -> 1 - 3 - 4 3 -> 2 - 4 - 5 4 -> 3 - 5 - 6 5 -> 3 - 4 6 -> 4 ๊ด€๊ณ„๋ฅผ ์ฐพ์•˜์œผ๋‹ˆ ์ด์ œ ๊ฐ ๋…ธ๋“œ์— ํ•ด๋‹นํ•˜๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด๋ณด์ž. ์†Œ์Šค ์ฝ”๋“œ.. 2020. 7. 21.
[์ž๋ฃŒ ๊ตฌ์กฐ] Java๋กœ ๊ทธ๋ž˜ํ”„ ๊ตฌํ˜„ํ•˜๊ธฐ :: ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๊ตฌํ˜„ํ•œ ๊ทธ๋ž˜ํ”„ ์šฐ๋ฆฌ๋Š” ์ง€๋‚œ ์‹œ๊ฐ„์— ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด์„œ ํ•™์Šตํ•˜์˜€๋‹ค. ์ด๋ฒˆ์—๋Š” ์ด๋ก ์ ์ธ ๊ทธ๋ž˜ํ”„๋ฅผ ์ง์ ‘ Java๋ฅผ ์ด์šฉํ•˜์—ฌ ์ฝ”๋“œ๋กœ ์˜ฎ๊ฒจ ๋ณด๋Š” ํ•™์Šต์„ ํ•ด๋ณผ ์˜ˆ์ •์ด๋‹ค. ์ด์™€ ๊ฐ™์€ ๋…ธ๋“œ๋ฅผ ๊ฐ–๊ณ  ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๊ฐ€ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ด๋ณด์ž. ์ง€๋‚œ ๋ฒˆ์—๋„ ๋ง ํ–ˆ๋“ฏ์ด ๊ทธ๋ž˜ํ”„๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์—๋Š” ๋‘ ๊ฐ€์ง€๊ฐ€ ์žˆ๋‹ค. ์ธ์ ‘ ํ–‰๋ ฌ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ์˜ค๋Š˜์€ ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ตฌํ˜„ํ•ด๋ณผ ๊ฒƒ์ด๋‹ค. ์ธ์ ‘ ํ–‰๋ ฌ ์ธ์ ‘ ํ–‰๋ ฌ(adjacency matrix)์ด๋ž€ ์€ ๊ทธ๋ž˜ํ”„์—์„œ ์–ด๋Š ๊ผญ์ง“์ ๋“ค์ด ๋ณ€์œผ๋กœ ์—ฐ๊ฒฐ๋˜์—ˆ๋Š”์ง€ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์‚ฌ๊ฐ ํ–‰๋ ฌ์ด๋‹ค. ์ถœ์ฒ˜ : ์œ„ํ‚ค ๋ฐฑ๊ณผ ์œ„ํ‚ค ๋ฐฑ๊ณผ์—์„œ๋Š” ์ธ์ ‘ ํ–‰๋ ฌ์— ๋Œ€ํ•œ ์˜ˆ๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ฆผ์„ ๋ณด์—ฌ์ค€๋‹ค. ์ด ๊ทธ๋ฆผ์„ ๋ถ„์„ํ•ด๋ณด์ž๋ฉด 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ 6๋ฒˆ ๋…ธ๋“œ๊นŒ์ง€ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๋…ธ๋“œ์— 1์„ ๋„ฃ๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋Ÿผ ์•„๊นŒ ๊ทธ๋ ธ๋˜ ๊ทธ๋ž˜ํ”„๋ฅผ ํ•œ ๋ฒˆ ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ์˜ฎ๊ฒจ ๋ณด์ž. .. 2020. 7. 21.
[์ž๋ฃŒ ๊ตฌ์กฐ] ์ž๋ฐ”๋ฅผ ์ด์šฉํ•œ ํŠธ๋ฆฌ์˜ 3๊ฐ€์ง€ ์ˆœํšŒ ๋ฐฉ๋ฒ• ๊ตฌํ˜„ํ•˜๊ธฐ :: Tree Traversal (InOrder, PostOrder, PreOrder) ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ•™์Šตํ•˜๋Š” ๊ฐ€์žฅ ํฐ ์ด์œ ๋Š” ์ง€๋‚œ ์‹œ๊ฐ„์—์„œ ์„ค๋ช…ํ–ˆ๋“ฏ์ด ํƒ์ƒ‰์„ ํšจ์œจ์ ์œผ๋กœ ํ•˜๊ธฐ ์œ„ํ•จ ์ด๋ผ๊ณ  ํ–ˆ๋‹ค. ์ด๋Ÿฐ ํŠธ๋ฆฌ ํƒ์ƒ‰ํ•˜๋Š”๋ฐ์— ์กฐ๊ธˆ ๋” ํšจ์œจ์ ์ด๋ฉฐ ์ฒด๊ณ„์ ์ธ ๋ฐฉ๋ฒ•์ด ์žˆ๋Š”๋ฐ, ๊ทธ ๋Œ€ํ‘œ ์ฃผ์ž 3๊ฐ€์ง€๋ฅผ ์ด๋ฒˆ ์‹œ๊ฐ„์—๋Š” ์•Œ์•„๋ณด๊ณ  ๊ตฌํ˜„๊นŒ์ง€ ๋งˆ์ณ๋ณด๊ฒ ๋‹ค. InOrder PreOrder PostOrder ๋ ˆ๋ฒจ ์ˆœ์„œ ์ˆœํšŒ (์ด๋ฒˆ์—๋Š” ๋‹ค๋ฃจ์ง€ ์•Š์„ ๊ฒƒ์ด๋‹ค) ์ˆœํšŒ for(String name : names) { name.toString(); } ๋ฐฐ์—ด์„ ์ธ๋ฑ์Šค 0 ๋ถ€ํ„ฐ ๊ธธ์ด๋งŒํผ ๋ฐ˜๋ณตํ•˜๋Š” ๊ฒƒ์ด Iteration ์ด๋ผ๊ณ  ๋ถˆ๋ฆฌ๋Š” ์ˆœํšŒ๋ฅผ ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ˆœํšŒ๋ผ๊ณ  ํ•œ๋‹ค๋ฉด ์˜์–ด๋กœ๋Š” Circulation. ๋ฐ”๋กœ ์›์†Œ๋ฅผ ํ•˜๋‚˜ ํ•˜๋‚˜ ํ™•์ธํ•œ๋‹ค๋Š” ๋œป์ด๋‹ค. ์šฐ๋ฆฌ๋Š” ์‚ฌ์‹ค ๋งŽ์€ ๋ถ€๋ถ„์—์„œ ์ˆœํšŒ๋ฅผ ๊ฒฝํ—˜ํ•ด ์™”์—ˆ๋‹ค. ํ•˜์ง€๋งŒ ์•ž์œผ๋กœ ์šฐ๋ฆฌ๊ฐ€ ๋ฐฐ์šธ ์ˆœํšŒ์™€ ๋‹ค๋ฅธ ์ .. 2020. 7. 8.