์•Œ๊ณ ๋ฆฌ์ฆ˜

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

6. Union Find(ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) : MST - 1

Union Find (ํ•ฉ์ง‘ํ•ฉ ์ฐพ๊ธฐ) MST - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. MST ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€๋˜ ๋„์ค‘ ์ƒ๊ฐ๋‚˜์„œ ํฌ์ŠคํŒ… ํ•˜๊ฒŒ ๋๋‹ค. ๋งค์ฃผ ์ฃผ๋ง๋งˆ๋‹ค ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… ์ •๋ฆฌ๋ฅผ ํ•˜๋ ค๊ณ  ํ•˜๋Š”๋ฐ ๊ณ„์† ์‹คํŒจํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค... ใ…Žใ…Ž;; ์˜ค๋Š˜ ๋‹ค๋ค„๋ณผ ์ฃผ์ œ๋Š” MST, ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๊ธฐ๋ณธ ๋ฒ ์ด์Šค์ธ Union Find์ด๋‹ค. ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ ๋ฐฉ๋ฒ•์—๋Š” ๋Œ€ํ‘œ์ ์œผ๋กœ ํฌ๋ฃจ์Šค์นผ(Kruskal)๊ณผ ํ”„๋ฆผ(Prim) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค. Union FInd๋Š” ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•ต์‹ฌ์ด๋ผ๊ณ  ๋งํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿผ Union Find๊ฐ€ ๋ฌด์—‡์ธ์ง€ ์•Œ์•„๋ณด์ž. Union Find๋Š” ๋ง ๊ทธ๋Œ€๋กœ Union, ์ง‘ํ•ฉ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ทธ๋ž˜ํ”„ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด๋“ค ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ์•Œ์•„๋ณผ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ ์˜ˆ์‹œ..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

3. Dijsktra(๋‹ค์ต์ŠคํŠธ๋ผ) : ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 1

