TIL 21.05.01

ffwangยท2021๋…„ 5์›” 1์ผ
0

TIL

๋ชฉ๋ก ๋ณด๊ธฐ
25/45

๐Ÿ“ŒToday I Learned

J2KB 5์ฃผ์ฐจ

  • ๋ผ์ดํŠธ๋‹ ํ† ํฌ์—์„œ ์žฅํ˜ธ๋™๋‹˜์˜ ๊ฐ•์—ฐ์„ ๋“ค์€ ๋’ค ๋ฏธํŒ…์ฃผ์ฐจ๋ฅผ ์ง„ํ–‰ํ–ˆ๋‹ค.
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‹œ๊ฐ„์— ๊ฐ ์กฐ๋งˆ๋‹ค ์ง„ํ–‰์ƒํ™ฉ์„ ๋ณด๊ณ ํ–ˆ๋Š”๋ฐ, ์ง€๋‚œ ํ•œ ์ฃผ๊ฐ€ ์‹œํ—˜๊ธฐ๊ฐ„์ด ๊ปด์žˆ์–ด์„œ ๊ทธ๋Ÿฐ์ง€ ์ƒ๊ฐ๋ณด๋‹ค BFS์™€ DFS๋ฅผ ๊ณต๋ถ€ํ•œ ํŒ€์ด ์ ์—ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์ด๊ฑธ ๋‹ค์‹œ ๊ณต๋ถ€ํ•ด์•ผํ•˜๋‚˜ ๋”ฐ๋กœํ•ด์•ผํ•˜๋‚˜ ๊ณ ๋ฏผํ•˜๋‹ค๊ฐ€ ๊ฒฐ๊ตญ ๋ชปํ•œ ๋ถ€๋ถ„์€ ๊ฐ์ž๊ฐ€ ๊ณต๋ถ€ํ•˜๊ธฐ๋กœ ํ•˜๊ณ  ์ด๋ฒˆ ์ฃผ๋Š” ์ƒˆ๋กœ ๊ณต๋ถ€ํ•˜๊ธฐ๋กœ ํ–ˆ๋‹ค.
    ์ด๋ฒˆ ์ฃผ์ œ๋Š” Queue, Stack, Trie ๋‹ค.
  • ๋ฆฌ์•กํŠธ ์‹œ๊ฐ„์—๋Š” ๊ฐ์ž ์ง€๋‚œ ํ•œ ์ฃผ๊ฐ„ ๊ณต๋ถ€ํ•œ ๋ถ€๋ถ„์„ ๋‚˜๋ˆ„์—ˆ๋‹ค. ๋‚˜๋Š” ๋ฆฌ์•กํŠธ ๊ฐ•์˜(ํด๋ก ์ฝ”๋”ฉ)๋ฅผ ์™„๊ฐ•ํ•˜๊ธฐ๋Š” ํ–ˆ์ง€๋งŒ ์•„์ง ๋‹ค ์ดํ•ดํ•˜์ง€๋Š” ๋ชปํ•ด์„œ ์ถ”๊ฐ€์ ์œผ๋กœ ๊ณต๋ถ€๊ฐ€ ํ•„์š”ํ•˜๋‹ค๊ณ  ๋งํ–ˆ๋‹ค. ๋‹ค๋ฅธ ๋ถ„๋“ค์ด ๋ฆฌ์•กํŠธ๋ฅผ ๋ญ๋ผ๊ณ  ์„ค๋ช…ํ•ด ์ฃผ์…จ๋Š”๋ฐ ๋‚˜๋Š” ์•Œ์•„๋“ฃ์ง€ ๋ชปํ–ˆ๋‹ค.
    ๋‚˜๋„ ๋” ๊ณต๋ถ€ํ•˜๋ฉด ์ €๋ ‡๊ฒŒ ์ž˜ ํ•  ์ˆ˜ ์žˆ์„๊นŒ? ๋ฌผ๋ก  ๋งŽ์ด ๊ณต๋ถ€ํ•˜๋ฉด ์ž˜ ํ•˜๊ฒŒ ๋  ๊ฒƒ์„ ์•ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ž๋ฐ”๋งŒ ์ฃผ๋กœ ์‚ฌ์šฉํ•˜๋Š” ๋‚ด ์ž…์žฅ์—์„œ๋Š” ๋ฆฌ์•กํŠธ๋ฅผ ์‹ฌํ™”ํ•˜์—ฌ ๊ณต๋ถ€ํ•˜๋Š” ๊ฒƒ์ด ์˜ณ์€ ์ผ์ธ์ง€๋Š” ๊ณ ๋ฏผ์ด ๋งŽ์ด ๋œ๋‹ค. ๋ฆฌ์•กํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋ ค๋ฉด JS๋„ ๋Šฅ์ˆ™ํ•ด์•ผํ•˜๊ณ  ๊ฑฐ๊ธฐ์— ๋ฆฌ์•กํŠธ๊นŒ์ง€ ์ž˜ ์•Œ์•„์•ผ ํ•œ๋‹ค. ๋‘˜ ๋‹ค ๋‚ฏ์„  ๋‚ด๊ฒŒ ๋ชจ๋‘๊ฐ€ ์ต์ˆ™ํ•ด์ง€๋ ค๋ฉด ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆด ๊ฒƒ ๊ฐ™๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ผ๋‹จ ๋‚ด๊ฐ€ ์ฆ๊ฑฐ์šด์ง€๋ฅผ ๋ชจ๋ฅด๊ฒ ๋‹ค. ์ด๋ฒˆ ์ฃผ์— ์ฒœ์ฒœํžˆ ๋ณต์Šตํ•ด๋ณด๋ฉด์„œ ์ •๋ง ๋ฆฌ์•กํŠธ๋ฅผ ๊ณต๋ถ€ํ•˜๋Š” ๊ฒƒ์ด ๋งž๋Š”์ง€, ๋˜ ๋‚˜์™€ ๋งž๋Š”์ง€ ์•Œ์•„๋ด์•ผ๊ฒ ๋‹ค.

