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

๋ชฉ๋ก์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋… (4)

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ตฌํ˜„(Implementation) / ํ–‰๋ ฌ, ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ ์ ‘๊ทผ ๋ฐฉ๋ฒ•!

1. ๊ตฌํ˜„(Implementation) ์œ ํ˜•์˜ ๋ฌธ์ œ๋ž€?๊ตฌํ˜„ ์œ ํ˜•์˜ ๋ฌธ์ œ๋ž€ ํ’€์ด๋ฅผ ๋– ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ์€ ์‰ฝ์ง€๋งŒ ์†Œ์Šค์ฝ”๋“œ๋กœ ์˜ฎ๊ธฐ๊ธฐ ์–ด๋ ค์šด ๋ฌธ์ œ๋ฅผ ์ง€์นญํ•ฉ๋‹ˆ๋‹ค.์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ฐ„๋‹จํ•œ๋ฐ ์ฝ”๋“œ๊ฐ€ ์ง€๋‚˜์น  ๋งŒํผ ๊ธธ์–ด์ง€๋Š” ๋ฌธ์ œ์‹ค์ˆ˜ ์—ฐ์‚ฐ์„ ๋‹ค๋ฃจ๊ณ , ํŠน์ • ์†Œ์ˆ˜์  ์ž๋ฆฌ๊นŒ์ง€ ์ถœ๋ ฅํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ๋ฌธ์ž์—ด์„ ํŠน์ •ํ•œ ๊ธฐ์ค€์— ๋”ฐ๋ผ์„œ ๋Š์–ด ์ฒ˜๋ฆฌํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ ์ ˆํ•œ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ฐพ์•„์„œ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ ์ผ๋ฐ˜์ ์œผ๋กœ ๊ตฌํ˜„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์˜ 2์ฐจ์› ๊ณต๊ฐ„์€ ํ–‰๋ ฌ(Matrix)์˜ ์˜๋ฏธ๋กœ ์‚ฌ์šฉ๋˜๊ณ  ์ž์ฃผ ์ถœ์ œ๋ฉ๋‹ˆ๋‹ค.ํ–‰๋ ฌ์ด๋ž€ 2์ฐจ์› ๋ฐ์ดํ„ฐ๋ฅผ ์ผ์ข…์˜ ํ‘œ์™€ ๊ฐ™์€ ํ˜•ํƒœ๋กœ ์‰ฝ๊ฒŒ ๋‚˜ํƒ€๋‚ด๋Š” ์ˆ˜ํ•™ ๊ฐœ๋…์ž…๋‹ˆ๋‹ค. ์ฆ‰, ํŒŒ์ด์ฌ์—์„  2์ฐจ์› ๋ฐฐ์—ด์„ ๋งํ•ฉ๋‹ˆ๋‹ค.๋ณดํ†ต ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฐ ์™„์ „ ํƒ์ƒ‰ ๋ฌธ์ œ์—์„œ๋Š” 2์ฐจ์› ๊ณต๊ฐ„์—์„œ์˜ ๋ฐฉํ–ฅ๋ฒกํ„ฐ๊ฐ€ ์ž์ฃผ ํ™œ์šฉ๋ฉ๋‹ˆ๋‹ค.์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” ์–ด๋– ํ•œ ์บ๋ฆญํ„ฐ๋‚˜ ์‚ฌ..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ฆฌ๋””(Greedy) ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€

1. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์ด๋ž€?๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ์ง€๊ธˆ ๋‹น์žฅ ์ข‹์€ ๊ฒƒ๋งŒ ๊ณ ๋ฅด๋Š” ๋ฐฉ๋ฒ•์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.์‰ฝ๊ฒŒ ๋งํ•˜๋ฉด ํƒ์š•์Šค๋Ÿฝ๊ฒŒ ์ตœ๊ณ ์˜ ์„ ํƒ๋งŒ ์ทจํ•˜๋Š” ๊ฒƒ์„ ๋งํ•ฉ๋‹ˆ๋‹ค.์ผ๋ฐ˜์ ์ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ์ตœ์†Œํ•œ์˜ ์•„์ด๋””์–ด๋ฅผ ๋– ์˜ฌ๋ฆด ์ˆ˜ ์žˆ๋Š” ๋Šฅ๋ ฅ์„ ์š”๊ตฌํ•ฉ๋‹ˆ๋‹ค.๊ทธ๋ฆฌ๋”” ํ•ด๋ฒ•์€ ๊ทธ ์ •๋‹น์„ฑ ๋ถ„์„์ด ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.๋‹จ์ˆœํžˆ ๊ฐ€์žฅ ์ข‹์•„ ๋ณด์ด๋Š” ๊ฒƒ์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ์„ ํƒํ•ด๋„ ์ตœ์ ์˜ ํ•ด๋ฅผ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ฒ€ํ† ํ•ฉ๋‹ˆ๋‹ค.โœ”๏ธ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค.์ผ๋ฐ˜์ ์ธ ์ƒํ™ฉ์—์„œ ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•  ์ˆ˜ ์—†์„ ๋•Œ๊ฐ€ ๋งŽ์Šต๋‹ˆ๋‹ค.ํ•˜์ง€๋งŒ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ์˜ ๋Œ€๋ถ€๋ถ„์˜ ๊ทธ๋ฆฌ๋”” ๋ฌธ์ œ๋Š” ํƒ์š•๋ฒ•์œผ๋กœ ์–ป์€ ํ•ด๊ฐ€ ์ตœ์ ์˜ ํ•ด๊ฐ€ ๋˜๋Š” ์ƒํ™ฉ์—์„œ, ์ด๋ฅผ ์ถ”๋ก ํ•  ์ˆ˜ ์žˆ์–ด์•ผ ํ’€๋ฆฌ๋„๋ก ์ถœ์ œ๋ฉ๋‹ˆ๋‹ค. ํŠธ๋ฆฌ์—์„œ ๊ฒฝ๋กœ๋ฅผ ์ด๋™..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰(BFS)์ด๋ž€

1. ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ BFS ( Breadth-First Search )BFS๋Š” ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ, ๊ทธ๋ž˜ํ”„์—์„œ ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. BFS๋Š” ํ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค. ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•œ๋‹ค.ํ์—์„œ ๋…ธ๋“œ๋ฅผ ๊บผ๋‚ธ ๋’ค์— ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ธ์ ‘ ๋…ธ๋“œ ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ ํ•œ๋‹ค.๋” ์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค. 2. BFS ๋™์ž‘ ์˜ˆ์‹œ[Step 0] ๊ทธ๋ž˜ํ”„๋ฅผ ์ค€๋น„ (๋ฐฉ๋ฌธ๊ธฐ์ค€ : ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘๋…ธ๋“œ๋ถ€ํ„ฐ) / ์‹œ์ž‘๋…ธ๋“œ : 1[Step 1] ์‹œ์ž‘๋…ธ๋“œ ‘1’์„ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•ฉ๋‹ˆ๋‹ค.[Step 2] ํ์—์„œ ๋…ธ๋“œ ‘1’์„ ๊บผ๋‚ด ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘๋…ธ๋“œ ‘2’..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰(DFS)์ด๋ž€

1. ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS ( Depth - First Search) DFS๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ ๊ทธ๋ž˜ํ”„์—์„œ ๊นŠ์€ ๋ถ€๋ถ„์„ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. DFS๋Š” ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ ํ˜น์€ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค.์Šคํƒ์˜ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ์œผ๋ฉด ๊ทธ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ๋„ฃ๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์Šคํƒ์—์„œ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ๋ฅผ ๊บผ๋ƒ…๋‹ˆ๋‹ค.๋”์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. 2. DFS ๋™์ž‘ ์˜ˆ์‹œ (์˜ˆ์‹œ๋Š” ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘ ๋…ธ๋“œ ๋ถ€ํ„ฐ ๋ฐฉ๋ฌธ)[step 0] ๊ทธ๋ž˜ํ”„ ์ค€๋น„ (๋ฐฉ๋ฌธ ๊ธฐ์ค€ : ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘๋…ธ๋“œ๋ถ€ํ„ฐ) / ์‹œ์ž‘๋…ธ๋“œ : 1[step 1..