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

๐Ÿ’พ Algorithm147

[์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด ์Šคํ‚ฌ] ์ž๋ฐ”๋กœ ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ ์„œ๋ก  ์•Œ๊ณ ๋ฆฌ์ฆ˜ PS ๋ฅผ ํ•˜๋‹ค๋ณด๋ฉด ์•ŒํŒŒ๋ฒณ์„ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•ด์•ผํ•˜๋Š” ์ผ์ด ์ข…์ข… ์ƒ๊ธด๋‹ค. ์ด๋ฅผํ…Œ๋ฉด ๋ฐฑ์ค€ 1316๋ฒˆ ๊ทธ๋ฃน ๋‹จ์–ด ์ฒด์ปค ๋ฐฑ์ค€ 10809๋ฒˆ ์•ŒํŒŒ๋ฒณ ์ฐพ๊ธฐ ๋“ฑ๋“ฑ ์ด์™ธ์—๋„ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ์—์„œ๋„ ๊ฐ„๊ฐ„ํžˆ ์ด์™€ ๋น„์Šทํ•œ ์œ ํ˜•์˜ ๋ฌธ์ œ๋“ค์—์„œ ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ ํ•˜๋Š” ๋ฌธ์ œ๋“ค์ด ๋ช‡๊ฐ€์ง€ ์กด์žฌํ•œ๋‹ค. ์˜ค๋Š˜์€ ๊ทธ ๋ฌธ์ œ๋“ค์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋ ค ํ•œ๋‹ค. ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•˜๊ธฐ ์•ŒํŒŒ๋ฒณ์„ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ๋ณ€ํ™˜ํ•œ๋‹ค๋Š” ๋ง์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์•ŒํŒŒ๋ฒณ์€ ์ด 26๊ฐœ์˜ ๋ฌธ์ž๊ฐ€ ์กด์žฌํ•œ๋‹ค. ๊ทธ๋Ÿผ ์ด๋ฅผ ๋ฐฐ์—ด๋กœ ๋ฐ”๊พผ๋‹ค๋ฉด a ๋Š” 0 ๋ฒˆ์งธ ์ธ๋ฑ์Šค๋กœ b ๋Š” 1๋ฒˆ์งธ ์ธ๋ฑ์Šค๋กœ ... z ๋Š” 25 ์ธ๋ฑ์Šค๋กœ ์œ„์น˜ํ•  ๊ฒƒ์ด๋‹ค. ์ด๋Ÿฌํ•œ ๊ฒƒ์„ ๋ฐ”๋กœ ๋ฐฐ์—ด์˜ ์ธ๋ฑ์Šค๋กœ ์•ŒํŒŒ๋ฒณ์„ ๋ณ€ํ™˜ํ•œ๋‹ค๊ณ  ํ•œ๋‹ค. ์ด๊ฒƒ์„ ์ฝ”๋“œ๋กœ ๋ด๋ณด.. 2022. 3. 19.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 15729๋ฒˆ ๋ฐฉํƒˆ์ถœ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ ๋ฐฑ์ค€ 15729 ๋ฐฉํƒˆ์ถœ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. 15729๋ฒˆ: ๋ฐฉํƒˆ์ถœ ์ฒซ์งธ ์ค„์— N(1 โ‰ค N โ‰ค 1,000,000)๊ฐ€ ์ฃผ์–ด์ง€๊ณ  ๋‘˜์งธ ์ค„์—๋Š” ์ชฝ์ง€์— ์ ํ˜€ ์žˆ๋Š” N์ž๋ฆฌ์˜ ์ˆ˜๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. www.acmicpc.net ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ๋ฌธ์ œ ์ ‘๊ทผ ์ด ๋ฌธ์ œ๋Š” Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋‹ค. ์šฐ์„  2๊ฐ€์ง€์˜ ๋ถˆ์„ ๋‚˜๋ˆ ์„œ ์ƒ๊ฐํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ๋ถˆ์ด ๋ชจ๋‘ ๊บผ์ง„ ์ƒํƒœ -> starts ์›ํ•˜๋Š” ๋ถˆ์ด ์ผœ์ง„ ์™„์„ฑ ์ƒํƒœ -> ends ๋ฌธ์ œ ํ•ด๊ฒฐ ์ปจ์…‰์€ starts ์—์„œ ๋ฐฐ์—ด ์›์†Œ ํ•˜๋‚˜์”ฉ ๋Œ๋ฉฐ ends ๋ฐฐ์—ด๊ณผ ๋‹ค๋ฅธ ์ธ๋ฑ์Šค๊ฐ€ ์žˆ๋‹ค๋ฉด.. 2021. 12. 8.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 1946๋ฒˆ ์‹ ์ž… ์‚ฌ์› ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ ๋ฌธ์ œ ์ด๋ฆ„ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. 1946๋ฒˆ: ์‹ ์ž… ์‚ฌ์› ์ฒซ์งธ ์ค„์—๋Š” ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ๊ฐœ์ˆ˜ T(1 โ‰ค T โ‰ค 20)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์˜ ์ฒซ์งธ ์ค„์— ์ง€์›์ž์˜ ์ˆซ์ž N(1 โ‰ค N โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ ์ค„์—๋Š” ๊ฐ๊ฐ์˜ ์ง€์›์ž์˜ ์„œ๋ฅ˜์‹ฌ์‚ฌ ์„ฑ www.acmicpc.net ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ๋ฌธ์ œ ์ ‘๊ทผ ์ด๋ฒˆ ๋ฌธ์ œ๋Š” Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด์„œ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋‹ค. Greedy ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํŠน์„ฑ๋‹ต๊ฒŒ ํ•ต์‹ฌ ์•„์ด๋””์–ด๊ฐ€ ์ค‘์š”ํ•œ ๋ฌธ์ œ๊ฐ™๋‹ค. ํ•ด๊ฒฐ๋ฒ• ๋งŒ์•ฝ ์„œ๋ฅ˜ ์ ์ˆ˜๋˜ ๋ฉด์ ‘์ด๋˜ ํ•˜๋‚˜๋ผ๋„ 1๋“ฑ์—๊ฒŒ ๋–จ์–ด์ง€๋ฉด ๊ทธ ์ธ์›.. 2021. 8. 19.
[์•Œ๊ณ ๋ฆฌ์ฆ˜ PS] ๋ฐฑ์ค€ 2206๋ฒˆ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ ์ž๋ฐ” ๋ฌธ์ œํ’€์ด ๋ฌธ์ œ ํ•ด๋‹น ํฌ์ŠคํŒ…์€ ๋ฐฑ์ค€์˜ 2206๋ฒˆ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ ์˜ ์ ‘๊ทผ๊ณผ ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•์„ ์„ค๋ช…ํ•œ ๊ธ€ ์ž…๋‹ˆ๋‹ค. ์ •๋‹ต ์†Œ์Šค ์ฝ”๋“œ๋ฅผ ํ™•์ธํ•˜์‹œ๋ ค๋ฉด solve url ์—์„œ ํ™•์ธ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. 2206๋ฒˆ: ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ Nร—M์˜ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„๋˜๋Š” ๋งต์ด ์žˆ๋‹ค. ๋งต์—์„œ 0์€ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ด๊ณ , 1์€ ์ด๋™ํ•  ์ˆ˜ ์—†๋Š” ๋ฒฝ์ด ์žˆ๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ๋‹น์‹ ์€ (1, 1)์—์„œ (N, M)์˜ ์œ„์น˜๊นŒ์ง€ ์ด๋™ํ•˜๋ ค ํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ตœ๋‹จ ๊ฒฝ๋กœ www.acmicpc.net ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์–ด๋–ค ๋ฐฉ์‹์œผ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•˜๋Š”์ง€๋ฅผ ๋จผ์ € ์ƒ๊ฐํ•ด๋ณด์ž. ๋ฌธ์ œ ์ ‘๊ทผ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ผ BFS๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ด๋‹ค. ์ง€๊ธˆ๊นŒ์ง€ ํ•ด๊ฒฐํ–ˆ๋˜ BFS ์—์„œ๋Š” ์ œ์ผ ์ดํ•ด๊ฐ€ ํž˜๋“ค์—ˆ๋˜ ๋ฌธ์ œ๋‹ค. ์ฒ˜์Œ์€ ๋ธŒ๋ฃจํŠธํฌ์Šค๋กœ ๋ฒฝ์„ ๋šซ๊ณ  bfs ๋ฅผ ์ˆ˜ํ–‰ํ–ˆ๋Š”๋ฐ ๊ณ„์†ํ•ด์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ .. 2021. 8. 15.