[๋ฐฑ์ค€] 14501. ํ‡ด์‚ฌ/Python - Silver3
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/14501์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 32412 KB, ์‹œ๊ฐ„: 36 ms๋ฌธ์ œ ์„ค๋ช…์ƒ๋‹ด์›์œผ๋กœ ์ผํ•˜๊ณ  ์žˆ๋Š” ๋ฐฑ์ค€์ด๋Š” ํ‡ด์‚ฌ๋ฅผ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.์˜ค๋Š˜๋ถ€ํ„ฐ N+1์ผ์งธ ๋˜๋Š” ๋‚  ํ‡ด์‚ฌ๋ฅผ ํ•˜๊ธฐ ์œ„ํ•ด์„œ, ๋‚จ์€ N์ผ ๋™์•ˆ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์ƒ๋‹ด์„ ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.๋ฐฑ์ค€์ด๋Š” ๋น„์„œ์—๊ฒŒ ์ตœ๋Œ€ํ•œ ๋งŽ์€ ์ƒ๋‹ด์„ ์žก์œผ๋ผ๊ณ  ๋ถ€ํƒ์„ ํ–ˆ๊ณ , ๋น„์„œ๋Š” ํ•˜๋ฃจ์— ํ•˜๋‚˜์”ฉ ์„œ๋กœ ๋‹ค๋ฅธ ์‚ฌ๋žŒ์˜ ์ƒ๋‹ด์„ ์žก์•„๋†“์•˜๋‹ค.๊ฐ๊ฐ์˜ ์ƒ๋‹ด์€ ์ƒ๋‹ด์„ ์™„๋ฃŒํ•˜๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ๊ธฐ๊ฐ„ Ti์™€ ์ƒ๋‹ด์„ ํ–ˆ์„ ๋•Œ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๊ธˆ์•ก Pi๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.N = 7์ธ ๊ฒฝ์šฐ์— ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ƒ๋‹ด ์ผ์ •ํ‘œ๋ฅผ ๋ณด์ž. 1์ผ2์ผ3์ผ4์ผ5์ผ6์ผ7์ผ Ti 3511242Pi1020102015402001์ผ์— ์žกํ˜€์žˆ๋Š” ์ƒ๋‹ด์€ ์ด 3์ผ์ด ๊ฑธ๋ฆฌ๋ฉฐ, ์ƒ๋‹ดํ–ˆ์„ ๋•Œ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ๊ธˆ์•ก..
[๋ฐฑ์ค€] 18870. ์ขŒํ‘œ ์••์ถ•/Python - Silver2
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/18870์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 149248 KB, ์‹œ๊ฐ„: 1824 ms๋ถ„๋ฅ˜๊ฐ’ / ์ขŒํ‘œ ์••์ถ•, ์ •๋ ฌ ๋ฌธ์ œ ์„ค๋ช…์ˆ˜์ง์„  ์œ„์— N๊ฐœ์˜ ์ขŒํ‘œ X1, X2, ..., XN์ด ์žˆ๋‹ค. ์ด ์ขŒํ‘œ์— ์ขŒํ‘œ ์••์ถ•์„ ์ ์šฉํ•˜๋ ค๊ณ  ํ•œ๋‹ค.Xi๋ฅผ ์ขŒํ‘œ ์••์ถ•ํ•œ ๊ฒฐ๊ณผ X'i์˜ ๊ฐ’์€ Xi > Xj๋ฅผ ๋งŒ์กฑํ•˜๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ์ขŒํ‘œ Xj์˜ ๊ฐœ์ˆ˜์™€ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.X1, X2, ..., XN์— ์ขŒํ‘œ ์••์ถ•์„ ์ ์šฉํ•œ ๊ฒฐ๊ณผ X'1, X'2, ..., X'N๋ฅผ ์ถœ๋ ฅํ•ด๋ณด์ž.โœ๐Ÿปํ’€์ด๋ฌธ์ œ๋ฅผ ์ฝ์–ด๋ณด๋ฉด Xi > Xj๋ฅผ ๋งŒ์กฑํ•˜๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ์ขŒํ‘œ Xj์˜ ๊ฐœ์ˆ˜๊ฐ€ Xi'๊ณผ ๊ฐ™๋‹ค๊ณ  ํ•œ๋‹ค. ์ •๋ง ๋‹จ์ˆœํ•˜๊ฒŒ ์ƒ๊ฐํ•˜๋ฉด ์ด์ค‘๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ ์ตœ์•…์˜ ๊ฒฝ์šฐ O(N²)์œผ๋กœ N์ด ์ตœ๋Œ€ 1,000,..
[๋ฐฑ์ค€] 1012. ์œ ๊ธฐ๋† ๋ฐฐ์ถ”/Python - Silver 2
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1012์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 114308 KB, ์‹œ๊ฐ„: 132 ms๋ถ„๋ฅ˜๊ทธ๋ž˜ํ”„ ์ด๋ก , ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰, ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ๋ฌธ์ œ ์„ค๋ช…์ฐจ์„ธ๋Œ€ ์˜๋†์ธ ํ•œ๋‚˜๋Š” ๊ฐ•์›๋„ ๊ณ ๋žญ์ง€์—์„œ ์œ ๊ธฐ๋† ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๊ธฐ๋กœ ํ•˜์˜€๋‹ค. ๋†์•ฝ์„ ์“ฐ์ง€ ์•Š๊ณ  ๋ฐฐ์ถ”๋ฅผ ์žฌ๋ฐฐํ•˜๋ ค๋ฉด ๋ฐฐ์ถ”๋ฅผ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ๋‚˜๋Š” ํ•ด์ถฉ ๋ฐฉ์ง€์— ํšจ๊ณผ์ ์ธ ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๋ฅผ ๊ตฌ์ž…ํ•˜๊ธฐ๋กœ ๊ฒฐ์‹ฌํ•œ๋‹ค. ์ด ์ง€๋ ์ด๋Š” ๋ฐฐ์ถ”๊ทผ์ฒ˜์— ์„œ์‹ํ•˜๋ฉฐ ํ•ด์ถฉ์„ ์žก์•„ ๋จน์Œ์œผ๋กœ์จ ๋ฐฐ์ถ”๋ฅผ ๋ณดํ˜ธํ•œ๋‹ค. ํŠนํžˆ, ์–ด๋–ค ๋ฐฐ์ถ”์— ๋ฐฐ์ถ”ํฐ์ง€๋ ์ด๊ฐ€ ํ•œ ๋งˆ๋ฆฌ๋ผ๋„ ์‚ด๊ณ  ์žˆ์œผ๋ฉด ์ด ์ง€๋ ์ด๋Š” ์ธ์ ‘ํ•œ ๋‹ค๋ฅธ ๋ฐฐ์ถ”๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์–ด, ๊ทธ ๋ฐฐ์ถ”๋“ค ์—ญ์‹œ ํ•ด์ถฉ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธ๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. ํ•œ ๋ฐฐ์ถ”์˜ ์ƒํ•˜์ขŒ์šฐ ๋„ค ๋ฐฉํ–ฅ์— ๋‹ค๋ฅธ ๋ฐฐ์ถ”๊ฐ€ ์œ„์น˜ํ•œ ๊ฒฝ์šฐ์—..
[๋ฐฑ์ค€] 2667. ๋‹จ์ง€๋ฒˆํ˜ธ๋ถ™์ด๊ธฐ/Python - Silver 1
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/2667์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 108548 KB, ์‹œ๊ฐ„: 92 ms๋ถ„๋ฅ˜๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰, ๊ทธ๋ž˜ํ”„ ์ด๋ก , ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ๋ฌธ์ œ ์„ค๋ช…๊ณผ ๊ฐ™์ด ์ •์‚ฌ๊ฐํ˜• ๋ชจ์–‘์˜ ์ง€๋„๊ฐ€ ์žˆ๋‹ค. 1์€ ์ง‘์ด ์žˆ๋Š” ๊ณณ์„, 0์€ ์ง‘์ด ์—†๋Š” ๊ณณ์„ ๋‚˜ํƒ€๋‚ธ๋‹ค. ์ฒ ์ˆ˜๋Š” ์ด ์ง€๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์—ฐ๊ฒฐ๋œ ์ง‘์˜ ๋ชจ์ž„์ธ ๋‹จ์ง€๋ฅผ ์ •์˜ํ•˜๊ณ , ๋‹จ์ง€์— ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ด๋ ค ํ•œ๋‹ค. ์—ฌ๊ธฐ์„œ ์—ฐ๊ฒฐ๋˜์—ˆ๋‹ค๋Š” ๊ฒƒ์€ ์–ด๋–ค ์ง‘์ด ์ขŒ์šฐ, ํ˜น์€ ์•„๋ž˜์œ„๋กœ ๋‹ค๋ฅธ ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋ฅผ ๋งํ•œ๋‹ค. ๋Œ€๊ฐ์„ ์ƒ์— ์ง‘์ด ์žˆ๋Š” ๊ฒฝ์šฐ๋Š” ์—ฐ๊ฒฐ๋œ ๊ฒƒ์ด ์•„๋‹ˆ๋‹ค. ๋Š” ์„ ๋‹จ์ง€๋ณ„๋กœ ๋ฒˆํ˜ธ๋ฅผ ๋ถ™์ธ ๊ฒƒ์ด๋‹ค. ์ง€๋„๋ฅผ ์ž…๋ ฅํ•˜์—ฌ ๋‹จ์ง€์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๊ฐ ๋‹จ์ง€์— ์†ํ•˜๋Š” ์ง‘์˜ ์ˆ˜๋ฅผ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.โœ๐Ÿปํ’€์ด๊ฐ ๋‹จ์ง€์— ์†ํ•˜๋Š” ์ง‘์˜ ์ˆ˜..
[๋ฐฑ์ค€] 24480. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—… - ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ 2/Python - Silver 2
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/24480์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 70312 KB, ์‹œ๊ฐ„: 540 ms๋ถ„๋ฅ˜๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰, ๊ทธ๋ž˜ํ”„ ์ด๋ก , ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰, ์ •๋ ฌ๋ฌธ์ œ ์„ค๋ช…์˜ค๋Š˜๋„ ์„œ์ค€์ด๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS) ์ˆ˜์—… ์กฐ๊ต๋ฅผ ํ•˜๊ณ  ์žˆ๋‹ค. ์•„๋น ๊ฐ€ ์ˆ˜์—…ํ•œ ๋‚ด์šฉ์„ ํ•™์ƒ๋“ค์ด ์ž˜ ์ดํ•ดํ–ˆ๋Š”์ง€ ๋ฌธ์ œ๋ฅผ ํ†ตํ•ด์„œ ํ™•์ธํ•ด๋ณด์ž.N๊ฐœ์˜ ์ •์ ๊ณผ M๊ฐœ์˜ ๊ฐ„์„ ์œผ๋กœ ๊ตฌ์„ฑ๋œ ๋ฌด๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„(undirected graph)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ •์  ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ์ด๊ณ  ๋ชจ๋“  ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋Š” 1์ด๋‹ค. ์ •์  R์—์„œ ์‹œ์ž‘ํ•˜์—ฌ ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์œผ๋กœ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•  ๊ฒฝ์šฐ ๋…ธ๋“œ์˜ ๋ฐฉ๋ฌธ ์ˆœ์„œ๋ฅผ ์ถœ๋ ฅํ•˜์ž.๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ ์˜์‚ฌ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ์ธ์ ‘ ์ •์ ์€ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ๋‹ค.dfs(V, E, R) { # V : ์ •์  ์ง‘ํ•ฉ, E : ๊ฐ„์„  ..
[๋ฐฑ์ค€] 1753. ์ตœ๋‹จ๊ฒฝ๋กœ/Python - ๊ณจ๋“œ4
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œ์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 136204 KB, ์‹œ๊ฐ„: 380 ms๋ถ„๋ฅ˜๋‹ค์ต์ŠคํŠธ๋ผ, ๊ทธ๋ž˜ํ”„ ์ด๋ก , ์ตœ๋‹จ ๊ฒฝ๋กœ ๋ฌธ์ œ ์„ค๋ช…๋ฐฉํ–ฅ๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ฃผ์–ด์ง„ ์‹œ์ž‘์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ •์ ์œผ๋กœ์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ, ๋ชจ๋“  ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜๋Š” 10 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค.โœ๐Ÿปํ’€์ด์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์ธ์ ‘ํ–‰๋ ฌ๊ณผ ์ธ์ ‘๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ ์ธ์ ‘ ํ–‰๋ ฌ์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ, ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(V²)์ด ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒฝ์šฐ ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(E * logV)์ด ๋˜๋ฏ€๋กœ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ’€๊ฒ ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋‹ค์ต์ŠคํŠธ๋ผ๋Š” Heap์„ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์ด ๋น ๋ฆ…๋‹ˆ๋‹ค.heapq๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด pq๋ฅผ ์ƒ์„ฑํ•ด (๊ฐ€์ค‘์น˜, ์‹œ์ž‘ ์ •์ ) ์Œ์œผ๋กœ ํž™ํ์— ๋„ฃ์–ด์ค€๋‹ค. ๊ทธ๋ฆฌ๊ณ  dist๋Š” ๊ฐ ์ •์ ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํ…Œ์ด๋ธ”์„ ..