๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“’ | Kotlin/๐Ÿค– | ์•Œ๊ณ ๋ฆฌ์ฆ˜7

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋งค๊ฐœ๋ณ€์ˆ˜ ํƒ์ƒ‰(Parametric Search)๊ณผ ์ด๋ถ„ ํƒ์ƒ‰(Binary Search) ๋‚ด๊ฐ€ ์ž‘๋…„์— ๋ฐ”์ด๋„ˆ๋ฆฌ ์„œ์น˜์— ๋Œ€ํ•ด ์˜ฌ๋ฆฐ ์ ์ด ์žˆ๋‹ค.์ด๋ฒˆ์— ๋ฌธ์ œ ํ’€์ด์—์„œ ๋ฐ”์ด๋„ˆ๋ฆฌ ์„œ์น˜์™€ ๋งค๊ฐœ๋ณ€์ˆ˜ ํƒ์ƒ‰์„ ์ด์šฉํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ํ’€๊ณ  ๋‹ค์‹œ ๊ฐœ๋…์„ ๊ณต๋ถ€ํ•ด๋ณด๋ ค ํ•œ๋‹ค.  ์ด๋ถ„ ํƒ์ƒ‰ ๋ณต์Šต(Binary Search)์ด๋ถ„ ํƒ์ƒ‰์„ ๊ฐ„๋‹จํ•˜๊ฒŒ ๋ณต์Šต์„ ํ•ด๋ณด์ž.์•„๋ž˜ gif์„ ๋ณด๋ฉด ์ด๋ถ„ ํƒ์ƒ‰์ด ์–ด๋–ป๊ฒŒ ๋Œ์•„๊ฐ€๋Š”์ง€ ๋ฐ”๋กœ ์ดํ•ด๋ฅผ ํ•  ์ˆ˜ ์žˆ์„ ๊ฒƒ์ด๋‹ค. ์•„๋ž˜๊ฐ€ ์ผ๋ฐ˜ ๊ฒ€์ƒ‰ ๋ฐฉ๋ฒ•์ด๊ณ  ์œ„๊ฐ€ ์ด๋ถ„ ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์ธ๋ฐ,์ผ๋ฐ˜ ํƒ์ƒ‰๊ณผ๋Š” ๋‹ค๋ฅด๊ฒŒ ์ค‘๊ฐ„ ์ง€์ ๊ณผ ์‹œ์ž‘์ , ๋์ง€์ ์„ ์ •ํ•ด์„œ ์ค‘๊ฐ„๊ฐ’์„ ์ฐพ์•„์•ผ ํ•˜๋Š” ๊ฐ’๊ณผ ๋น„๊ต ํ›„ ๋Œ€์†Œ์— ๋”ฐ๋ผ ๋ฒ”์œ„๋ฅผ ์ค„์—ฌ๊ฐ€๋ฉด์„œ ํƒ์ƒ‰ํ•œ๋‹ค.์ด๋ถ„ ํƒ์ƒ‰์€ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ •๋ ฌ๋˜์–ด์žˆ์–ด์•ผ ํ•œ๋‹ค๋Š” ์ ์ด ํŠน์ง•์ด๋‹ค.์ค‘๊ฐ„๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ๋Œ€์†Œ๋ฅผ ๋น„๊ตํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์กฐ๊ฑด์— ๋ถ€ํ•ฉํ•˜์ง€ ์•Š์€ ์ ˆ๋ฐ˜์˜ ๋ฐ์ดํ„ฐ๋ฅผ ๊ฑธ๋Ÿฌ๊ฐ€๋ฉด์„œ ํƒ์ƒ‰ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํƒ์ƒ‰ ์‹œ๊ฐ„์ด ํšจ๊ณผ์ ์œผ๋กœ ์ค„์–ด๋“ ๋‹ค.  ๋งค๊ฐœ ๋ณ€์ˆ˜.. 2024. 6. 26.
[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋งค๋‚ด์ฒ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜(Manacher) ๊ฐœ๋… ๋งค๋‚ด์ฒ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?๋ฌธ์ž์—ด S๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋œปํ•œ๋‹ค. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด์€ S์˜ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด ์ค‘ ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ ๊ฒฝ์šฐ๋ฅผ ์˜๋ฏธํ•œ๋‹ค(banana์—์„œ anana๊ฐ€ ๋ถ€๋ถ„ ๋ฌธ์ž์—ด ํŒฐ๋ฆฐ๋“œ๋กฌ์ด๋‹ค).๋ชจ๋“  i์— ๋Œ€ํ•ด i๋ฒˆ ๋ฌธ์ž๊ฐ€ ์ค‘์‹ฌ์ธ ์ตœ๋Œ€ ๊ธธ์ด์˜ ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„๋ฌธ์ž์—ด์„ ๊ฒ€์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜.ํŒฐ๋ฆฐ๋“œ๋กฌ์˜ ๊ธธ์ด๋Š” ์ฃผ๋กœ ํŒฐ๋ฆฐ๋“œ๋กฌ์˜ ๋ฐ˜์ง€๋ฆ„์˜ ํ˜•ํƒœ๋กœ ์ €์žฅ๋œ๋‹ค(๋ฐ˜์ง€๋ฆ„์ด๋ž€, ํŒฐ๋ฆฐ๋“œ๋กฌ์˜ ์ค‘์‹ฌ์œผ๋กœ๋ถ€ํ„ฐ ๊ฐ€์žฅ ๋จผ ๋ฌธ์ž๊ฐ€ ์–ผ๋งˆ๋‚˜ ๋–จ์–ด์ ธ ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•œ ๊ฒƒ์ด๋‹ค(aba์—์„œ ๋ฐ˜์ง€๋ฆ„์€ 1์ด ๋œ๋‹ค).ํŒฐ๋ฆฐ๋“œ๋กฌ์˜ ๊ธธ์ด๊ฐ€ i๋ผ๋ฉด ๋ฐ˜์ง€๋ฆ„์€ (i -1) / 2๊ฐ€ ๋œ๋‹ค. ๋งค๋‚ด์ฒ˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์•Œ์•„๋ณด๊ธฐ ์ „์— ํŒฐ๋ฆฐ๋“œ๋กฌ์ด ์ •ํ™•ํžˆ ๋ฌด์—‡์ธ์ง€ ์งš๊ณ  ๋„˜์–ด๊ฐ€์ž. ํŒฐ๋ฆฐ๋“œ๋กฌ(ํšŒ๋ฌธ, palindrome)๋’ค์ง‘์–ด๋„ ๊ฐ™์€ ๋ฌธ์ž์—ด์„ ๋œปํ•œ๋‹ค.๊ฑฐ๊พธ๋กœ ์ฝ์–ด๋„.. 2024. 6. 24.
[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜(DFS, BFS) ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์ด๋ž€?๋งŽ์€ ์–‘์˜ ๋ฐ์ดํ„ฐ๋“ค ์ค‘์—์„œ ์›ํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๋Š” ๊ณผ์ •์„ ํƒ์ƒ‰์ด๋ผ๊ณ  ํ•˜๋Š”๋ฐ,๊ทธ๋ž˜ํ”„์—์„œ ์›ํ•˜๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๋Š” ๊ณผ์ •์„ ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์ด๋ผ ๋ถ€๋ฅธ๋‹ค. ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—๋Š” DFS, BFS๊ฐ€ ์žˆ๋‹ค.DFS(Depth-First Search): ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰BFS(Breadth-First Search): ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS)๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ทธ๋ž˜ํ”„์˜ ์ž์‹ ๋ฐ์ดํ„ฐ์— ๋“ค์–ด๊ฐ„ ํ›„, ์ž์‹์˜ ์ž์‹ ๋ฐ์ดํ„ฐ๋ฅผ ์ž์‹์˜ ์ž์‹์˜ ์ž์‹ ๋ฐ์ดํ„ฐ๋ฅผ ๋“ค์–ด๊ฐ€๋Š” ์‹์œผ๋กœ, ํ•œ ๊ฐ€์ง€๋ฅผ ๋๊นŒ์ง€ ํŒŒ๊ณ  ๋“ค์–ด๊ฐ€์„œ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋œปํ•œ๋‹ค. ํ•œ ์ค„๊ธฐ๋ฅผ ๋๊นŒ์ง€ ํŒŒ๊ณ ๋“  ํ›„, ๋‹ค์Œ ์ค„๊ธฐ๋กœ ์ด๋™ํ•ด ๋‹ค์‹œ ๋๊นŒ์ง€ ํŒŒ๊ณ ๋“œ๋Š” ๋ฐฉ์‹์œผ๋กœ ์ž‘๋™ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.  ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS)๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์€ ์‹œ์ž‘ ๋ฐ์ดํ„ฐ์—์„œ ์ž์‹ ์˜ ์ž.. 2024. 6. 22.
[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(Greedy Algorithm) ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€?๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜(ํƒ์š•๋ฒ•)์ด๋ž€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ๊ฐ€์žฅ ์ข‹์€ ๊ฒƒ(์ตœ์„ ์˜ ์„ ํƒ)์„ ๊ณ ๋ฅด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋œปํ•œ๋‹ค. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ(DP)์„ ๊ฐ„๋‹จํ•œ ๋ฌธ์ œ ํ•ด๊ฒฐ์— ์‚ฌ์šฉํ•˜๋ฉด ์ง€๋‚˜์น˜๊ฒŒ ๋งŽ์€ ์ผ์„ ํ•œ๋‹ค๋Š” ๊ฒƒ์„ ์ฐฉ์•ˆํ•ด ๊ณ ์•ˆ๋˜์—ˆ๋‹ค. ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ๊ฐ€์žฅ ์ข‹์€ ๊ฒฐ๊ณผ๋ฅผ ์„ ํƒํ•ด ๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„ ๊ธฐ๋ฒ•์ด๋‹ค.ํ•˜์ง€๋งŒ ์ด ๊ฐ€์žฅ ์ข‹์€ ๊ฒฐ๊ณผ๋Š” ํ•ญ์ƒ ์ตœ์ข…์ ์ธ ๊ฒฐ๊ณผ ๋„์ถœ์— ๋Œ€ํ•œ ์ตœ์ ํ•ด๋ฅผ ๋ณด์žฅํ•ด ์ฃผ๋Š” ๊ฒƒ์€ ์•„๋‹ˆ๋‹ค.   ์œ„ ๊ทธ๋ฆผ์—์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’์ด ์ตœ์ ์˜ ๊ฐ’์ผ ๋•Œ, ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ˜„์žฌ ์ƒํ™ฉ์—์„œ ๊ฐ€์žฅ ์ตœ์ ์˜ ๊ฐ’์„ ๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์—์ตœ์ข…์ ์ธ ๋‹ต์€ 23์ด ๋‚˜์˜ค๊ฒŒ ๋œ๋‹ค(์ตœ์ ์˜ ๊ฐ’: 128). ๊ทธ๋ฆฌ๋”” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ ์ตœ์ข…์ ์ธ ๊ฒฐ๊ณผ ๋„์ถœ์— ์ตœ์ ํ•ด๋ฅผ ๋ณด์žฅํ•ด ์ฃผ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— ์ƒํ™ฉ์— ๋งž๊ฒŒ ์‚ฌ์šฉํ•ด์•ผ ํ•œ.. 2024. 6. 18.
[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ(Dynamic Programming) ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ(๋™์  ๊ณ„ํš๋ฒ•)์€ ๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๋” ์ž‘์€ ํ•˜์œ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ•ด๊ฒฐํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„ ๊ธฐ๋ฒ•์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ค๊ณ„ ๊ธฐ๋ฒ•: ๋ฌธ์ œ ํ•ด๊ฒฐ์„ ์œ„ํ•ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ค๊ณ„ํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‚˜ ์ ‘๊ทผ ๋ฐฉ์‹์„ ๋œปํ•œ๋‹ค.์„ค๊ณ„ ๊ธฐ๋ฒ•์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ฐœ๋ฐœํ•˜๊ณ  ๊ตฌํ˜„ํ•˜๋Š” ๋ฐ ์‚ฌ์šฉ๋˜๋Š” ์ „๋žต๊ณผ ์›์น™์„ ๋œปํ•œ๋‹ค. DP์™€ ์žฌ๊ท€ ํ˜ธ์ถœ์˜ ์ฐจ์ด์ DP์™€ ์žฌ๊ท€ ํ˜ธ์ถœ์˜ ์ฐจ์ด์ ์„ ์•Œ๊ธฐ ์ „์— ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•๊ณผ ์ƒํ–ฅ์‹ ์ ‘๊ทผ๋ฒ•์ด ๋ฌด์—‡์ธ์ง€ ์•Œ์•„์•ผ ํ•œ๋‹ค.1. ํ•˜ํ–ฅ์‹(top-down) ์ ‘๊ทผ๋ฒ•๊ณผ ์ƒํ–ฅ์‹(bottom-top) ์ ‘๊ทผ๋ฒ•ํ•˜ํ–ฅ์‹ ์ ‘๊ทผ ๋ฐฉ์‹์€ ํฐ ๋ฌธ์ œ๋ฅผ ์ž‘์€ ํ•˜์œ„ ๋ฌธ์ œ๋กœ ์ชผ๊ฐœ์„œ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ์ฃผ๋กœ ์žฌ๊ท€ ํ˜ธ์ถœ์„ ํ•  ๋•Œ ์‚ฌ์šฉ๋œ๋‹ค.์ƒํ–ฅ์‹ ์ ‘๊ทผ ๋ฐฉ์‹์€ ์ž‘์€ ๋ฌธ์ œ๋“ค๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด ์ž‘์€ ๋ฌธ์ œ๋“ค์˜ ๊ฒฐ๊ณผ๋ฅผ ์ด์šฉํ•ด ์ ์  ํฐ ๋ฌธ์ œ์˜ ๊ฒฐ๊ณผ๋ฅผ ๊ตฌํ•˜๋Š” ๋ฐฉ๋ฒ•. 2. ๋ฉ”๋ชจ์ด์ œ์ด์…˜(Memo.. 2024. 6. 12.
[Kotlin] ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ•์ด๋ž€? 2๊ฐœ์˜ ์ž์—ฐ์ˆ˜์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ธฐ๋ณธ ๊ณผ์ • ์˜ˆ์‹œ๋กœ 32์™€ 24์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ฉด, 32๋Š” 24๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์—, 32๋ฅผ 24๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๊ตฌํ•œ๋‹ค. => 8 32๋Š” 8๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง„๋‹ค. ๋”ฐ๋ผ์„œ 32์™€ 24์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋Š” 8์ด๋‹ค. ์˜ˆ์ œ ์ฝ”๋“œ1. ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉ package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val number = bf.readLine().split(" ") val a = number[0].toInt() val .. 2022. 10. 24.
[Kotlin] ์ด์ง„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ด์ง„ ํƒ์ƒ‰์ด๋ž€? ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ์˜ ์ค‘๊ฐ„ ๊ฐ’์„ ์ด์šฉํ•ด ๊ฒ€์ƒ‰ ๊ฐ’์„ ์ค„์—ฌ ๊ฐ€๋ฉด์„œ ์›ํ•˜๋Š” ๊ฐ’์„ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํƒ์ƒ‰ ๊ณผ์ • ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ์˜ ์ค‘๊ฐ„๊ฐ’์„ ์ฐพ๋Š”๋‹ค. ์ฐพ๋Š” ์ˆ˜๊ฐ€ ์ค‘๊ฐ„๊ฐ’๋ณด๋‹ค ํฌ๋ฉด ์˜ค๋ฅธ์ชฝ์œผ๋กœ, ์ž‘์œผ๋ฉด ์™ผ์ชฝ์œผ๋กœ ๊ฒ€์ƒ‰ ๋ฒ”์œ„๋ฅผ ์ขํžŒ๋‹ค. 1, 2๋ฒˆ์„ ๋ฐ˜๋ณตํ•œ๋‹ค. ์ด ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•˜๋ฉด ๊ทธ๋ƒฅ ๋ฐ˜๋ณต๋ฌธ์„ ์ด์šฉํ•ด ์ฐพ๋Š” ๊ฒƒ๋ณด๋‹ค ๋” ๋น ๋ฅด๊ฒŒ ์›ํ•˜๋Š” ์ˆซ์ž๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค. ์˜ˆ์ œ ์ฝ”๋“œ ์ˆซ์ž์˜ ๋ฒ”์œ„์™€ ์›ํ•˜๋Š” ์ˆซ์ž๋ฅผ ์ž…๋ ฅํ•˜๊ณ  ์ด์ง„ ํƒ์ƒ‰์œผ๋กœ ๊ทธ ์ˆซ์ž๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val array.. 2022. 10. 21.
728x90