Java 4

์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” Recap (DP &Dijkstra)

๐Ÿ“Recap Day: ์ด๋ฒˆ์ฃผ๋Š” ์ง€๊ธˆ๊นŒ์ง€ ์ง„ํ–‰ํ–ˆ๋˜ ์ฃผ์ œ์˜ ๋ฌธ์ œ ์ค‘์—์„œ ๋ชป ํ‘ผ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ณ  ๊ณต์œ !1๏ธโƒฃ DP & DnC์ ํ™”์‹์ด ํ•„์š”ํ•œ ๋ฌธ์ œ๋Š” DP ํ˜น์€ DnC?!?์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ณต๋ถ€ํ•˜๊ณ  ๊ณ„์† ์ ํ™”์‹์„ ๋ณด๋ฉด DP ํ˜น์€ DnC๋ฅผ ๋– ์˜ฌ๋ ธ๋Š”๋ฐ,,๋‹จ๋ฐฉํ–ฅ์œผ๋กœ ํ˜๋Ÿฌ๊ฐˆ ๋•Œ ๋ถ„ํ•  ์ •๋ณต,์ž‘์€ ๊ฐ’์„ ๊ตฌํ•ด ํฐ ๊ฐ’์— ์‚ฌ์šฉํ•ด์•ผ ํ•  ๋•Œ DP๋ฅผ ํ”ํžˆ ์‚ฌ์šฉํ•œ๋‹ค๊ณ  ์ƒ๊ฐ ↑ ์ด ๋ง์„ ๋“ค์œผ๋‹ˆ,, ํ‹€๋ ธ์„์ง€๋„ ๋ชจ๋ฅธ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์–ด๋”ฐ.. ๊ทธ๋ž˜์„œ GPTํ•œํ…Œ ๋ฌผ์–ด๋ด„DP์™€ DnC ์œ ํ˜•์„ ๊ตฌ๋ถ„ํ•˜๋Š” ๊ธฐ์ค€์„ ์„ธ์šฐ์ž๋ฉด ์ ํ™”์‹์ธ๊ฐ€?!? ๋ณด๋‹ค๋Š” ๋ถ€๋ถ„ ๋ฌธ์ œ๊ฐ€ ์„œ๋กœ ๋…๋ฆฝ์ ์ธ๊ฐ€!? ๊ฐ€ ๋” ์ž˜ ๋งž๋Š”๋‹ค๊ณ  ํ•จ..DP๋Š” ๋ถ€๋ถ„ ๋ฌธ์ œ๊ฐ€ ์ค‘๋ณต๋˜์–ด์„œ ๊ฐ™์€ ์—ฐ์‚ฐ์„ ๋ฐ˜๋ณต์ ์œผ๋กœ ํ•ด์•ผํ•˜๋Š” ๊ฒฝ์šฐ์— ๋” ์ ํ•ฉํ•˜๊ณ  DnC๋Š” ๋ถ€๋ถ„ ๋ฌธ์ œ๊ฐ€ ๋…๋ฆฝ์ ์ผ ๋•Œ ๋” ์ ํ•ฉํ•˜๋‹ค๊ณ  ํ•จDP(Top-Down) vs D..

Java ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” DnC & Hashing

