Computer Science/Algorithm

[Algorithm] ๊ทธ๋ž˜ํ”„ ์•Œ๊ณ ๋ฆฌ์ฆ˜(1) - ๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ ์šฉ์–ด

์ดํƒœํ™ 2022. 10. 4. 21:54

๐Ÿค” ๊ทธ๋ž˜ํ”„ ์•Œ๊ณ ๋ฆฌ์ฆ˜

๊ทธ๋ž˜ํ”„๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ธฐ๋ฒ•์ด๋ผ๊ธฐ ๋ณด๋‹ค๋Š” ์—ฌ๋Ÿฌ๊ฐ€์ง€ ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•˜๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

 

๊ทธ๋ž˜ํ”„๋Š” ์ •์ ๊ณผ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋œ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ๋œปํ•ฉ๋‹ˆ๋‹ค.

 

์ด๋ฒˆ ํฌ์ŠคํŒ…์—์„œ๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” ๋‹จ์–ด๋“ค์— ๋Œ€ํ•œ ๊ธฐ๋ณธ์šฉ์–ด๋ฅผ ์•Œ์•„๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

๐Ÿ”Ž ๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ ์šฉ์–ด

์ œ๊ฐ€ ๊ฐ€์žฅ ์งˆํˆฌํ•˜๋ฉด์„œ ์กด๊ฒฝํ•˜๋Š” ์นœ๊ตฌ์˜ ๋ธ”๋กœ๊ทธ์— ๋„ˆ๋ฌด ์ž˜ ์ •๋ฆฌ๋˜์–ด ์žˆ์–ด์„œ ํ•ด๋‹น ๋ธ”๋กœ๊ทธ๋ฅผ ์‚ดํŽด๋ณด๋Š” ๊ฒƒ์ด ๋„์›€์ด ๋  ๊ฒƒ์ž…๋‹ˆ๋‹ค.

 

๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ ์šฉ์–ด๋Š” ์ดํ•ด๋ณด๋‹ค ์•”๊ธฐ๊ฐ€ ํ•„์š”ํ•œ ๋ถ€๋ถ„์ด๊ธฐ๋•Œ๋ฌธ์— ํฌ์ŠคํŒ…์œผ๋กœ ๋„˜์–ด๊ฐ€๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

๐Ÿ”Ž ์ฐธ์กฐ

https://ttl-blog.tistory.com/954?category=964962 

 

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ž˜ํ”„ (1) - ๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ ์šฉ์–ด

๐Ÿง ๊ทธ๋ž˜ํ”„ (Graph) ๊ทธ๋ž˜ํ”„๋Š” ์ •์ (vertex)๋“ค๊ณผ ๊ฐ„์„ (edge)๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ๊ตฌ์กฐ๋กœ์จ, ๊ธฐํ˜ธ๋กœ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค. $$G = (V(G), E(G))$$ $V$ ๋Š” ์ •์ ์„, $E$ ๋Š” ๊ฐ„์„ ์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. ๐Ÿง Simple Graph Self loo..

ttl-blog.tistory.com