[์„œํ‰] ์‹ฌ๊ฐํ•œ ํ…Œ๋ผํผ ์ค‘๋…์ž…๋‹ˆ๋‹ค
ยท
ETC
GCP๋ฅผ ์ด์šฉํ•ด์„œ ํ”„๋กœ์ ํŠธ๋ฅผ ํ•˜๊ณ  ํ…Œ๋ผํผ์œผ๋กœ ์˜ฎ๊ฒจ ์ ์œผ๋ฉด์„œ ์‹ค๋ฌด์—์„œ๋Š” ์–ด๋–ป๊ฒŒ ์ž‘์„ฑํ•˜๋Š”์ง€ ๊ณ ๋ฏผ์„ ํ•˜๋‹ค๊ฐ€ ์„œํ‰๋‹จ์— ์ฐธ์—ฌํ•  ๊ธฐํšŒ๊ฐ€ ์ƒ๊ฒจ์„œ ์„œํ‰ ๋‚จ๊น๋‹ˆ๋‹ค๐Ÿค—๐ŸŒŸ์ฑ… ์†Œ๊ฐœ์˜ค๋Š˜ ์„œํ‰์„ ๋‚จ๊ธฐ๊ณ ์ž ํ•˜๋Š” ์ฑ…์€ ์‹ฌ๊ฐํ•œ ํ…Œ๋ผํผ ์ค‘๋…์ž…๋‹ˆ๋‹ค์ž…๋‹ˆ๋‹ค. ์ธํ”„๋ผ ๊ตฌ์ถ• ์‹œ ํ…Œ๋ผํผ์„ ์ด์šฉํ•ด์„œ ๋งŽ์ด ํ•œ๋‹ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํ…Œ๋ผํผ์„ ์‚ฌ์šฉํ•˜๋ฉด ๊ด€๋ฆฌ์— ์šฉ์ดํ•˜๊ณ , ๋ฏธ๋ฆฌ ์˜ค๋ฅ˜๋ฅผ ๋ฐœ๊ฒฌํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.์ด ์ฑ…์€ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ตฌ์„ฑ์„ ๊ฐ–๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค.PART I ์™œ ํ…Œ๋ผํผ์ธ๊ฐ€?PART II ํ…Œ๋ผํผ ๊ธฐ๋ณธPART III ํ…Œ๋ผํผ ๊ธฐ๋Šฅ๋ณ„ ์‹ค๋ฌด ์‚ฌ๋ก€PART IV AWS ๋ชจ๋“ˆ ์‚ฌ๋ก€PART V ๋‹ค์–‘ํ•œ ํ”„๋กœ๋ฐ”์ด๋” ํ™œ์šฉ ์˜ˆ์ œAPPENDIX ํ…Œ๋ผํผ Q&A๐ŸŒŸ์ถ”์ฒœํ•˜๋Š” ๋Œ€์ƒ ๋ฐ ์ด์œ ์ด ์ฑ…์€ ํ…Œ๋ผํผ์„ ์กฐ๊ธˆ์ด๋ผ๋„ ๊ณต๋ถ€ํ•ด๋ณธ ๋ถ„ํ•œํ…Œ ์ถ”์ฒœ๋“œ๋ฆฝ๋‹ˆ๋‹ค. ๋ชฉ์ฐจ์— ํ…Œ๋ผํผ ๊ธฐ๋ณธ์ด๋ผ๊ณ  ๋‚˜์™€์žˆ์ง€๋งŒ ๊ทธ๋ ‡๋‹ค๊ณ  ๊ธฐ๋ณธ..
[๋ฐฑ์ค€] 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(์„œ๋กœ์†Œ ์ง‘ํ•ฉ, ๋ถ„๋ฆฌ ์ง‘ํ•ฉ)์ด๋ž€ ์„œ๋กœ..