์•Œ๊ณ ๋ฆฌ์ฆ˜/์ด๋ก 

int[] copy = arr ๋Š” ๋ฐฐ์—ด ๊ฐ’์„ ๋ณต์‚ฌํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ, ์ฃผ์†Œ๊ฐ’์„ ๋ณต์‚ฌํ•˜๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‘˜ ์ค‘ ํ•˜๋‚˜๋ฅผ ๋ณ€๊ฒฝํ•˜๊ฒŒ ๋˜๋ฉด → ๋‹ค๋ฅธ ๊ฐ’ ๋˜ํ•œ ๋ณ€๊ฒฝ ๋จ ์ด๋ ‡๊ฒŒ ์ฃผ์†Œ ๊ฐ’๋งŒ ๋ณต์‚ฌํ•˜๋Š” ๊ฒƒ์„ Shallow Clone ๊ฐ’์„ ๋ณต์‚ฌํ•˜์—ฌ ๋‹ค๋ฅธ ๊ฐ์ฒด๋ฅผ ๋งŒ๋“œ๋Š” ๊ฒƒ์„ Deep Clone ์—ฌ๊ธฐ์„œ โœ… System.arraycopy() → Shallow Clone clone() → Deep Clone
Prim's Algorithm ์ด๋ž€ Prim's Algorithm์€ ๋ฌดํ–ฅ ์—ฐ๊ฒฐ ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ์†Œ ๋น„์šฉ ์‹ ์žฅ ํŠธ๋ฆฌ ์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ Prim's Algorithm ๋™์ž‘ 1๏ธโƒฃ ์ž„์˜์˜ node ( ์‹œ์ž‘ ์ •์  )์„ ์„ ํƒํ•˜์—ฌ MST ( ์ตœ์†Œ ๋น„์šฉ ์‹ ์žฅ ํŠธ๋ฆฌ ) ์ง‘ํ•ฉ์— ์ถ”๊ฐ€ 2๏ธโƒฃ ์ธ์ ‘ node ์ค‘ ์ตœ์†Œ ๋น„์šฉ์˜ edge๋กœ ์—ฐ๊ฒฐ๋œ node ์„ ํƒ ๐Ÿ‘‰ ์ด ๊ณผ์ •์„ ๋ชจ๋“  node๋ฅผ ์„ ํƒํ•  ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณต โ€ผ๏ธ Prim's Algorithm ์‹œ๊ฐ„ ๋ณต์žก๋„ ์ฃผ ๋ฐ˜๋ณต๋ฌธ์ด node์˜ ์ˆ˜ n๋ฒˆ ๋ฐ˜๋ณต โŒ ๋‚ด๋ถ€ ๋ฐ˜๋ณต๋ฌธ์ด n๋ฒˆ ๋ฐ˜๋ณต ๐Ÿ‘‰ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(n^2)
TreeMap ์ด๋ž€ ? TreeMap ์€ ์ด์ง„ํŠธ๋ฆฌ๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ ํ•œ Map ์ปฌ๋ ‰์…˜์ด๋‹ค. ์ •๋ ฌ ์ˆœ์„œ๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ๋ถ€๋ชจ ํ‚ค ๊ฐ’๊ณผ ๋น„๊ตํ•ด์„œ ์ž‘์€ ๊ฒƒ์€ ์™ผ์ชฝ ์ž์‹ ๋…ธ๋“œ์—, ํฐ ๊ฒƒ์€ ์˜ค๋ฅธ์ชฝ ์ž์‹ ๋…ธ๋“œ์— ๊ฐ์ฒด๋ฅผ ์ €์žฅํ•œ๋‹ค. Map์œผ๋กœ์จ์˜ ์„ฑ๋Šฅ์ด HashMap๋ณด๋‹ค ๋–จ์–ด์ง€์ง€๋งŒ, ์ •๋ ฌ๋œ ์ƒํƒœ๋กœ Map์œ ์ง€ํ•ด์•ผ ํ•˜๊ฑฐ๋‚˜ ์ •๋ ฌ๋œ ํ…Œ์ดํ„ฐ๋ฅผ ์กฐํšŒํ•ด์•ผํ•˜๋Š” ๋ฒ”์œ„ ๊ฒ€์ƒ‰์ด ํ•„์š”ํ•œ ๊ฒฝ์šฐ์—๋Š” ํšจ์œจ์„ฑ์ด ์ข‹๋‹ค. ๋ ˆ๋“œ - ๋ธ”๋ž™ ํŠธ๋ฆฌ (Red - Black Tree) TreeMap์€ ๋ ˆ๋“œ - ๋ธ”๋ž™ ํŠธ๋ฆฌ๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ์ผ๋ฐ˜์ ์ธ ์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ๋Š” ํŠธ๋ฆฌ์˜ ๋†’์ด๋งŒํผ ์‹œ๊ฐ„์ด ํ•„์š”ํ•˜๋‹ค. ๋งŒ์•ฝ ๋ฐ์ดํ„ฐ๊ฐ€ ์ž…๋ ฅ๋  ๋•Œ, ๊ฐ’์ด ํ•œ์ชฝ์œผ๋กœ ํŽธํ–ฅ๋˜๊ฒŒ ๋“ค์–ด์˜ฌ ๊ฒฝ์šฐ ํฌ๊ฒŒ ์น˜์šฐ์ณ์ง„ ํŠธ๋ฆฌ๊ฐ€ ๋˜์–ด์„œ ๊ต‰์žฅํžˆ ๋น„ํšจ์œจ์ ์ด๋‹ค. ์ด๋Ÿฌํ•œ ๋ฌธ์ œ๋ฅผ ๋ณด์™„ํ•˜๊ธฐ ์œ„ํ•œ ๊ฒƒ์ด Red - Black Tree
Parametric Search ๋ž€? ์ตœ์ ํ™” ๋ฌธ์ œ (๋ฌธ์ œ์˜ ์ƒํ™ฉ์„ ๋งŒ์กฑํ•˜๋Š” ํŠน์ • ๋ณ€์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’, ์ตœ๋Œ“๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ)๋ฅผ ๊ฒฐ์ • ๋ฌธ์ œ ( decision problem )์œผ๋กœ ๋ฐ”๊พธ์–ด ํ‘ธ๋Š” ๊ฒƒ ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜๋Š” ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋‚˜๊ฐ€๋Š” ๊ณผ์ •์ด ๋ฐ”์ด๋„ˆ๋ฆฌ ์„œ์น˜ ( ์ด๋ถ„ ํƒ์ƒ‰ ) ๊ณผ ๋งค์šฐ ํก์‚ฌํ•˜๋‹ค. โžก๏ธ ์˜์™ธ์˜ ๋ฌธ์ œ๋“ค์— ์ ์šฉ๋˜์–ด์„œ ์ตœ์ ํ™” ๋ฌธ์ œ๋“ค์„ ์กฐ๊ธˆ ๋” ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ๊ฒŒ ํ•ด์ค€๋‹ค. ํ•ต์‹ฌ์€ ๊ฒฐ์ • ๋ฌธ์ œ ๐Ÿ‘‰ ํ•ด๋‹น๊ฐ’์ด ์ •๋‹ต์ด ๋  ์ˆ˜ ์žˆ๋Š” ๊ฐ’์ธ์ง€ ์•„๋‹Œ์ง€๋ฅผ ์‰ฝ๊ฒŒ ํŒ๋‹จํ•  ์ˆ˜ ์žˆ์–ด์•ผ ์ตœ์ ํ™” ๋ฌธ์ œ๋ฅผ ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ๐Ÿ‘‰ ์ •๋‹ต์ด ๋  ์ˆ˜ ์žˆ๋Š” ๊ฐ’๋“ค์ด ์—ฐ์†์ ์ด์—ฌ์•ผ ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜๋ฅผ ์ด์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ์ •๋‹ต์ด a์ผ ๋•Œ, a ์ด์ƒ์˜ ๊ฐ’๋“ค์€ ๋ชจ๋‘ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•œ๋‹ค๋Š” ์˜๋ฏธ์‹œ๊ฐ„ ๋ณต์žก๋„ ์‹œ๊ฐ„ ๋ณต์žก๋„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž์ฒด๋ณด๋‹ค ์กฐ๊ฑด ํ•จ์ˆ˜๊ฐ€ ์–ผ๋งˆ๋‚˜ ๋น ๋ฅธ..
Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ? Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€, ๋ณ€์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์Œ์ด๊ฑฐ๋‚˜ ์–‘์ธ ( ์Œ์ˆ˜ ์‚ฌ์ดํด์€ ์—†๋Š” ) ๊ฐ€์ค‘ ๊ทธ๋ž˜ํ”„์—์„œ ๋ชจ๋“  ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ• ์ด๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋ฒจ๋งŒํฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•˜๋‚˜์˜ ์ •์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ• ์ด๋‹ค. Dijkstra ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ •ํ•ด์ง„ ์ถœ๋ฐœ์ง€ vertex ์—์„œ ๋ถ€ํ„ฐ ๋‹ค๋ฅธ ๋ชจ๋“  vertex์œผ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•œ๋‹ค. ๊ฐ€์žฅ ์ž‘์€ ๊ฐ€์ค‘์น˜๋ฅผ ํ•˜๋‚˜์”ฉ ์„ ํƒํ•ด๋‚˜๊ฐ„๋‹ค. ( ์šฐ์„ ์ˆœ์œ„ ํ ์ด์šฉ ) Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋“  vertex ์—์„œ ๋ชจ๋“  vertex ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ํ•œ๋ฒˆ์— ๊ตฌํ•œ๋‹ค. ์ฆ‰, ๋ชจ๋“  vertex ์Œ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•œ๋‹ค. ๋ชจ๋“  ์Œ์„ ํ‘œํ˜„ํ•˜๋Š” ์ด์ฐจ์› ๋ฐฐ์—ด ์„ ์„ ์–ธํ•˜๊ณ , Dynamic Programmi..
KIMHYEYUN
'์•Œ๊ณ ๋ฆฌ์ฆ˜/์ด๋ก ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๊ธ€ ๋ชฉ๋ก