[๋ฐฑ์ค€] 2075. N๋ฒˆ์งธ ํฐ ์ˆ˜/Python - Silver3
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/2075์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 115420 KB, ์‹œ๊ฐ„: 532 ms๋ถ„๋ฅ˜์ž๋ฃŒ ๊ตฌ์กฐ, ์ •๋ ฌ, ์šฐ์„ ์ˆœ์œ„ ํ ๋ฌธ์ œ ์„ค๋ช…N×N์˜ ํ‘œ์— ์ˆ˜ N2๊ฐœ ์ฑ„์›Œ์ ธ ์žˆ๋‹ค. ์ฑ„์›Œ์ง„ ์ˆ˜์—๋Š” ํ•œ ๊ฐ€์ง€ ํŠน์ง•์ด ์žˆ๋Š”๋ฐ, ๋ชจ๋“  ์ˆ˜๋Š” ์ž์‹ ์˜ ํ•œ ์นธ ์œ„์— ์žˆ๋Š” ์ˆ˜๋ณด๋‹ค ํฌ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค. N=5์ผ ๋•Œ์˜ ์˜ˆ๋ฅผ ๋ณด์ž.127915513811196211026311648142835255220324149์ด๋Ÿฌํ•œ ํ‘œ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, N๋ฒˆ์งธ ํฐ ์ˆ˜๋ฅผ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ํ‘œ์— ์ฑ„์›Œ์ง„ ์ˆ˜๋Š” ๋ชจ๋‘ ๋‹ค๋ฅด๋‹ค.โœ๐Ÿปํ’€์ด์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•ด N๋ฒˆ์งธ ํฐ ์ˆ˜๋ฅผ ์ฐพ์Šต๋‹ˆ๋‹ค.์ตœ์†Œ ํž™ ํ๋ฅผ ์ด์šฉํ•˜๋ฉด [12], [7, 12], [7, 12, 9], ... , [28, 31, 48, 35, 52], [31, 32, 48..
[๋ฐฑ์ค€] 20040. ์‚ฌ์ดํด ๊ฒŒ์ž„/Python - Gold4
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/20040์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 116208 KB, ์‹œ๊ฐ„: 292 ms๋ถ„๋ฅ˜์ž๋ฃŒ ๊ตฌ์กฐ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ ๋ฌธ์ œ ์„ค๋ช…์‚ฌ์ดํด ๊ฒŒ์ž„์€ ๋‘ ๋ช…์˜ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ฐจ๋ก€๋Œ€๋กœ ๋Œ์•„๊ฐ€๋ฉฐ ์ง„ํ–‰ํ•˜๋Š” ๊ฒŒ์ž„์œผ๋กœ, ์„  ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ํ™€์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ, ํ›„ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ง์ˆ˜ ๋ฒˆ์งธ ์ฐจ๋ก€๋ฅผ ์ง„ํ–‰ํ•œ๋‹ค. ๊ฒŒ์ž„ ์‹œ์ž‘ ์‹œ 0 ๋ถ€ํ„ฐ n − 1 ๊นŒ์ง€ ๊ณ ์œ ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ€์—ฌ๋œ ํ‰๋ฉด ์ƒ์˜ ์  n ๊ฐœ๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ด ์ค‘ ์–ด๋А ์„ธ ์ ๋„ ์ผ์ง์„  ์œ„์— ๋†“์ด์ง€ ์•Š๋Š”๋‹ค. ๋งค ์ฐจ๋ก€ ๋งˆ๋‹ค ํ”Œ๋ ˆ์ด์–ด๋Š” ๋‘ ์ ์„ ์„ ํƒํ•ด์„œ ์ด๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์„ ๋ถ„์„ ๊ธ‹๋Š”๋ฐ, ์ด์ „์— ๊ทธ๋ฆฐ ์„ ๋ถ„์„ ๋‹ค์‹œ ๊ทธ์„ ์ˆ˜๋Š” ์—†์ง€๋งŒ ์ด๋ฏธ ๊ทธ๋ฆฐ ๋‹ค๋ฅธ ์„ ๋ถ„๊ณผ ๊ต์ฐจํ•˜๋Š” ๊ฒƒ์€ ๊ฐ€๋Šฅํ•˜๋‹ค. ๊ฒŒ์ž„์„ ์ง„ํ–‰ํ•˜๋‹ค๊ฐ€ ์ฒ˜์Œ์œผ๋กœ ์‚ฌ์ดํด์„ ์™„์„ฑํ•˜๋Š” ์ˆœ๊ฐ„ ๊ฒŒ์ž„์ด ์ข…๋ฃŒ๋œ๋‹ค. ์‚ฌ์ดํด C๋Š” ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ..
[๋ฐฑ์ค€] 1956. ์šด๋™/Python - Gold4
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1956์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 112760 KB, ์‹œ๊ฐ„: 2168 ms๋ถ„๋ฅ˜๊ทธ๋ž˜ํ”„ ์ด๋ก , ์ตœ๋‹จ ๊ฒฝ๋กœ, ํ”Œ๋กœ์ด๋“œ–์›Œ์…œ ๋ฌธ์ œ ์„ค๋ช…V๊ฐœ์˜ ๋งˆ์„์™€ E๊ฐœ์˜ ๋„๋กœ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š” ๋„์‹œ๊ฐ€ ์žˆ๋‹ค. ๋„๋กœ๋Š” ๋งˆ์„๊ณผ ๋งˆ์„ ์‚ฌ์ด์— ๋†“์—ฌ ์žˆ์œผ๋ฉฐ, ์ผ๋ฐฉ ํ†ตํ–‰ ๋„๋กœ์ด๋‹ค. ๋งˆ์„์—๋Š” ํŽธ์˜์ƒ 1๋ฒˆ๋ถ€ํ„ฐ V๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค๊ณ  ํ•˜์ž.๋‹น์‹ ์€ ๋„๋กœ๋ฅผ ๋”ฐ๋ผ ์šด๋™์„ ํ•˜๊ธฐ ์œ„ํ•œ ๊ฒฝ๋กœ๋ฅผ ์ฐพ์œผ๋ ค๊ณ  ํ•œ๋‹ค. ์šด๋™์„ ํ•œ ํ›„์—๋Š” ๋‹ค์‹œ ์‹œ์ž‘์ ์œผ๋กœ ๋Œ์•„์˜ค๋Š” ๊ฒƒ์ด ์ข‹๊ธฐ ๋•Œ๋ฌธ์—, ์šฐ๋ฆฌ๋Š” ์‚ฌ์ดํด์„ ์ฐพ๊ธฐ๋ฅผ ์›ํ•œ๋‹ค. ๋‹จ, ๋‹น์‹ ์€ ์šด๋™์„ ๋งค์šฐ ๊ท€์ฐฎ์•„ํ•˜๋ฏ€๋กœ, ์‚ฌ์ดํด์„ ์ด๋ฃจ๋Š” ๋„๋กœ์˜ ๊ธธ์ด์˜ ํ•ฉ์ด ์ตœ์†Œ๊ฐ€ ๋˜๋„๋ก ์ฐพ์œผ๋ ค๊ณ  ํ•œ๋‹ค.๋„๋กœ์˜ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋„๋กœ์˜ ๊ธธ์ด์˜ ํ•ฉ์ด ๊ฐ€์žฅ ์ž‘์€ ์‚ฌ์ดํด์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ..
[๋ฐฑ์ค€] 1976. ์—ฌํ–‰ ๊ฐ€์ž/Python - Gold4
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1976์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 32412 KB, ์‹œ๊ฐ„: 40 ms๋ถ„๋ฅ˜๊ทธ๋ž˜ํ”„ ์ด๋ก , ์ž๋ฃŒ ๊ตฌ์กฐ, ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ ๋ฌธ์ œ ์„ค๋ช…๋™ํ˜์ด๋Š” ์นœ๊ตฌ๋“ค๊ณผ ํ•จ๊ป˜ ์—ฌํ–‰์„ ๊ฐ€๋ ค๊ณ  ํ•œ๋‹ค. ํ•œ๊ตญ์—๋Š” ๋„์‹œ๊ฐ€ N๊ฐœ ์žˆ๊ณ  ์ž„์˜์˜ ๋‘ ๋„์‹œ ์‚ฌ์ด์— ๊ธธ์ด ์žˆ์„ ์ˆ˜๋„, ์—†์„ ์ˆ˜๋„ ์žˆ๋‹ค. ๋™ํ˜์ด์˜ ์—ฌํ–‰ ์ผ์ •์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์—ฌํ–‰ ๊ฒฝ๋กœ๊ฐ€ ๊ฐ€๋Šฅํ•œ ๊ฒƒ์ธ์ง€ ์•Œ์•„๋ณด์ž. ๋ฌผ๋ก  ์ค‘๊ฐ„์— ๋‹ค๋ฅธ ๋„์‹œ๋ฅผ ๊ฒฝ์œ ํ•ด์„œ ์—ฌํ–‰์„ ํ•  ์ˆ˜๋„ ์žˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋„์‹œ๊ฐ€ 5๊ฐœ ์žˆ๊ณ , A-B, B-C, A-D, B-D, E-A์˜ ๊ธธ์ด ์žˆ๊ณ , ๋™ํ˜์ด์˜ ์—ฌํ–‰ ๊ณ„ํš์ด E C B C D ๋ผ๋ฉด E-A-B-C-B-C-B-D๋ผ๋Š” ์—ฌํ–‰๊ฒฝ๋กœ๋ฅผ ํ†ตํ•ด ๋ชฉ์ ์„ ๋‹ฌ์„ฑํ•  ์ˆ˜ ์žˆ๋‹ค.๋„์‹œ๋“ค์˜ ๊ฐœ์ˆ˜์™€ ๋„์‹œ๋“ค ๊ฐ„์˜ ์—ฐ๊ฒฐ ์—ฌ๋ถ€๊ฐ€ ์ฃผ์–ด์ ธ ์žˆ๊ณ , ๋™..
[๋ฐฑ์ค€] 1717. ์ง‘ํ•ฉ์˜ ํ‘œํ˜„/Python - Gold5
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1717์„ฑ๋Šฅ ์š”์•ฝ๋ฉ”๋ชจ๋ฆฌ: 77876 KB, ์‹œ๊ฐ„: 284 ms๋ถ„๋ฅ˜์ž๋ฃŒ ๊ตฌ์กฐ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ๋ฌธ์ œ ์„ค๋ช…์ดˆ๊ธฐ์— n+1n+1๊ฐœ์˜ ์ง‘ํ•ฉ {0},{1},{2},…,{n}{0},{1},{2},…,{n}์ด ์žˆ๋‹ค. ์—ฌ๊ธฐ์— ํ•ฉ์ง‘ํ•ฉ ์—ฐ์‚ฐ๊ณผ, ๋‘ ์›์†Œ๊ฐ€ ๊ฐ™์€ ์ง‘ํ•ฉ์— ํฌํ•จ๋˜์–ด ์žˆ๋Š”์ง€๋ฅผ ํ™•์ธํ•˜๋Š” ์—ฐ์‚ฐ์„ ์ˆ˜ํ–‰ํ•˜๋ ค๊ณ  ํ•œ๋‹ค.์ง‘ํ•ฉ์„ ํ‘œํ˜„ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.โœ๐Ÿปํ’€์ดhttps://yoongrammer.tistory.com/102 ์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set) & ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ(Union find)๋ชฉ์ฐจ์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set) & ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ(Union find)์„œ๋กœ์†Œ ์ง‘ํ•ฉ(Disjoint Set)Disjoint Set(์„œ๋กœ์†Œ ์ง‘ํ•ฉ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ)์ด๋ž€ ์„œ๋กœ..
[๋ฐฑ์ค€] 1197. ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ/Python - Gold4
ยท
Coding Test/Algorithms
โ“๋ฌธ์ œhttps://www.acmicpc.net/problem/1197์„ฑ๋Šฅ ์š”์•ฝKruskal, Python3โžก๏ธ๋ฉ”๋ชจ๋ฆฌ: 57288 KB, ์‹œ๊ฐ„: 264 msPrim, PyPy3โžก๏ธ๋ฉ”๋ชจ๋ฆฌ: 129144 KB, ์‹œ๊ฐ„: 380 ms๋ถ„๋ฅ˜์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ, ๊ทธ๋ž˜ํ”„ ์ด๋ก ๋ฌธ์ œ ์„ค๋ช…๊ทธ๋ž˜ํ”„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ทธ ๊ทธ๋ž˜ํ”„์˜ ์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.์ตœ์†Œ ์ŠคํŒจ๋‹ ํŠธ๋ฆฌ๋Š”, ์ฃผ์–ด์ง„ ๊ทธ๋ž˜ํ”„์˜ ๋ชจ๋“  ์ •์ ๋“ค์„ ์—ฐ๊ฒฐํ•˜๋Š” ๋ถ€๋ถ„ ๊ทธ๋ž˜ํ”„ ์ค‘์—์„œ ๊ทธ ๊ฐ€์ค‘์น˜์˜ ํ•ฉ์ด ์ตœ์†Œ์ธ ํŠธ๋ฆฌ๋ฅผ ๋งํ•œ๋‹ค.โœ๐Ÿปํ’€์ด2024.11.29 - [Computer Science/Algorithms] - [Algorithms] ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ (Minimum Spanning Tree) [Algorithms] ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ (Minimum Spannin..