2109028 ๊ฐœ๋ฐœ๊ธฐ๋ก: ์š”์ฆ˜ ๋Š๋ผ๋Š” ์ ๋“ค

2021. 9. 28. 23:08ใ†๐Ÿ“” TIL

BFS ์™€ DFS

์š”์ฆ˜ ์•„์นจ๋งˆ๋‹ค BFS/DFS ๋ฌธ์ œ๋ฅผ ํ•˜๋‚˜์”ฉ ํ’€๊ณ  ์žˆ๋‹ค. ์›Œ๋‚™ ๋ชปํ•˜๋Š” ์œ ํ˜•์ด๊ธฐ๋„ ํ•˜๊ณ , ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๋งˆ๋‹ค ๋งค๋ฒˆ ๋ง‰ํ˜€ ๊ฐœ์ธ์ ์œผ๋กœ ๋ฒฝ์ด๋ผ ๋Š๊ผˆ๋˜ ๋ฌธ์ œ์˜€๋‹ค. ๊ทธ๋Ÿฐ๋ฐ ์–ด์ œ, ์˜ค๋Š˜์€ ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค lv3 ๋ฌธ์ œ๋„ ํ•œ๋ฒˆ๋งŒ์— ํ’€๋ฆฌ๋Š”๊ฒŒ ์•„๋‹Œ๊ฐ€. ์ž ๊น์ด์ง€๋งŒ ๋น›์ด ๋ณด์˜€๋‹ค. ๊ทธ๋Ÿฌ๋ฉด์„œ BFS / DFS ์˜ ์ฐจ์ด,BFS: queue, DFS: stack ์„ ์ฒด๊ฐํ–ˆ๋‹ค.

BFS ๋Š” ์ž์‹ ๊ณผ ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ๋ฅผ ์šฐ์„ ์ ์œผ๋กœ ๋ชจ๋‘ ์ˆœํšŒํ•˜๋Š”๋ฐ, ์ด๋ฅผ queue ์— ๋‹ด๋Š”๋‹ค. stack ์—๋„ ๋‹ด์„ ์ˆ˜ ์žˆ์ง€ ์•Š๋ƒ๊ณ ? 

 

์ž๋ฐ”์Šคํฌ๋ฆฝํŠธ for ๋ฌธ

์ด๊ฑฐ ์ฒ˜์Œ ์•Œ์•˜๋‹ค. for () ๋‚ด๋ถ€์—์„œ in ๊ณผ of ์— ๋”ฐ๋ผ ์ฐจ์ด๊ฐ€ ๋ฐœ์ƒํ•˜๋Š”๋ฐ, in ์„ ์‚ฌ์šฉํ•˜๋ฉด ๋ฐฐ์—ด(List)์˜ ์ธ๋ฑ์Šค๋กœ ์ ‘๊ทผ, of ๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ๋ฐฐ์—ด์˜ ์›์†Œ์— ์ ‘๊ทผํ•œ๋‹ค.

// index์— ์ ‘๊ทผ
for (let i in List){
	...
    }

// element ์— ์ ‘๊ทผ
for (let i of List){
	...
    }

 

ํšŒ์‚ฌ

๋ฃจ๋‚˜ ์˜ค๋น— ์ปดํฌ๋„ŒํŠธ๊ฐ€ ํด๋ž˜์Šค ์ปดํฌ๋„ŒํŠธ๋ฅผ ๋ฒ ์ด์Šค๋กœ ๊ฐœ๋ฐœ๋๋‹ค ๋ณด๋‹ˆ, ํ•จ์ˆ˜ ์ปดํฌ๋„ŒํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์šฐ๋ฆฌ ๋ถ€์„œ์—์„  ๋ฐ”๋กœ ์‚ฌ์šฉํ•˜๊ธฐ ์‰ฝ์ง€ ์•Š์•˜๋‹ค. ์ง€์†์ ์œผ๋กœ ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•ด์„œ ๊ณจ๋จธ๋ฆฌ๋ฅผ ์•“์•˜๋Š”๋ฐ, ์˜† ๋™๋„ค ์—ฐ๊ตฌ์›๋ถ„์ด ์ฝ”๋“œ๋ฅผ ๊ณ„์† ๊นŒ๋ณธ๋‹ค๋”๋‹ˆ ์‹ค์ œ๋กœ ํ•ด๊ฒฐ์ฑ…์„ ๊ฐ€์ ธ์˜ค์…จ๋‹ค. ์ง€๊ธˆ๊นŒ์ง„ ๋‚˜ ํ˜ผ์ž ๋ฌด์–ธ๊ฐˆ ํ•ด๊ฒฐํ•ด์•ผํ•œ๋‹ค๋Š” ๋งˆ์Œ์— ๋ถ€๋‹ด๊ฐ์ด ์ปธ๋Š”๋ฐ, ๋ฏฟ์„๋งŒํ•œ ๋™๋ฃŒ๊ฐ€ ์ƒ๊ธด ๊ธฐ๋ถ„์ด ๋“ค์—ˆ๋‹ค. ์ด๊ฒŒ ์ƒ๊ฐ๋ณด๋‹ค ๋“ ๋“ ํ•ด์ง„๋‹ค. ์ตœ๊ณ ์˜ ๋ณต์ง€๋Š” ๋™๋ฃŒ๋ผ๋Š” ๋ง์ด ๊ดœํžˆ ๋‚˜์˜ค๋Š”๊ฒŒ ์•„๋‹Œ๊ฐ€๋ณด๋‹ค.