์•Œ๊ณ ๋ฆฌ์ฆ˜

์ฝ”๋“œ์—…์—์„œ C์–ธ์–ด ๊ธฐ์ดˆ 100์ œ๋ฅผ ์ž๋ฐ”๋กœ ํ’€์—ˆ๋‹ค. 1012๋ฒˆ๋ถ€ํ„ฐ 1034๋ฒˆ๊นŒ์ง€ ํ’€์—ˆ๋‹ค. ์˜ค๋Š˜๋„ ๋ชจ๋“  ๋ฌธ์ œ๋ฅผ ํ•œ๋ฒˆ์— ํ†ต๊ณผํ•˜์ง€๋Š” ๋ชปํ–ˆ๋‹ค. ์ฝ”๋“œ์—…์—์„œ ์ฝ”๋“œ๋ฅผ ์ž…๋ ฅํ•˜๊ณ  ์‹คํ–‰์‹œ์ผฐ์„ ๋•Œ ์•Œ ์ˆ˜ ์—†๋Š” ์˜ค๋ฅ˜๊ฐ€ ๊ณ„์† ๋‚˜์„œ ๋ฐ”๋กœ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ•˜๊ธฐ๋„ ํ–ˆ๋‹ค. ๊ทธ๋ž˜๋„ ์‹œ๊ฐ„์ด ์ง€๋‚˜์„œ ๋‹ค์‹œ ํ’€์–ด๋ณด๋‹ˆ ํ•ด๊ฒฐ์€ ๋˜์—ˆ๋‹ค. ์ด๋ฒˆ์—๋„ ๊ธฐ์ดˆ๋ฅผ ํ’€๋ฉด์„œ ์‚ฌ์†Œํ•ด์„œ ๋†“์ณค๋˜ ๋ถ€๋ถ„์„ ์•Œ ์ˆ˜ ์žˆ์–ด์„œ ์ข‹์•˜๋‹ค.

.์€ \\.์œผ๋กœ ์‚ฌ์šฉํ•˜๊ธฐ, 10์ง„์ˆ˜์—์„œ 8, 16์ง„์ˆ˜๋กœ ๋ฐ”๊พธ๋Š” ๋ฒ•, ๊ทธ ๋ฐ˜๋Œ€ ...

๋…์„œ

์ƒˆ๋กœ ๊ตฌ๋…ํ•œ ๋ฐ€๋ฆฌ์˜ ์„œ์žฌ๋ฅผ ์‚ดํŽด๋ณด๋‹ค๊ฐ€

  • ์ง‘์ฃผ์ธ ํ• ๋จธ๋‹ˆ์™€ ๋‚˜ - ์•ผ๋ฒ  ํƒ€๋กœ(์ง€์€์ด), ์–‘์œค์˜ฅ(์˜ฎ๊ธด์ด)

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

profile
์ฐจ๊ทผ์ฐจ๊ทผ ํ•˜๋‚˜์”ฉ

0๊ฐœ์˜ ๋Œ“๊ธ€