Dijsktra (๋‹ค์ต์ŠคํŠธ๋ผ) ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ - 1 ์ •๋ง ์˜ค๋žœ๋งŒ์— ํฌ์ŠคํŒ…์ด๋‹ค. ์›๋ž˜ ๋ชฉํ‘œ๋Œ€๋กœ ์ง„ํ–‰ํ–ˆ์œผ๋ฉด ๊ฐœ๊ฐ•์„ ํ•˜๊ธฐ ์ „์— DP๊นŒ์ง€ ํฌ์ŠคํŒ…์„ ํ–ˆ์–ด์•ผํ•˜๋Š”๋ฐ ์š”์ƒˆ ์กฐ๊ธˆ ๋ฐ”๋นด๋‹ค...(์‚ฌ์‹ค ์˜์š•์ด ์—†๋˜๊ฑธ ์ˆ˜๋„...) ์•„๋ฌดํŠผ ์ด๋ฒˆ 3-1 ๊ณผ๋ชฉ์— ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‘์šฉ์ด๋ผ๋Š” ๊ณผ๋ชฉ์„ ์ˆ˜๊ฐ•ํ•˜๋Š”๋ฐ ์ž‘๋…„์—๋Š” ๋”ฅ๋Ÿฌ๋‹๊ณผ ๊ด€๋ จํ•˜์—ฌ ์ˆ˜์—…ํ–ˆ๋‹ค๊ณ ํ•ด์„œ ์‹ ์ฒญํ–ˆ๋Š”๋ฐ ์ด๋ฒˆ์— ๊ต์ˆ˜๋‹˜์ด ๋ฐ”๋€Œ๋ฉด์„œ ์ •๋ง ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ํ•™์Šตํ•˜๋Š” ์ˆ˜์—…์ด ๋˜์–ด๋ฒ„๋ ธ๋‹ค. ์‚ด์ง ์•„์‰ฌ์› ์ง€๋งŒ ๊ฐ•์˜๊ณ„ํš์„œ๋ฅผ ๋ณด๋‹ˆ 2-2 ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…๊ณผ ๊ฑฐ์˜ ๋น„์Šทํ•ด์„œ? ํ•™๊ธฐ ์ดˆ์— ๋ฏธ๋ฆฌ๋ฏธ๋ฆฌ ์ •๋ฆฌํ•ด๋‘๋ ค๊ณ  ํ•œ๋‹ค. ์„œ๋ก ์ด ๊ธธ์—ˆ๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํƒ์ƒ‰ํ•ด๋ณด์ž. graph ๋ณ€์ˆ˜์— ์—ฐ๊ฒฐ๋œ ์ •์ ๊ณผ ๊ฐ€์ค‘์น˜๊ฐ€ ์ €์žฅ๋˜์–ด ์žˆ๋‹ค๊ณ  ๋ณธ๋‹ค. graph[1] = [2..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

2. DFS(Depth-Find-Search) : ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰

DFS(Depth-Find-Search) ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์ง€๋‚œ ์‹œ๊ฐ„ BFS์— ์ด์–ด ์˜ค๋Š˜์€ DFS์— ๋Œ€ํ•ด ์•Œ์•„๋ณด๋ ค๊ณ  ํ•œ๋‹ค. DFS๋Š” Depth-Find-Search๋กœ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋‹ค. BFS์™€ ๋‹ค๋ฅด๊ฒŒ DFS๋Š” ๊นŠ์ด๋ฅผ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•œ๋‹ค. ์ฆ‰ ์ตœ๋Œ€ ๊นŠ์ด๊นŒ์ง€ ์žฌ๊ท€์ ์œผ๋กœ ์ด๋™ํ•œ ํ›„ ์ตœ๋Œ€ ๊นŠ์ด์— ๋„๋‹ฌํ•œ ๊ฒฝ์šฐ ์˜†์œผ๋กœ ์ด๋™ํ•œ๋‹ค. ๋˜ํ•œ BFS์—์„œ๋Š” Queue๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค๋ฉด DFS์—์„œ๋Š” Stack์„ ์‚ฌ์šฉํ•œ๋‹ค. ์ด Stack์— ์ €์žฅ๋œ ๊ฐ’์ด ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” DFS์˜ ํƒ์ƒ‰ ์ˆœ์„œ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘ ๋ฐฉ์‹ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. 1. ํŠน์ • ์ •์ ์ด ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ธ ๊ฒฝ์šฐ ์ด๋ฅผ ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ ํ•ด์ค€๋‹ค. 2. ํ•ด๋‹น ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋œ ๋‹ค๋ฅธ ์ •์ ์— ๋Œ€ํ•ด ์œ„ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ DFS๋ฅผ ์ ์šฉํ•ด๋ณด์ž. โ‘  ์‹œ์ž‘ ์ •์ ์„ 8..

โœ๏ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Graph

1. BFS(Breath-Find-Search) : ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰

BFS(Breath-Find-Search) ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ๊ทธ๋ž˜ํ”„์˜ ํƒ์ƒ‰ ๋ฐฉ๋ฒ• ์ค‘ ํ•˜๋‚˜์˜ BFS์— ๋Œ€ํ•ด์„œ ์‚ดํŽด๋ณด๋ ค๊ณ  ํ•œ๋‹ค. BFS๋Š” ๋ง ๊ทธ๋Œ€๋กœ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, ์ฆ‰ ํŠน์ • Vertice์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด Vertice๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•œ๋‹ค๋Š” ๋œป์ด๋‹ค. ์šฐ์„  BFS๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” Queue๊ฐ€ ํ•„์š”ํ•˜๋‹ค. Stack, Queue, Heap์— ๋Œ€ํ•ด์„œ๋Š” ๋‚˜์ค‘์— ์ž์„ธํžˆ ์„ค๋ช…ํ•˜๊ธฐ๋กœ ํ•˜๊ณ  Queue์— ๋Œ€ํ•ด ๊ฐ„๋‹จํ•˜๊ฒŒ ์„ค๋ช…ํ•˜์ž๋ฉด FIFO(First in First out - ์„ ์ž…์„ ์ถœ)์œผ๋กœ ๋™์ž‘ํ•˜๋Š” ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์œ„์—์„œ๋„ ๋งํ–ˆ๋“ฏ์ด BFS์˜ ๊ฐ€์žฅ ํฐ ๊ฐœ๋…์€ ๊ฐ€๊นŒ์šด ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋˜, ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ธ ๊ฒฝ์šฐ ๋ฐฉ๋ฌธ ๋ฆฌ์ŠคํŠธ์— ์ •์ ์„ ์ €์žฅํ•˜๋ฉด ๋œ๋‹ค. ์ด ๋ฐฉ๋ฌธ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์šฐ๋ฆฌ๊ฐ€ ์›ํ•˜๋Š” ์ตœ์ข…์ ์ธ BFS์˜ ํƒ์ƒ‰ ์ˆœ์„œ์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋™์ž‘ ๋ฐฉ์‹..

kodo_o
'์•Œ๊ณ ๋ฆฌ์ฆ˜' ํƒœ๊ทธ์˜ ๊ธ€ ๋ชฉ๋ก