์ด๋ฒˆ์ฃผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” ์ฃผ์ œ๋Š” DnC & Hashing๋‹คDnC๋Š” ํฐ ์–ด๋ ค์›€ ์—†์ด ํ’€์—ˆ๋Š”๋ฐ Hashing์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๋ฅผ ์žก๊ธฐ๊ฐ€ ์ •๋ง ํž˜๋“ค์—ˆ๋‹ค....ใ… ์•”ํŠผ ์ด๋ฒˆ์ฃผ ๋ฌธ์ œ์ง‘์€ ์•„๋ž˜์™€ ๊ฐ™๋‹ค.์ด๋ฒˆ์ฃผ ์œ ํ˜•์€ ๊ฐœ๋…์€ ์ž˜ ๋ชจ๋ฅด๊ฑฐ๋‚˜ ์•Œ๊ณ  ์žˆ๋Š”๋ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€์ด์— ์ ์šฉํ•˜๋ ค๊ณ  ํ•˜๋‹ˆ ์—ฐ๊ฒฐ์ด ์ž˜ ๋˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๊ฐ€ ์žˆ์–ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์ „์— ๊ฐœ๋…์„ ํ•œ ๋ฒˆ ์ •๋ฆฌํ•˜๊ณ  ๋ฌธ์ œ๋ฅผ ํ’€์—ˆ๋‹ค....๐ŸŽฏ ๊ฐ„๋‹จ ๊ฐœ๋… ์ •๋ฆฌ๊ฐœ๋…์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ์™€ ์—ฐ๊ฒฐ๋˜์ง€ ์•Š์•„์„œ ์ด๋ฒˆ์ฃผ๋Š” ํ’€๊ธฐ ์ „์— ๊ฐ„๋‹จํžˆ(?) ์ •๋ฆฌํ•จ!โœ… ๋ถ„ํ•  ์ •๋ณต: Divide - Conquer - CombineDivide : ์›๋ž˜ ๋ฌธ์ œ๋ฅผ ๋น„์Šทํ•œ ์œ ํ˜•์˜ ๋” ์ž‘์€ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ”Conquer : ํ•˜์œ„ ๋ฌธ์ œ๋ฅผ ์žฌ๊ท€์ ์œผ๋กœ ํ•ด๊ฒฐCombine : ํ•ด๊ฒฐํ•œ ๋ฌธ์ œ๋ฅผ ํ•ฉ์นจ⇒ ์–ด๋–ค ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ํ•˜์œ„ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ..

Java ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” DP & Heap

์ด๋ฒˆ์ฃผ ์ž๋ฐ” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” ์ฃผ์ œ๋Š” DP & Heap์ด๋‹ค!ํ•ญ์ƒ DP ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ฒŒ ์–ด๋ ต๊ฒŒ ๋А๊ปด์กŒ์—ˆ๋Š”๋ฐ..ใ…  ๊ฐ์˜ค๋Š” ํ–ˆ์ง€๋งŒ ๋ฌธ์ œ ํ‘ธ๋Š” ๊ฒŒ ์ƒ๋‹นํžˆ.. ํž˜๋“ค์—ˆ๋‹ค..!DP๋ฅผ ํ’€ ๋•Œ์— ์–ด๋–ป๊ฒŒ ์ ‘๊ทผํ–ˆ๋Š”์ง€, ์™œ ๊ทธ๋ ‡๊ฒŒ ํ’€์—ˆ๋Š”์ง€๋ฅผ ๊ณต์œ ํ•˜๋ฉด ์•ž์œผ๋กœ DPํ‘ธ๋Š”๋ฐ ๋„์›€์ด ๋  ๊ฒƒ ๊ฐ™์•„ ์Šคํ„ฐ๋”” ๋‚ ์ด ๊ธฐ๋‹ค๋ ค์กŒ๋‹ค.DP & Heap์ด๋ฒˆ์ฃผ ๋ฌธ์ œ์ง‘์—๋Š” ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ, ์šฐ์„ ์ˆœ์œ„ ํ, ๋ฐฐ๋‚ญ ๋ฌธ์ œ, ํ•ด์‹œ๋ฅผ ์‚ฌ์šฉํ•œ ์ง‘ํ•ฉ๊ณผ ๋งต ์œ ํ˜•์˜ ๋ฌธ์ œ๋“ค์ด ์žˆ์—ˆ๋‹ค. ์˜ค๋Š˜๋„ ์Šคํ„ฐ๋”” ๋•Œ ๋‚˜์™”๋˜ ์งˆ๋ฌธ์ด๋‚˜ ์•ˆ๊ฑด์„ ์ค‘์‹ฌ์œผ๋กœ ์ •๋ฆฌํ•ด๋†“์œผ๋ฉด ์ข‹์„ ๊ฒƒ ๊ฐ™์€ ๋‚ด์šฉ์„ ์ž‘์„ฑํ•ด๋ณด๋ คํ•œ๋‹ค!... ์งˆ๋ฌธ ๋ชฉ๋ก1๏ธโƒฃ ์ด ๋ฌธ์ œ๋Š” ์™œ DP๋กœ ํ’€์–ด์•ผ ํ• ๊นŒ?DP๋กœ ํ’€ ๋•Œ์˜ ํฐ ์žฅ์ ์€ ๊ฐ™์€ ์ž‘์—…์„ ๋ฐ˜๋ณตํ•˜์ง€ ์•Š๊ฒŒ ํ•ด์ค€๋‹ค๋Š” ๊ฒƒ ⇒ ๋ถˆํ•„์š”ํ•œ ์—ฐ์‚ฐ์„ ์ค„์—ฌ์„œ ํšจ์œจ์ ์ด๋‹ค!ex. ์ ํ™”์‹์œผ๋กœ ์–ด๋–ค ๊ฐ’์„ ๊ตฌํ•ด..

