Back to : cp-rounds

์ด ๊ธ€์€ ์˜ฌํ•ด ํ•ด์‹œ์ฝ”๋“œ๋ฅผ ์ค€๋น„ํ•˜๋Š” ๊ณผ์ • ๋“ฑ์— ๋Œ€ํ•œ ์ด์•ผ๊ธฐ์ด๊ณ , ํ•ด์‹œ์ฝ”๋“œ 2021์— Specificํ•œ (๋ฌธ์ œ ๋“ฑ) ์€ ๋‹ค์Œ ๊ธ€(๋งํฌ์—์„œ ๋‹ค๋ฃน๋‹ˆ๋‹ค.

๋‚ด๋…„์— ํ•ด์‹œ์ฝ”๋“œ๋ฅผ ์ค€๋น„ํ•˜๋ ค๋Š” ๋ถ„๋“ค์ด ์ฝ์—ˆ์„๋•Œ ์žฌ๋ฐŒ๊ฒŒ ์“ฐ๊ณ  ์‹ถ์—ˆ๋Š”๋ฐ ์–ด๋–ค์ง€ ๋ชจ๋ฅด๊ฒ ๋„ค์š”. :(

Contents

Google Hashcode

Google Hashcode๋Š” ๊ตฌ๊ธ€์—์„œ ๊ฐœ์ตœํ•˜๋Š” Coding competition ์ค‘ ์ตœ์ ํ™”์™€ ํœด๋ฆฌ์Šคํ‹ฑ์„ ๊ฒจ๋ฃจ๋Š” ๋Œ€ํšŒ์ž…๋‹ˆ๋‹ค. NPํ•œ ๋ฌธ์ œ๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ์ด ๋ฌธ์ œ์— ๋Œ€ํ•ด ์ข‹์€ ํœด๋ฆฌ์Šคํ‹ฑ๊ณผ ์ ์ ˆํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์  ์ตœ์ ํ™”๋ฅผ ํ†ตํ•ด ์ฃผ์–ด์ง„ ๋ฐ์ดํ„ฐ์…‹์—์„œ ์ข‹์€ ์ ์ˆ˜๋ฅผ ๋ฐ›๋Š” ๊ฒฝ์Ÿ์ธ๋ฐ, ๋ชจ๋“  ๋ฐ์ดํ„ฐ์…‹์ด ๊ณต๊ฐœ๋˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ์ดํ„ฐ์…‹์˜ ์„ฑ์งˆ์„ ์ž˜ ํ™œ์šฉํ•œ๋‹ค๊ฑฐ๋‚˜ ํ•˜๋Š”, Data scienceํ‹ฑํ•œ ๋ฉด์ด ์กฐ๊ธˆ ์žˆ๋‹ค๊ณ ๋„ ํ•  ์ˆ˜ ์žˆ๊ฒ ์Šต๋‹ˆ๋‹ค.

์ด๋Ÿฐ ํ˜•ํƒœ์˜ ๋Œ€ํšŒ๋Š” ๊ธฐ์กด์˜ PS์™€๋Š” ๋˜ ๋‹ค๋ฅด์ง€๋งŒ, ํ•„์š”ํ•œ ์Šคํ‚ฌ์…‹์€ ์–ด๋Š์ •๋„ ๋น„์Šทํ•˜๊ณ , ์ตœ์ƒ์œ„๊ถŒ ๋ ˆ๋ฒจ์—์„œ๋Š” ๊ธฐ์กด PS ์Šค๋Ÿฌ์šด ํ…Œํฌ๋‹‰๋“ค์ด ์œ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค. PS ์‹ค๋ ฅ๊ณผ ๋งค์šฐ ๋†’์€ ์ƒ๊ด€๊ด€๊ณ„๊ฐ€ ์žˆ์ง€๋งŒ, Hashcode ํ˜• ๋Œ€ํšŒ์— ํŠนํžˆ ๊ฐ•ํ•œ ํŒ€๋“ค๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฌธ์ œ๊ฐ€ ์ƒ๋‹นํžˆ Real-world ์Šค๋Ÿฝ๊ฒŒ ์ถœ์ œ๋˜๋ฉฐ, ์‹ค์ œ๋กœ Google Loon ๊ฐ™์€ ๊ตฌ๊ธ€์˜ product์™€ ๊นŠ์€ ์—ฐ๊ด€์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๋‹ค ๋ณด๋ฉด ๋ญ”๊ฐ€ ์ง„์งœ ์‹ค์ œ๋กœ ์œ ์˜๋ฏธํ•œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋Š๋‚Œ์„ ๋ฐ›๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค.

Team Little Piplup

์ด ํŒ€์€ 2019๋…„๋„ ICPC๋ฅผ ๊ธฐ์ ์œผ๋กœ ์ €์™€ Coffeetea, DHDroid ๋กœ ์ถœ๋ฐœํ–ˆ์Šต๋‹ˆ๋‹ค. ์ดํ›„ ๋‘ ์‚ฌ๋žŒ์ด ๋ณ‘์—ญํŠน๋ก€๋ฅผ ์œ„ํ•ด ํœดํ•™์„ ํ•˜๊ฒŒ ๋˜์—ˆ๋Š”๋ฐ, ํœดํ•™์ƒ์€ ICPC ๋ณธ์„  ์ถœ์ „๊ถŒ์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ œ๊ฐ€ ๋‹ค๋ฅธ ํŒ€์„ ์ฐพ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. (๊ฒฐ๊ณผ์ ์œผ๋กœ, ์„œ์šธ๋Œ€์—์„œ ๋ณธ์„ ์— ์ง„์ถœํ•˜๋Š” ๋‚œ์ด๋„๋ฅผ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ๋ณ„๋กœ ๊ทธ๋Ÿด ํ•„์š”๊ฐ€ ์—†์—ˆ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค๊ธฐ๋„ ํ•ฉ๋‹ˆ๋‹ค๋งŒโ€ฆ) 2020๋…„๋ถ€ํ„ฐ ๊ทธ ์ž๋ฆฌ๋Š” ๋ณ‘ํŠน์ค‘์ด์—ˆ๊ณ  ์ €๋ž‘ ๊ณ„์† PS๋ฅผ ๊ฐ™์ด ๊ณต๋ถ€ํ–ˆ๋˜ Dlwocks31 ์ด ๋“ค์–ด๊ฐ€๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

Dlwocks31์ด ๋“ค์–ด๊ฐ„ ์‹œ์ ์˜ ํŒ€๋ช…์€ Army Piplup์œผ๋กœ ๊ฐœ์นญ๋˜์—ˆ๊ณ , 2020 ICPC ์˜ˆ์„ ์—์„œ 11๋“ฑ์„ ๊ฑฐ๋‘๋Š” ๋†€๋ผ์šด ์‹ค๋ ฅ์„ ๋ณด์—ฌ์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค. ์ฝ”๋“œํฌ์Šค ๋ ˆ์ดํŒ… (Max)๋ฅผ ๊ธฐ์ค€์œผ๋กœ dlwocks๋Š” 2200++, ์ €๋Š” 2100, Coffeetea์™€ DHDroid๋Š” 1900์ธ๋ฐ dlwocks31์€ ๋ชฐ๋ผ๋„ ์ €๋Š” ๊ฑฐํ’ˆ๋ ˆ์ดํŒ…์ด์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ฑฐํ’ˆ์ด ๊บผ์ง„ ์ง€๊ธˆ์€ 1900 ์ •๋„, ์ž˜์ณ์ฃผ๋ฉด ํผํ”Œ ์ค‘๊ฐ„์ฏค์˜ CP ์‹ค๋ ฅ์„ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๋ณด์ž…๋‹ˆ๋‹ค.

  • Gratus907 : ์ˆ˜ํ•™์ ์ธ ๋ฌธ์ œ์— ๋น„๊ต์  ๊ฐ•ํ•˜๊ณ , ๋ง๋ฆฌ์ง€ ์•Š์„๋•Œ๊นŒ์ง€๋Š” ๊ตฌํ˜„์ด ๋น ๋ฅด์ง€๋งŒ ๋ง๋ฆฌ๋ฉด ํ•œ์—†์ด ๋ง๋ฆฌ๋Š” ๊ฒฝํ–ฅ์ด ์žˆ์Šต๋‹ˆ๋‹ค.
  • Dlwocks31 : ๊ฐ€์žฅ C++ ๊ตฌํ˜„์„ ๊น”๋”ํ•˜๊ฒŒ ์ž˜ ํ•˜๊ณ , ๊ตฌํ˜„์—์„œ ๋œ ๋ง๋ฆฌ๋Š” ํŽธ์ž…๋‹ˆ๋‹ค.
  • DHDroid : Constructiveํ•œ ๋ฌธ์ œ์— ๋งค์šฐ ๊ฐ•ํ•˜๊ณ , ๊ด€์ฐฐ์„ ์ •๋‹นํ™” (์ฆ๋ช…) ํ•˜๋Š” ๋Šฅ๋ ฅ์ด ๋›ฐ์–ด๋‚ฉ๋‹ˆ๋‹ค.
  • Coffeetea : ๊ทธ๋ฆฌ๋””ํ•˜๊ฑฐ๋‚˜ ํœด๋ฆฌ์Šคํ‹ฑํ•œ ๊ด€์ฐฐ, ๋Œ€๋žต์ ์ธ ๊ฒฝํ–ฅ์„ฑ์˜ ํŒŒ์•…์— ๊ฐ•ํ•ฉ๋‹ˆ๋‹ค. ๋ญ”๊ฐ€ ๋ฌธ์ œ์— ๋น™์˜ํ•˜๋Š” ํŠน์„ฑ์ด ์žˆ์–ด์„œ ๊ธ€์“ธ๋•Œ Coffeetea์˜ ํ‘œํ˜„์„ ๋งŽ์ด ๋นŒ๋ฆฌ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค :)

Preperation

Hashcode ๋Œ€ํšŒ๋ฅผ ์ค€๋น„ํ•˜๊ธฐ ์œ„ํ•ด์„œ ์˜ฌํ•ด๋Š” ๋งŽ์€ ๋…ธ๋ ฅ์„ ๊ธฐ์šธ์ด์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ์ž‘๋…„์—๋Š” ๋น„๊ต์  ๋งŽ์€ ๋…ธ๋ ฅ์„ ํ–ˆ๋Š”๋ฐ, ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๊ตํ›ˆ์„ ์–ป์—ˆ์Šต๋‹ˆ๋‹ค. ์ž‘๋…„ ๋Œ€ํšŒ ํ›„๊ธฐ๋Š” ์ œ ํ‹ฐ์Šคํ† ๋ฆฌ ๋ธ”๋กœ๊ทธ์—์„œ(๋งํฌ) ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • ๋ฌธ์ œ์˜ ๊ตฌํ˜„๋Ÿ‰์ด ์ƒ๋‹นํžˆ ๋งŽ์•„์„œ, ๊ตฌํ˜„์—์„œ ๋ง๋ฆฌ๋ฉด ์ƒ๋‹นํžˆ ํž˜๋“ญ๋‹ˆ๋‹ค. ๊ธฐ๋ณธ์ ์œผ๋กœ dlwocks31์ด ๊ตฌํ˜„์ด ๊ฐ€์žฅ ๋œ ๋ง๋ฆฌ๋‹ˆ๊นŒ ์ „์ฒด์ ์ธ ๊ตฌํ˜„์„ ๋งก๋˜, ํ•„์š”ํ•˜๋‹ค๋ฉด ์–ธ์ œ๋“  ๊ตฌํ˜„์— ์ €๋‚˜ ๋‹ค๋ฅธ ํŒ€์›๋“ค์ด ์ฐธ์—ฌํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • Parameter Tuning์ด ๋งŽ์€ ๋„์›€์ด ๋ฉ๋‹ˆ๋‹ค. ํŒŒ์ธ ํŠœ๋‹์„ ์ž๋™ํ™”ํ•˜๋Š” ์ฝ”๋“œ๋ฅผ ๋ฏธ๋ฆฌ ์ค€๋น„ํ–ˆ๋Š”๋ฐ, ์ด๋ฅผ ์œ„ํ•ด์„œ๋Š” ์‹ ์†ํ•˜๊ณ  ์ •ํ™•ํ•˜๊ฒŒ ์ฑ„์ ์„ ๋ฐ›๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
    • ์ฑ„์ ์„ ์›น ํ™˜๊ฒฝ์—์„œ ์ œ์ถœํ•˜๋Š” ๋ฐ ๋งŽ์€ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฝ๋‹ˆ๋‹ค. ์ด๋Š” ์ƒ๋‹นํžˆ ๋ถˆํŽธํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์ฑ„์ ๊ธฐ๋ฅผ ์งœ๋Š” ๊ฒƒ์ด ์˜๋ฏธ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ์ฑ„์ ๊ธฐ๋ฅผ ์ž‘์„ฑํ•˜๋Š” ๊ฒƒ์˜ ๋‹จ์ ์€ ๋‹น์—ฐํ•˜๊ฒŒ๋„ 4์‹œ๊ฐ„์ด๋ผ๋Š” ์งง์€ ๋Œ€ํšŒ์‹œ๊ฐ„์—์„œ ํ•œ๋ช…์ด ๋น ์ ธ์„œ 1์‹œ๊ฐ„์ •๋„๋ฅผ ์ฑ„์ ๊ธฐ์— ์จ์•ผ ํ•œ๋‹ค๋Š” ์ ์ž…๋‹ˆ๋‹ค.
    • ๊ทธ๋Ÿผ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ , ์ฑ„์ ๊ธฐ ์ž‘์„ฑ์„ ํ†ตํ•ด ๋ฌธ์ œ ์ƒํ™ฉ์„ ์ข€๋” ๊นŠ์ด ์ดํ•ดํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์ , ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์ฑ„์ ๊ธฐ์˜ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๊ฐ™์€ ๋ถ€๋ถ„๋“ค์€ ๋ณธ ์†”๋ฃจ์…˜์—์„œ๋„ ์‘์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์ ์ด ์žˆ์–ด์„œ ๊ณ ๋ คํ• ๋งŒ ํ•ฉ๋‹ˆ๋‹ค.
  • ๊ฒฐ๊ตญ ์ƒ์œ„๊ถŒ(5-10%)์—์„œ ์ตœ์ƒ์œ„๊ถŒ(1%)์„ ๊ฒฐ์ •ํ•˜๋Š” ๊ฒƒ์€, (์ž‘๋…„์—๋Š”) ์—”๋“œ์ŠคํŽ™๊ธ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ตœ์ ํ™”์˜€์Šต๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ๋Š”, ํŠน์ • ๋ฐ์ดํ„ฐ์˜ ๊ฒฝ์šฐ ์ ์ ˆํ•œ ํ™˜์›์„ ํ†ตํ•ด 3-SAT ๊ฐ™์€ ๋ฌธ์ œ๋กœ ๋ฐ”๊ฟ€ ์ˆ˜ ์žˆ์—ˆ๊ณ , ์ด๋ฅผ ์ ์ ˆํ•œ 3SAT ์†”๋ฒ„์— ๋จน์—ฌ์„œ ๋‹ต์„ ๊ตฌํ•œ๋‹ค๊ฑฐ๋‚˜, greedy ๋Œ€์‹  MCMF๋ฅผ ์“ด๋‹ค๋˜๊ฐ€ ํ•˜๋Š” ์†”๋ฃจ์…˜๋“ค์ด ์ตœ์ƒ์œ„๊ถŒ์„ ๊ฒจ๋ฃจ์—ˆ์Šต๋‹ˆ๋‹ค. ๋‹ค์‹œ ๊ฐ™์€ ์ตœ์ƒ์œ„๊ถŒ ๋‚ด์—์„œ๋Š” Parameter Tuning์ด ์„ธ๋ถ€๋“ฑ์ˆ˜๋ฅผ ๊ฒฐ์ •ํ•ฉ๋‹ˆ๋‹ค.
    • ๊ทธ๋ž˜์„œ, ์ด๋ฒˆ์—๋Š” ์ƒ์šฉ NP-Complete Solver๋“ค์„ ์ค€๋น„ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋Ÿฐ์ชฝ์— ๋น„๊ต์  ์ œ๊ฐ€ ์กฐ๊ธˆ๋” ํ•ด๋ณธ๊ฒŒ ๋งŽ๊ธฐ ๋•Œ๋ฌธ์—, ์ด๊ฒƒ์ €๊ฒƒ ์ฐพ์•„ ๋ชจ์œผ๊ณ , ์ œ ์ตœ๋Œ€์˜ ๋ชฉํ‘œ๋Š” ์ด๊ฑฐ ์‚ฌ์‹ค 3SAT์ธ๋ฐ ๋ฅผ ์ฐพ๋Š” ๊ฒƒ์ด๋ผ๊ณ  ์Šค์Šค๋กœ ์ƒ๊ฐํ–ˆ์Šต๋‹ˆ๋‹ค. (๊ฒฐ๊ตญ ํ‹€๋ ธ์Šต๋‹ˆ๋‹ค)
    • Glucose SAT Solver, Concorde TSP Solver, Google ORTools(LP, Flow, IP) ์ •๋„๋Š” ์„ธํŒ…๋˜์–ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.
  • ์ƒ๊ฐ๋ณด๋‹ค ๋†’์€ Computation power๊ฐ€ ํ•„์š”ํ•œ ๊ฒฝ์šฐ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ํŒ€์› ์ „์›์ด i7๊ธ‰ ์ด์ƒ์˜ ๋…ธํŠธ๋ถ์„ ์‚ฌ์šฉํ–ˆ์œผ๋ฉฐ ํ•„์š”ํ• ๋•Œ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” i7๊ธ‰ ๋ฐ์Šคํฌํƒ‘ 2๋Œ€๊ฐ€ ์„ธํŒ…๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์นด์นด์˜ค ํด๋ผ์šฐ๋“œ, ๋„ค์ด๋ฒ„ ํด๋ผ์šฐ๋“œ ๋“ฑ์ด ์ค€๋น„๋˜์–ด์žˆ์—ˆ๋˜ ๋‹ค๋ฅธ ํŒ€์— ๋น„ํ•˜๋ฉด ๋ถ€์กฑํ• ์ง€๋„ ๋ชจ๋ฅด์ง€๋งŒ ์ €ํฌ๊ฐ€ ํ™•๋ณดํ•  ์ˆ˜ ์žˆ๋Š” ์ปดํ“จํŒ… ํŒŒ์›Œ๋Š” ๋‚˜์˜์ง€ ์•Š์•˜๊ณ , ๊ฒฐ๊ตญ ๊ทธ ๋ฌด์—‡๋„ ํ•„์š” ์—†์—ˆ์Šต๋‹ˆ๋‹ค.

์ „๋žต

  1. ์ฒซ 1์‹œ๊ฐ„ ์ •๋„, ์ œ๊ฐ€ Grader๋ฅผ ์งœ๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค.
  2. ๊ทธ๋™์•ˆ, DHDroid์™€ Coffeetea๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ๋ถ„์„ํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๊ทธ๋ž˜ํ”„ ๋ฐ์ดํ„ฐ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค๋ฉด, ๋ช‡๊ฐœ์˜ ํ—ˆ๋ธŒ๊ฐ€ ์กด์žฌํ•˜๋Š” ๋ฐ์ดํ„ฐ์ธ์ง€, Degree-bounded์ธ์ง€ ๋“ฑ์˜ ์ •๋ณด๊ฐ€ ์žˆ์œผ๋ฉด ์ผ๋ฐ˜์ ์ธ ๊ทธ๋ž˜ํ”„์—์„œ๋Š” ์ƒ์ƒ๋„ ๋ชปํ•  ๊ฒƒ๋“ค์ด ๊ฐ€๋Šฅํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ด๋Ÿฐ ์ •๋ณด๋Š” ์ •๋ง ํ•„์ˆ˜์ ์ž…๋‹ˆ๋‹ค. ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์ด ๋‘๋ช…์ด ์–ด๋Š์ •๋„์˜ ๊ทธ๋ฆฌ๋””ํ•œ ์†”๋ฃจ์…˜์„ ์ œ๊ณตํ•ด ์ค„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. Grader ์ž‘์„ฑ์€ ๊ทธ๋ƒฅ ๊นก ์‹œ๋ฎฌ์ด๊ธฐ ๋•Œ๋ฌธ์—, ์ด ๋‘๋ช…์˜ ๋…ผ์˜๋ฅผ ์ œ๊ฐ€ ์–ด๋Š์ •๋„ ๋“ค์œผ๋ฉด์„œ ์งค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค,
  3. Dlwocks31์ด ์ด๋•Œ ํŠœ๋‹๊ฐ€๋Šฅํ•œ ์ œ๋„ค๋ฆญ ์†”๋ฃจ์…˜์„ ์ž‘์„ฑํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด ์ฝ”๋“œ๋Š” ๋‚˜์ค‘์— ๊ฐ™์ด ๋Œ์•„๊ฐ€๋ฉด์„œ ๊ณ ์น˜๊ณ  ํŠœ๋‹ํ•ด์•ผ ํ•˜๋ฏ€๋กœ, ๋น„๊ต์  ์ฝ๊ธฐ ์‰ฝ๊ฒŒ ์งœ์•ผ ํ•˜๊ณ , IO๊ฐ™์€ (๋‹ค๋ฅธ ์‚ฌ๋žŒ๋“ค์ด ๋ชฐ๋ผ๋„ ๋˜๋Š”) ๋ถ€๋ถ„๋“ค์„ ๋ถ„๋ฆฌํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค.
  4. ์ดํ›„ 2-3์‹œ๊ฐ„ ๋™์•ˆ, ๋„ค๋ช…์ด ๊ฐ™์ด ์†”๋ฃจ์…˜์„ ์žก์œผ๋ฉด์„œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ์„ ๊ณผ ํŒŒ๋ผ๋ฏธํ„ฐ ํŠœ๋‹์„ ๋ฐ˜๋ณตํ•˜๋ฉฐ ๊ณ„์† ์ œ์ถœํ•˜๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

์ „๋ฐ˜์ ์œผ๋กœ ์ฒซ 1์‹œ๊ฐ„๋™์•ˆ ์ €๋ž‘ dlwocks31์˜ ์ฝ”๋”ฉ์‹ค๋ ฅ์— ์กฐ๊ธˆ ์˜์กดํ•˜๋Š” ๊ฐ์ด ์žˆ์Šต๋‹ˆ๋‹ค๋งŒ, ์ €ํฌ๊ฐ€ ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ์„ ์ด์—ˆ๊ณ  ์ง€๋‚œ ๋ช‡๋…„์น˜ ์˜ˆ์„ ์„ ํ’€์–ด๋ดค์„ ๋•Œ๋Š” ๋ง์ด ๋˜๋Š” ์ „๋žต์ด์—ˆ์Šต๋‹ˆ๋‹ค. ์ด์ •๋„ ๋ณต์žก๋„์˜ ๊ตฌํ˜„์€ ์ €ํฌ ๋‘˜์€ ์–ด๋–ป๊ฒŒ๋“  ๊ฐ€๋Šฅํ•˜๊ธด ํ–ˆ์—ˆ๊ณ , ํ‰์†Œ PS๋•Œ์™€๋Š” ๋‹ฌ๋ฆฌ 1์ดˆ์˜ Strict time limit์ด ์—†์œผ๋ฏ€๋กœ set, map ๊ฐ™์€ ๊ฒƒ๋“ค์„ ๋งˆ๊ตฌ ๋‚จ์šฉํ•˜๋ฉฐ ์งœ๋„ ๋˜๊ธด ํ•ฉ๋‹ˆ๋‹ค.

์ด ์ „๋žต์€ ์˜ฌํ•ด ํ•ด์‹œ์ฝ”๋“œ์—์„œ ํ•œ๊ณ„์— ๋ถ€๋”ชํžˆ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

์ž‘๋…„ ํŒ€์—ฐ์Šต๋“ค

๋ช‡๋ช‡ ํ•ด์‹œ์ฝ”๋“œ ์˜ˆ์„  ๋ฌธ์ œ๋ฅผ ์ž‘๋…„์— ๊ฐ™์ด ํ’€์–ด๋ณด์•˜์—ˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋•Œ ์œ„ 1-4 ์ „๋žต๋„ ์ •๋ฆฝํ–ˆ๋Š”๋ฐ, ๋ช‡๊ฐ€์ง€ ์ „๋žต์ ์ธ ํŠœ๋‹๋„ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

  1. ๋ฌธ์ œ์˜ ๊ตฌํ˜„ ๋ณต์žก๋„๊ฐ€ ๋†’๋‹ค๋ฉด, ์ฒด์ปค๋ฅผ ์งœ๋Š” ๊ฒƒ์€ ๋ณ„๋กœ ๋ฐ”๋žŒ์งํ•˜์ง€ ๋ชปํ•ฉ๋‹ˆ๋‹ค. ์ด๊ฑด 2016 Qual๋ผ์šด๋“œ์˜ DRONE์ด๋ผ๋Š” ๋ฌธ์ œ์—์„œ ๋Š๊ผˆ์Šต๋‹ˆ๋‹ค. ํ•ด์‹œ์ฝ”๋“œ๋ฅผ ์ค€๋น„ํ•œ๋‹ค๋ฉด ๊ผญ ํ’€์–ด๋ณด๊ธธ ๋ฐ”๋ž๋‹ˆ๋‹ค.
    ๋ฐ˜๋ฉด, ๊ตฌํ˜„ ๋ณต์žก๋„๋Š” ์ ์ ˆํ•œ๋ฐ Simulated annealing๊ฐ™์€๊ฑธ ๋ฐ•์„์ˆ˜์žˆ๋Š” ๋ฌธ์ œ๋ผ๋ฉด ๋ฌด์กฐ๊ฑด ์ฒด์ปค๋ฅผ ์งœ์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  2. ์–ด๋–ค ๋ฌธ์ œ๋Š”, ์•„์˜ˆ ๋…๋ฆฝ์ ์ธ ๋‘๊ฐœ์ด์ƒ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์š”๊ตฌํ•œ๋‹ค๋Š” ์‚ฌ์‹ค์„ ์•Œ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๊ทธ๋ž˜ํ”„ ๋ฌธ์ œ์—์„œ ์–ด๋–ค ๋ฐ์ดํ„ฐ๋Š” Deg-bounded๊ณ  ์–ด๋–ค ๋ฐ์ดํ„ฐ๋Š” ๋‹ค์„ฏ๊ฐœ์˜ ํ—ˆ๋ธŒ์™€ 9995๊ฐœ์˜ ๊ฐ€์ง€์ •์ ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค๋ฉด, ๋‘ ๋ฌธ์ œ๋Š” ์‚ฌ์‹ค ์•„์˜ˆ ๋‹ค๋ฅธ ๋ฌธ์ œ์ด๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์ด๊ฒฝ์šฐ ๊ตฌํ˜„ํŽ˜์ด์ฆˆ๊ฐ€ n๋ฐฐ ํž˜๋“ค์–ด์ง€๋Š”๋ฐ, ์ด๋ฅผ ๋น ๋ฅด๊ฒŒ ํŒŒ์•…ํ•ด์•ผ ํ•˜๋ฏ€๋กœ ๋‘๋ช…์ด ๋ฐ์ดํ„ฐ๋ฅผ ์ƒ๊ฐ๋ณด๋‹ค ๋งŽ์ด ๋ถ„์„ํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒฐ๋ก ์„ ๋‚ด๋ ธ์Šต๋‹ˆ๋‹ค. ๊ตฌํ˜„์ด ์•„๋‹Œ ๋ฐ์ดํ„ฐ ๋ถ„์„์— 2๋ช…์„ ๋ฐฐ์ •ํ•œ ์ด์œ ๊ฐ€ ์—ฌ๊ธฐ ์žˆ์Šต๋‹ˆ๋‹ค.
  3. ์ด๋ฅผ ์œ„ํ•ด dlwocks31์ด ๊ตฌํ˜„์„ ์ •๋ง ์ตœ๋Œ€ํ•œ ์ œ๋„ค๋ฆญํ•˜๊ฒŒ ์งœ์•ผ ํ•จ์„ ๊นจ๋‹ฌ์•˜์Šต๋‹ˆ๋‹ค.

ํŒ€์—ฐ์Šต : 2020 Hashcode WF

๊ฐ€์žฅ ์ข‹์€ ํ•ด์‹œ์ฝ”๋“œ ์—ฐ์Šต์…‹์€ ํ•ด์‹œ์ฝ”๋“œ๊ธฐ ๋•Œ๋ฌธ์—, ์ž‘๋…„ ํ•ด์‹œ์ฝ”๋“œ ์›”ํŒŒ๋ฅผ ๊ฐ™์ด ๋Œ์•˜์Šต๋‹ˆ๋‹ค. ์ •๋ง ์ถฉ๊ฒฉ์ ์ธ ๋‚œ์ด๋„์˜ ๋ฌธ์ œ๋กœ ์ธํ•ด ์ €ํฌ ์ „๋žต์˜ ํ•œ๊ณ„๊ฐ€ ๋Š๊ปด์กŒ์Šต๋‹ˆ๋‹ค.

๋Œ€์ถฉ ์–˜๊ธฐํ•˜์ž๋ฉด ์ •๋ง ๋นก์„ผ ๊ตฌํ˜„ ๋ฌธ์ œ์˜€๊ณ , ๋Œ€์ถฉ ์‹œ๋ฎฌ๋ ˆ์ด์…˜๋งŒ ์„ฑ๊ณตํ•ด๋„ ์›”ํŒŒ ์ค‘๊ฐ„์ฏค์˜ ์ ์ˆ˜๊ฐ€ ๋‚˜์˜ค๋Š” ๋ฏธ์นœ ์…‹์ด์—ˆ์Šต๋‹ˆ๋‹ค. ์œ„ ์ „๋žต์ด ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์‹คํŒจํ–ˆ์Šต๋‹ˆ๋‹ค.

  1. ํŒ€์—ฐ์Šต๋•Œ๋Š” ์˜จ๋ผ์ธ ์ฑ„์ ์„ ๋ฐ›์„ ์ˆ˜ ์—†์œผ๋ฏ€๋กœ, ํ•œ๋ช…์„ ์ง€์ •ํ•ด์„œ ํ•œ๋ช…์ด ๋ฏธ๋ฆฌ ์ฒด์ปค๋ฅผ ์งœ ์˜ต๋‹ˆ๋‹ค. ์ œ๊ฐ€ ์ฒด์ปค๋ฅผ ์งœ ์™”๋Š”๋ฐ, ์ง‘์—์„œ ํ˜ผ์ž ์ฒด์ปค๋ฅผ ์งœ๋Š”๋ฐ ์ผ๋‹จ 1์‹œ๊ฐ„๋ณด๋‹ค ํ›จ์”ฌ ์˜ค๋ž˜๊ฑธ๋ ธ๊ณ , ์ •ํ™•์„ฑ๋„ ๋ณ„๋กœ ๋ณด์žฅ๋˜์ง€ ์•Š์•˜์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜๋„ ๊ทธ๋Ÿญ์ €๋Ÿญ ๋ง์ด ๋˜๋Š” ๊ฒƒ ๊ฐ™์•˜๋Š”๋ฐ ๋ญ ์ด๋ถ€๋ถ„์€ ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค. ์ค‘์š”ํ•œ ๊ฒƒ์€ ์ฒด์ปค๋ฅผ 1์‹œ๊ฐ„ ๋‚ด๋กœ ์งœ์ง€ ๋ชปํ–ˆ๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  2. ๋ฐ์ดํ„ฐ๋ฅผ ๋ถ„์„ํ•˜๊ณ  ๊ทธ๋ฆฌ๋””๋ฅผ ๋– ์˜ฌ๋ ค์•ผ ํ•˜๋Š”๋ฐ, ๊ทธ๋ฆฌ๋””ํ•˜๊ฒŒ ๋ญ˜ ํ•  ์ˆ˜ ์žˆ์„์ง€๋„ ๋‚œํ•ดํ–ˆ์Šต๋‹ˆ๋‹ค. ์ง€๋‚˜์น˜๊ฒŒ ๊ตฌํ˜„๋‚œ์ด๋„๊ฐ€ ๋†’์•„์„œ, Coffeetea์˜ ์žฅ์ ์„ ์‚ด๋ฆฐ ์•„์ด๋””์–ด๋“ค์ด ์Ÿ์•„์กŒ์ง€๋งŒ ๊ตฌํ˜„๊ฐ€๋Šฅํ•ด ๋ณด์ด๋Š” ์†”๋ฃจ์…˜์ด ์—†์—ˆ์Šต๋‹ˆ๋‹ค.
  3. dlwocks31์ด 1์‹œ๊ฐ„์€์ปค๋…• 2-3์‹œ๊ฐ„์— ๊ฑธ์ณ์„œ๋„ ๊ฐ€๋Šฅํ•œ C++ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๊ฑด blameํ•  ์ผ์€ ์ ˆ๋Œ€ ์•„๋‹Œ๊ฒŒ, ๋‹ค๋ฅธ 3๋ช…์ด ์žก์•˜์œผ๋ฉด ํ•˜๋ฃจ ์ข…์ผ ์งฐ์–ด๋„ ๋ชป ์งฐ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  4. ์†”๋ฃจ์…˜์ด ์—†์œผ๋ฏ€๋กœ ํŠœ๋‹ํ•  ํŒŒ๋ผ๋ฏธํ„ฐ๋„ ๊ฐœ์„ ํ•  ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ• ์ˆ˜๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

2020 WF๋ฅผ ํ’€๋ฉด์„œ, ์ €ํฌ ์ „๋žต์ด dlwocks31์˜ ๊ตฌํ˜„๋ ฅ์— ์–ผ๋งˆ๋‚˜ ์˜์กดํ•˜๋Š”์ง€ ๊นจ๋‹ซ๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค. ๊ฒฝ์šฐ์— ๋”ฐ๋ผ ์ฒด์ปค๋ฅผ ๋˜์ง€๋”๋ผ๋„ ์ด ๊ตฌํ˜„์€ ํ”ผํ•  ์ˆ˜ ์—†๊ณ , ์ด ๊ตฌํ˜„์—์„œ ๋ง๋ฆฌ๋ฉด 0์ ์œผ๋กœ ๋Œ€ํšŒ๋ฅผ ๋งˆ๋ฌด๋ฆฌํ•˜๋Š” ์ฐธ์‚ฌ๊ฐ€ ๋ฒŒ์–ด์ง€๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

ํ•„์š”ํ•˜๋‹ค๋ฉด ๊ตฌํ˜„์„ ๋‚˜๋ˆ„์–ด์•ผ ํ•œ๋‹ค๋Š” ์ง๊ฐ์ด ๋“ค์—ˆ์œผ๋ฏ€๋กœ, ์ฒ˜์Œ์œผ๋กœ ์ด๋Ÿฐ ๋Œ€ํšŒ ์ค‘์—๋„ Git์„ ์ด์šฉํ•˜๊ธฐ๋กœ ํ–ˆ์Šต๋‹ˆ๋‹ค. ์ตœ๋Œ€ํ•œ ๊ฐ™์€ ํŒŒ์ผ์„ ๋™์‹œ์— 2๋ช…์ด ๋งŒ์ง€๋Š” ์ผ์„ ํ”ผํ•˜๋ฉด์„œ, ํ•„์š”ํ•˜๋‹ค๋ฉด ํŒŒ์ผ์„ ๋งŽ์ด ๋Š˜๋ ค์„œ๋ผ๋„ ์ฝ”๋“œ๋ฅผ ์ ์ ˆํžˆ ๊ณต์œ ํ•  ํ•„์š”๊ฐ€ ์žˆ์—ˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค. ์—ฌ๋Ÿฌ ํŒŒ์ผ๋กœ ๋‚˜๋ˆ„์–ด ๊ตฌํ˜„ํ•œ ๋‹ค์Œ ํ•ฉ์น˜๋Š” ๋ฐฉ๋ฒ•์„ ํฌํ•จํ•ด์„œ, ๋ถ€์กฑํ•œ ๊ตฌํ˜„๋ ฅ์„ ์ „๋žต์œผ๋กœ ๋ฉ”์šฐ๊ธฐ ์œ„ํ•œ ๋งŽ์€ ์‹œ๋„๊ฐ€ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.