Java ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋”” Graph & Tree

SSAFY์— ๋“ค์–ด์™€์„œ Java๋ฅผ ์ฒ˜์Œ ์‹œ์ž‘ํ–ˆ๋Š”๋ฐ.. Java๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€์–ด์•ผํ•ด์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์Šคํ„ฐ๋””๋ฅผ ์‹œ์ž‘ํ–ˆ๋‹ค๐Ÿ”ฅ์Šคํ„ฐ๋””๋Š” ๊ฐ„๋‹จํ•˜๊ฒŒ ๊ฐ์ž ๊ณผ์ œ๋กœ ๋ฌธ์ œ๋ฅผ ๊ณตํ†ต ๋ฌธ์ œ๋ฅผ ํ’€์–ด์˜ค๊ณ  ๋ฌธ์ œ ๋‹น ๋žœ๋ค์œผ๋กœ 2๋ช…์”ฉ ์ž์‹ ์˜ ํ’€์ด๋ฅผ ์„ค๋ช…ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ง„ํ–‰ํ–ˆ๋‹ค.์Šคํ„ฐ๋”” ์ฒซ์งธ ์ฃผ! ์ฃผ์ œ๋Š”..Graph & Tree๊ทธ๋ž˜ํ”„ / ํŠธ๋ฆฌ ํƒ์ƒ‰, DFS/BFS, ๋‹ค์ต์ŠคํŠธ๋ผ ์œ ํ˜•์˜ ๋ฌธ์ œ๊ฐ€ ์žˆ์—ˆ๋Š”๋ฐ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋…์€ ๋‚˜์ค‘์— ์ •๋ฆฌํ•ด๋ณด๊ณ  ์ง€๊ธˆ ํฌ์ŠคํŠธ์—์„œ๋Š” ์Šคํ„ฐ๋””๋ฅผ ์ง„ํ–‰ํ•˜๋ฉด์„œ ๋‚˜์™”๋˜ ์งˆ๋ฌธ์„ ์ •๋ฆฌํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค!...์งˆ๋ฌธ ๋ชฉ๋ก1๏ธโƒฃ StringBuilder๊ฐ€ ๋น ๋ฅด๋‹ค? ์™œ?StringBuilder VS StringString ๋ณด๋‹ค๋Š” ๋น ๋ฆ„String์€ ๋ถˆ๋ณ€ ๊ฐ์ฒด๋ผ์„œ ํ•œ๋ฒˆ ์ƒ์„ฑ๋˜๋ฉด ๋ณ€๊ฒฝํ•  ์ˆ˜ ์—†์Œ๊ทธ๋ž˜์„œ +์—ฐ์‚ฐํ•˜๊ฑฐ๋‚˜ ์ˆ˜์ •ํ•˜๋ฉด ์ƒˆ๋กœ์šด String๊ฐ์ฒด ๋งŒ๋“ค๊ณ  ๊ทธ๊ฑธ..