Back to : cp-rounds

์ด ๊ธ€์€ ์˜ฌํ•ด ํ•ด์‹œ์ฝ”๋“œ ๋Œ€ํšŒ ๊ณผ์ •์— ๋Œ€ํ•œ ํ›„๊ธฐ์ด๊ณ , ์ค€๋น„ ๊ณผ์ •์€ ์•ž ๊ธ€(๋งํฌ)์— ์žˆ์Šต๋‹ˆ๋‹ค.

Contents

๊ฒฐ๊ณผ

A - An Example       2,000
B - By the Ocean     4,566,842
C - Checkmate        1,300,355
D - Daily Commute    1,574,469
E - Etoile           716,984
F - Forever Jammed   1,417,038
TOTAL SCORE          9,577,688

Global rank #211 / 9,000+ teams

Korea rank #11

๋ฌธ์ œ ์„ค๋ช…

  • ๊ต์ฐจ๋กœ, ๋„๋กœ, ์ฐจ๋Ÿ‰ ๋“ค์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
  • ๋„๋กœ ๋“ค์€ ๊ทธ๋ž˜ํ”„์—์„œ ๋ฐฉํ–ฅ ์žˆ๋Š” ๊ฐ„์„  ์ž…๋‹ˆ๋‹ค. ๊ต์ฐจ๋กœ ์—์„œ ๊ต์ฐจ๋กœ ๋กœ ์ด์–ด์ ธ ์žˆ๊ณ , ๊ธธ์ด ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ต์ฐจ๋กœ ๋Š” ๊ทธ๋ž˜ํ”„์—์„œ ์ •์  ์ž…๋‹ˆ๋‹ค. ๊ต์ฐจ๋กœ์—๋Š” ์‹ ํ˜ธ๋“ฑ ์ด ์žˆ๋Š”๋ฐ, ํŠน์ • ์‹œ์ (์ดˆ)์—๋Š” ์ •ํ™•ํžˆ 1๊ฐœ์˜ incoming edge ์—๋งŒ ์ดˆ๋ก๋ถˆ์ด ์ผœ์ ธ ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • Incoming edge ์— ์ดˆ๋ก๋ถˆ์ด ๋“ค์–ด์™€ ์žˆ๋‹ค๋ฉด, ๊ทธ ๊ต์ฐจ๋กœ์˜ ๊ทธ ๋„๋กœ์— ์„œ ์žˆ๋Š” ์ฐจ๋Ÿ‰๋“ค ์ค‘ 1์ดˆ์— 1๋Œ€์”ฉ๋งŒ ๊ทธ ๊ต์ฐจ๋กœ์—์„œ ์ถœ๋ฐœํ•˜๋Š” ๊ฐ„์„ ๋“ค ์ค‘ ํ•˜๋‚˜๋กœ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ์ฐจ๋Ÿ‰ ๋“ค์€ ๊ฐ€๊ณ  ์‹ถ์€ ๊ฒฝ๋กœ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฒฝ๋กœ๋Š” ๊ฐ„์„ ๋“ค์˜ ์ˆœ์„œ๋กœ ์ฃผ์–ด์ง€๊ณ , ์‹œ์ž‘์ ์€ ์ฒซ ๊ฐ„์„ ์˜ ending intersection์— ์„œ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ฐจ๋Ÿ‰๋“ค์€ 1์ดˆ์— 1์”ฉ ์ด๋™ํ•˜๋Š”๋ฐ, ๊ต์ฐจ๋กœ๋ฅผ ๋งŒ๋‚˜๋ฉด ๋‚ด๊ฐ€ ์ง€๊ธˆ ์„œ ์žˆ๋Š” ๋„๋กœ์˜ ์ดˆ๋ก๋ถˆ์ด ์ผœ์งˆ๋•Œ๊นŒ์ง€ ๊ธฐ๋‹ค๋ฆฝ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ๊ต์ฐจ๋กœ A์—์„œ B๋กœ, B์—์„œ C๋กœ, A์—์„œ C๋กœ, C์—์„œ D๋กœ ๋„๋กœ๊ฐ€ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•ด ๋ด…์‹œ๋‹ค. ์—ฌ๊ธฐ์„œ ์ฐจ๋Ÿ‰ 1์ด A-B์—์„œ ์ถœ๋ฐœ, ์ฐจ๋Ÿ‰ 2๊ฐ€ A-C์—์„œ ์ถœ๋ฐœํ•œ๋‹ค๊ณ  ์ƒ๊ฐํ•ด ๋ด…์‹œ๋‹ค. ์ฐจ๋Ÿ‰ 1์ด B ์•ž์— ์„œ ์žˆ์„ ๋•Œ, B๊ต์ฐจ๋กœ๋Š” (A-B) ๋„๋กœ ์™ธ์˜ ๋‹ค๋ฅธ incoming ๋„๋กœ๊ฐ€ ์—†์œผ๋ฏ€๋กœ ์—ฌ๊ธฐ์— ์ดˆ๋ก๋ถˆ์„ ์ผœ ์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฌ๋ฉด ๊ต์ฐจ๋กœ๋ฅผ ๋ฐ”๋กœ ์ง€๋‚˜์ณ์„œ B-C ๋„๋กœ๋กœ ์˜ฌ๋ผํƒˆ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์œ„ ์˜ˆ์‹œ์—์„œ C ๊ต์ฐจ๋กœ๋Š” B-C ๊ฐ„์„ ๊ณผ A-C ๊ฐ„์„  ๋‘๊ฐœ์˜ endpoint์ž…๋‹ˆ๋‹ค. ์ด๋•Œ, B-C ๊ฐ„์„ ์— ์ดˆ๋ก๋ถˆ์ด ์ผœ ์žˆ๋‹ค๋ฉด, ์•ž์— ์ฐจ๊ฐ€ ์—†๋”๋ผ๋„ A-C ๊ฐ„์„ ์—๋Š” ๋นจ๊ฐ„๋ถˆ์ด ์ผœ ์žˆ์œผ๋ฏ€๋กœ A-C๊ฐ„์„ ์˜ ๋์—์„œ C๊ต์ฐจ๋กœ๋ฅผ ๋ฐ”๋ผ๋ณด๋Š” ์ฐจ๋Ÿ‰์€ ํ†ตํ–‰ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๋˜ํ•œ, ์ฐจ๋“ค์€ ๊ฒน์น˜์ง€ ์•Š๋Š”๋‹ค๋Š” ์ ๋„ (1์ดˆ์— ์ฐจ๋Ÿ‰์€ 1๋Œ€์”ฉ๋งŒ ํ†ตํ–‰ํ•ฉ๋‹ˆ๋‹ค) ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค.

  • ์‹ ํ˜ธ๋“ฑ ์€ ๊ต์ฐจ๋กœ๋งˆ๋‹ค ์„ค์น˜๋˜์–ด ์žˆ๋Š”๋ฐ, incoming edge๋“ค์„ ๋„๋Š” ์‚ฌ์ดํด ํ˜•ํƒœ๋กœ ์‹ ํ˜ธ๋“ฑ ์Šค์ผ€์ฅด๋ง์ด ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

  • ์‹ ํ˜ธ๋“ฑ ์Šค์ผ€์ฅด๋ง ์ด๋ž€, ์œ„ ์˜ˆ์‹œ๋ฅผ ๋‹ค์‹œ ๋นŒ๋ฆฌ์ž๋ฉด C๊ต์ฐจ๋กœ์—์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์Šค์ผ€์ฅด๋งํ•ฉ๋‹ˆ๋‹ค.

    • {B-C, 2} {A-C, 1}
    • ์ด ํ‘œํ˜„์˜ ํ•ด์„์€ B-C ๊ฐ„์„ ์— 2์ดˆ๊ฐ„ ์ดˆ๋ก๋ถˆ์„ ์ผœ์ฃผ๊ณ , A-C ๊ฐ„์„ ์œผ๋กœ 1์ดˆ๊ฐ„ ๋ฐ”๊ฟจ๋‹ค๊ฐ€, ๋‹ค์‹œ B-C ๊ฐ„์„ ์„ 2์ดˆ๊ฐ„ ์ผœ์ฃผ๋Š” ์‹์œผ๋กœ ๋ฐ˜๋ณตํ•œ๋‹ค๋Š” ๋œป์ž…๋‹ˆ๋‹ค.
    • ์ฆ‰, ์‚ฌ์ดํด๋กœ๋งŒ ๋Œ๋ฆด ์ˆ˜ ์žˆ๊ณ , ์„ธ๋ถ€์ ์œผ๋กœ ์‹ ํ˜ธ๋“ฑ์„ ์กฐ์ž‘ํ•  ์ˆ˜๋Š” ์—†์Šต๋‹ˆ๋‹ค. ๋Œ€์ถฉ ์ƒ๊ฐํ•ด ๋ณด๋ฉด, ๊ต์ฐจ๋กœ์˜ ๊ฐ ๋„๋กœ๋“ค์„ ์œ„ํ•ด ์‹ ํ˜ธ๋ฅผ ์ผœ์ฃผ๋Š” ์ˆœ์„œ์™€ ๊ทธ ๋น„์ค‘์„ ์กฐ์ •ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

Hashcode ๋ฌธ์ œ๋Š” ์—ฌ๊ธฐ์„œ ์‹ ํ˜ธ๋“ฑ ์Šค์ผ€์ฅด๋ง ์‚ฌ์ดํด ์„ ๋งŒ๋“œ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋‹ค๋ฅธ ๋ชจ๋“  ๊ฒƒ์€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

์ ์ˆ˜๋Š”, ์ œํ•œ ์‹œ๊ฐ„ ๋‚ด์— ๋„์ฐฉํ•œ ์ฐจ์˜ ๊ฐœ์ˆ˜ ์— ๋”ฐ๋ผ ์ ์ˆ˜๋ฅผ ๋ฐ›์œผ๋ฉฐ, ๋นจ๋ฆฌ ๋„์ฐฉํ• ์ˆ˜๋ก ๋ณด๋„ˆ์Šค ์ ์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ํƒ€์ž„์•„์›ƒ ๋‚œ ์ฐจ๋Ÿ‰์€ 0์ ์ž…๋‹ˆ๋‹ค.

๋ฐ์ดํ„ฐ ์„ค๋ช…

๋ฐ์ดํ„ฐ๋Š” ์ด 6๊ฐœ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. A๋Š” ์˜ˆ์ œ๊ณ , ๋‚˜๋จธ์ง€ ๋ฐ์ดํ„ฐ๋“ค์€..

  • B : ๊ทธ๋ƒฅ ํ‰๋ฒ”ํ•œ ๋ฐ์ดํ„ฐ์ž…๋‹ˆ๋‹ค. ํฐ ํŠน์ง•์€ ์—†์Šต๋‹ˆ๋‹ค.
  • C : ๊ฒฉ์žํ˜•ํƒœ๋กœ ๋„๋กœ๊ฐ€ ๊ตฌ์„ฑ๋œ ๋ฐ์ดํ„ฐ์ž…๋‹ˆ๋‹ค.
  • D : ์‹œ๊ฐ„์ด ๊ต‰์žฅํžˆ ๋นก๋นกํ•ด์„œ, ์กฐ๊ธˆ๋งŒ ์ง€์ฒดํ•ด๋„ ๋ชจ๋“  ์ฐจ๋“ค์ด ํƒ€์ž„์•„์›ƒ๋‚ฉ๋‹ˆ๋‹ค. ๋ช‡๊ฐœ์˜ ํ—ˆ๋ธŒ์ •์ ๋“ค๊ณผ ๋‹ค์ˆ˜์˜ ์ •์ ๋“ค์ด ํฌ๋„์†ก์ด์ฒ˜๋Ÿผ ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ์ž…๋‹ˆ๋‹ค.
  • E : ๋ชจ๋“  ์ •์ ๋“ค์ด ํ•˜๋‚˜์˜ ํ—ˆ๋ธŒ์— ์—ฐ๊ฒฐ๋œ STAR ํ˜•ํƒœ์˜ ๊ทธ๋ž˜ํ”„์ž…๋‹ˆ๋‹ค. Etoile๋Š” ํ”„๋ž‘์Šค์–ด๋กœ ๋ณ„์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
  • F : ๊ต์ฐจ๋กœ๊ฐ€ ๋งค์šฐ ๋งŽ๊ณ , ์ฐจ๋Ÿ‰๋“ค์ด ๊ต์ฐจ๋กœ์— Stuckํ•˜๋Š” ๋ฐ์ดํ„ฐ์ž…๋‹ˆ๋‹ค.

๋Œ€ํšŒ ์ „๋žต์˜ ์‹คํŒจ

  • ๊ตฌํ˜„ ๋ณต์žก๋„๊ฐ€ ๋†’์•„์„œ, ์ฒด์ปค๋ฅผ ์ž‘์„ฑํ•˜์ง€ ๋ชปํ–ˆ์Šต๋‹ˆ๋‹ค. ์ € ํ˜ผ์ž ๋Œ€๋žต 1์‹œ๊ฐ„ ์ •๋„ ์‹œ๊ฐ„์„ ์จ ๋ณด๊ณ , ํฌ๊ธฐํ•˜๊ธฐ๋กœ ๊ฒฐ์ •ํ–ˆ๋Š”๋ฐ, ๊ทธ ์ด์œ ๋Š”
    • Coffeetea์™€ DHDroid๊ฐ€ ์ œ์‹œํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๊ธฐ๋ณธ์ ์œผ๋กœ ์ฐจ์˜ ์šดํ–‰์„ Simulationํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ ๊ทธ๋Ÿฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‹ค์ œ๋กœ ์ฝ”๋“œ๋กœ ์˜ฎ๊ธด๋‹ค๋ฉด, Simulation์„ ํ†ตํ•ด ์ ์ˆ˜๋ฅผ ์—ฐ์‚ฐํ•˜๋Š” ๋ณ„๋„์˜ ์ฒด์ปค ์—†์ด๋„, ์ฝ”๋“œ์— ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ๋‚ด์žฅํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
    • ๋”์ด์ƒ ์ฒด์ปค๋ฅผ ์žก๊ธฐ์—๋Š” ์‹œ๊ฐ„์ด ๋„ˆ๋ฌด ์•„๊นŒ์› ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
  • ๋งˆ์ฐฌ๊ฐ€์ง€ ์ด์œ ๋กœ, dlwocks31์ด ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ์ฝ”๋“œ ์ž‘์„ฑ์— ์‹คํŒจํ–ˆ์Šต๋‹ˆ๋‹ค. ๋Œ€ํšŒ ํ›„๋ฐ˜๋ถ€์—๋Š” ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋น„์Šทํ•œ๊ฒŒ ๋Œ์•„๊ฐ”๋Š”๋ฐ, ์ •ํ™•ํžˆ ์„ฑ๊ณตํ–ˆ๋Š”์ง€ ์—ฌ๋ถ€๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค. ์˜ˆ์ƒ ์ ์ˆ˜์™€ ์‹ค์ œ ์ ์ˆ˜ ๊ฐ„์— ์กฐ๊ธˆ์˜ ์˜ค์ฐจ๊ฐ€ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๋ณด์•„ ์–ด๋”˜๊ฐ€ ๋ฌธ์ œ๊ฐ€ ์—ฌ์ „ํžˆ ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๋ณด์ž…๋‹ˆ๋‹ค.
  • Coffeetea / DHDroid ๋“€์˜ค์˜ ๋ฐ์ดํ„ฐ๋ถ„์„ ๋ฐ ๊ตฌ์ƒ์€ ํƒ์›”ํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฒฐ๊ณผ์ ์œผ๋กœ ๊ฑฐ์˜ ์ด ๋‘๋ช…์ด ๋Œ€ํšŒ๋ฅผ ์บ๋ฆฌํ•ด ๋ฒ„๋ ธ์Šต๋‹ˆ๋‹ค. ์ €๋ž‘ dlwocks31์€ ๊ณ„์† ๊ณ ํ†ต๋ฐ›์€ ๋Œ€ํšŒ์˜€์Šต๋‹ˆ๋‹ค :(

Algorithm : Demand - Proportional - Scheduling

์•ž์„œ ์‹ ํ˜ธ๋ฅผ ์ผœ์ฃผ๋Š” ์ˆœ์„œ์™€ ๊ทธ ๋น„์ค‘์„ ์กฐ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค ๋ผ๊ณ  ํ–ˆ๋Š”๋ฐ, ์ €ํฌ๋Š” ๊ทธ์ค‘ ๋น„์ค‘์— ์ง‘์ค‘ํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ตฌ์ฒด์ ์œผ๋กœ๋Š”, ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ๋Œ๋ฆฌ๋ฉด์„œ, ๊ฐ ์ฐจ๋Ÿ‰๋“ค์ด ํŠน์ • ๊ต์ฐจ๋กœ์˜ ํŠน์ • ๋„๋กœ์— ์žกํ˜€์žˆ์„ ๋•Œ๋งˆ๋‹ค, ๊ทธ ์ •๋ณด๋ฅผ report ํ•ฉ๋‹ˆ๋‹ค.

์ด๋Ÿฐ ์ •๋ณด๋“ค์„ ๋ชจ์•„๋‘”๋‹ค๋ฉด, ๊ต์ฐจ๋กœ X์—์„œ ๋„๋กœ a, b์˜ total jam-time์„ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๊ณ , ์ด total jam-time์ด ๋†’์€ ๋„๋กœ์˜ ์‹ ํ˜ธ๋ฅผ ๋” ๋งŽ์ด ์—ด์–ด ์ค„ ํ•„์š”๊ฐ€ ์žˆ์Œ์ด ์ž๋ช…ํ•ด ๋ณด์ž…๋‹ˆ๋‹ค. (๊ฑฐ๊ธฐ ์žกํ˜€์žˆ๋Š” ์ฐจ๊ฐ€ ๋งŽ์œผ๋‹ˆ๊นŒ, ๋” ๋„‰๋„‰ํ•˜๊ฒŒ ์—ด์–ด ์ฃผ๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค) ๋”ฐ๋ผ์„œ ์ด DEMAND ์— ๋น„๋ก€ํ•˜๋Š” (๋˜๋Š” ๋ญ ์ ๋‹นํžˆ ๋ฃจํŠธ๋ผ๋˜๊ฐ€โ€ฆ) ์‹œ๊ฐ„๊ฐ€์ค‘์น˜๋ฅผ ์ฃผ์–ด ์‚ฌ์ดํด์„ ๋Œ๋ฆฌ๋Š” ๋ฐฉ์‹์ž…๋‹ˆ๋‹ค.

Fine Tuning

์œ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ํŠœ๋‹ํ•  ์ˆ˜ ์žˆ๋Š” ์•„์ด๋””์–ด๋Š” ์ œ๊ฐ€ ์ถ”๊ฐ€๋กœ ๋“ค์–ด๊ฐ€๊ณ  ๋‚˜์„œ ์ž ๊น์”ฉ Discussํ•˜๋ฉด์„œ ๊ณ„์† ๋ฐœ์ „์‹œ์ผœ๋‚˜๊ฐ”์Šต๋‹ˆ๋‹ค. ๋Œ€ํ‘œ์ ์œผ๋กœ ์ด๋Ÿฐ ๊ฒƒ๋“ค์ด ์žˆ์Šต๋‹ˆ๋‹ค.

  • $t = 1$ ์—์„œ์˜ demand์™€ $t = 1000$์—์„œ์˜ demand์˜ ๊ฐ€์น˜๋Š” ๋™๋“ฑํ•˜์ง€ ์•Š๋‹ค๊ณ  ๋ณด์•˜์Šต๋‹ˆ๋‹ค. ๋‘˜์ค‘ ํ•˜๋‚˜๋ผ๋ฉด ์ดˆ๋ฐ˜์ด ๋น ๋ฅธ ํŽธ์ด ์œ ๋ฆฌํ•˜๊ธฐ ๋•Œ๋ฌธ์ธ๋ฐ, ๋˜‘๊ฐ™์ด 1์ดˆ๋งŒํผ ๋นจ๋ผ์ง„๋‹ค๋ฉด ์ดˆ๋ฐ˜์— ๋นจ๋ผ์ ธ์•ผ ๋น ๋ฅด๊ฒŒ ์ฐจ๋“ค์ด ์ค„์–ด๋“ค์–ด์„œ ํ›„๋ฐ˜์ด ๋œ ๋ง‰ํžˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
  • ๊ตฌํ˜„ํ•˜์ง€๋Š” ๋ชปํ–ˆ์ง€๋งŒ, ๋ณธ๋ž˜ ๊ณ„ํš์—๋Š” ์‹ค์ œ ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ๊ฑฐ์นœ ๋‹ค์Œ, ์•„๊น๊ฒŒ ์‹œ๊ฐ„์ด ์ง€๋‚˜ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ•œ ์ฐจ๋“ค์˜ demand์— ๋” ํฐ ๊ฐ€์ค‘์น˜๋ฅผ ๋ถ€์—ฌํ•˜๋Š” ๋ฐฉ์•ˆ์ด ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. ์ด ๋ฐฉ์•ˆ์€ (ํ…Œ์ŠคํŠธํ•ด๋ณด์ง€ ๋ชปํ–ˆ์ง€๋งŒ) ์ถฉ๋ถ„ํžˆ ์˜๋ฏธ๊ฐ€ ์žˆ์—ˆ์„ ๊ฒƒ์ด๋ผ๊ณ  ๋ณด์ž…๋‹ˆ๋‹ค.
  • ๊ฐ€์ค‘์น˜ $w = f(d)$ ๋Š” demand ๊ฐœ์ˆ˜์— ๋Œ€ํ•œ ํ•จ์ˆ˜์ž…๋‹ˆ๋‹ค. $f$๋ฅผ ์กฐ๊ธˆ์”ฉ ๋ฐ”๊พธ๋ฉด์„œ ํŠœ๋‹ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ด ๋ชจ๋“  ํŠœ๋‹์˜ ๊ฒฐ๊ณผ๊ฐ€ ๋งจ ์œ„์— ๊ธฐ๋ก๋œ ๊ฒฐ๊ณผ์ž…๋‹ˆ๋‹ค.

๊ฒฐ๊ณผ / Discussion

๋Œ€ํšŒ๊ฐ€ ๋๋‚˜๊ณ , ๋ฐ”๋กœ ๊ทผ์ฒ˜์—์„œ ๋Œ€ํšŒ๋ฅผ ์น˜๋ฅธ, ํ‰์†Œ ์ž˜ ์•„๋Š” ์‚ฌ์ด์ธ ์„œ์šธ๋Œ€ํ•™๊ต @channel ํŒ€๊ณผ ๊ฐ„๋‹จํ•œ Discussion์„ ํ–ˆ์Šต๋‹ˆ๋‹ค. ๊ทธ ํŒ€์€ 2018๋…„๋„์— Hashcode World Final์— ์ง„์ถœํ–ˆ๋˜ ํŒ€์œผ๋กœ, ์ด๋ฒˆ ๋Œ€ํšŒ์—์„œ๋Š” ์ €ํฌ๋ณด๋‹ค 20๋งŒ์  ์ •๋„ ๋†’์€ ์ ์ˆ˜๋กœ 40๋“ฑ์˜ ๋†’์€ ์„ฑ์ ์„ ๊ฑฐ๋‘์—ˆ์Šต๋‹ˆ๋‹ค. ์„œ๋กœ ์„ฑ์ ์„ ๋ณด๋Š” ์ˆœ๊ฐ„ ๋†€๋ž๋Š”๋ฐ,

  • @channel ํŒ€์€ D์—์„œ 240๋งŒ์  ๊ฐ€๊นŒ์ด (์ €ํฌ๋ณด๋‹ค 80๋งŒ์  ๋†’์€) ์„ฑ์ ์„ ๊ฑฐ๋‘์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋ฐ˜๋ฉด, F๋ฒˆ์˜ ์ ์ˆ˜๋Š” ์ €ํฌ ํŒ€์ด 60๋งŒ์  ์ •๋„ ๋†’์•˜์Šต๋‹ˆ๋‹ค. ์„œ๋กœ D์™€ F๋ฅผ ๋ณด๋ฉฐ ์–ด๋–ป๊ฒŒ ํ•œ ๊ฑฐ๋ƒ๊ณ  ๋ฌผ์œผ๋ฉฐ ๋””์Šค์ปค์…˜์„ ์ง„ํ–‰ํ–ˆ๋Š”๋ฐ, ์ด ํŒ€์—๊ฒŒ ๋“ค์€ ๋ฐฉ๋ฒ•์€ (์ œ๊ฐ€ ์˜ฌ๋ฐ”๋ฅด๊ฒŒ ์ดํ•ดํ–ˆ๋‹ค๋ฉด) ๋Œ€๋žต ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
    • D๋ฒˆ์˜ ๊ฒฝ์šฐ, Degree๊ฐ€ ํ‰๊ท ์ ์œผ๋กœ ๋งค์šฐ ์ž‘์Šต๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ, ๊ตณ์ด ๊ธด ์‹œ๊ฐ„๋™์•ˆ ํ•œ ๊ธธ์„ ์—ด์–ด์ฃผ๊ธฐ๋ณด๋‹ค๋Š”, 1์ดˆ์”ฉ ๋ฐ”๋กœ๋ฐ”๋กœ ๋ฐ”๊ฟ”์ฃผ๋”๋ผ๋„ ํŠน์ • ๋„๋กœ์˜ ๋Œ€๊ธฐ์‹œ๊ฐ„์ด ๊ทธ๋ ‡๊ฒŒ๊นŒ์ง€ ๊ธธ์ง€ ์•Š์œผ๋ฏ€๋กœ, ๋ชจ๋“  ์‹ ํ˜ธ ์‚ฌ์ดํด์€ 1์ดˆ๋กœ ๊ณ ์ •ํ•ฉ๋‹ˆ๋‹ค.
    • ๊ทธ๋Ÿฌ๋‚˜, ์–ด๋–ค ์ˆœ์„œ๋กœ ์‚ฌ์ดํด์„ ๋Œ๋ฆด์ง€๋Š” ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์‹ค์ œ ์‹œ๋ฎฌ๋ ˆ์ด์…˜์„ ์ง„ํ–‰ํ•˜๋ฉด์„œ, ํ•ด์‹œํ…Œ์ด๋ธ”์— ๊ธฐ๋กํ•˜๋Š” ์‹์œผ๋กœ ๊ฐ intersection๋งˆ๋‹ค ์–ด๋””์— ๋Œ€๊ธฐ๊ฐ€ ๊ฑธ๋ฆฌ๋Š”์ง€๋ฅผ ํŒŒ์•…ํ•ด์„œ ์‚ฌ์ดํด์˜ ์ˆœ์„œ๋ฅผ ์ตœ์ ํ™”ํ•ฉ๋‹ˆ๋‹ค.
    • ๊ฒฐ๋ก ์ ์œผ๋กœ, ์‹ ํ˜ธ๋ฅผ ์ผœ์ฃผ๋Š” ์ˆœ์„œ์™€ ๊ทธ ๋น„์ค‘์„ ์กฐ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค ์—์„œ, ๋น„์ค‘ ์„ ๋ฒ„๋ฆฌ๊ณ  ์ˆœ์„œ ์— ์ง‘์ค‘ํ•œ ํ˜•ํƒœ์˜ ์†”๋ฃจ์…˜์œผ๋กœ ๋ณด์ž…๋‹ˆ๋‹ค. ์ผ์ข…์˜ Dynamic Cycle Ordering ์ด๋ผ๋Š” ์ด๋ฆ„์„ ๋ถ™์ผ ์ˆ˜ ์žˆ๊ฒ ๋„ค์š”.
  • 1๋“ฑํŒ€์˜ ์ ์ˆ˜๋Š” 1050๋งŒ ์  ์ •๋„๊ณ , 1000๋งŒ์ ์„ ๋„˜์œผ๋ฉด 10์œ„๊ถŒ ํŒ€์ด์—ˆ์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ณผ์ ์œผ๋กœ, ์ €ํฌ์˜ Demand-Proportional Scheduling ๊ณผ @channel์˜ Dynamic Cycle Ordering์ด ์ƒํ˜ธ ๋ณด์™„์ ์ธ ๋ฐฉ๋ฒ•์ด๋ฉฐ, ์ €ํฌ๊ฐ€ ์ž˜ ํ‘ธ๋Š” ์ผ€์ด์Šค (F) ์™€ @channelํŒ€์ด ์ž˜ ํ‘ผ ์ผ€์ด์Šค (D) ์˜ max์ ์ˆ˜๋ฅผ ์ทจํ•˜๋ฉด 1030๋งŒ ์  ์ •๋„์ž„์„ ๋ณผ ๋•Œ, ์ตœ์ƒ์œ„๊ถŒ ํŒ€์€ ์ด ๋‘ ๊ฐ€์ง€ ์ „๋žต์„ ๊ฐ๊ฐ ์ฝ”๋”ฉํ•ด์„œ ์ œ์ถœํ–ˆ๊ฑฐ๋‚˜, ๋‘ ์ „๋žต์„ ์ ˆ์ถฉํ•œ ๋ฐฉ์•ˆ์ด ์žˆ๊ฑฐ๋‚˜, ๋˜๋Š” ์šฐ๋ฆฌ ๋ชจ๋‘ ์ƒ๊ฐ์ง€ ๋ชปํ•œ Novelํ•œ ๋ฐฉ๋ฒ• (์žˆ์„์ง€๋Š” ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค๋งŒ) ์ผ ๊ฒƒ์œผ๋กœ ๋ณด์ž…๋‹ˆ๋‹ค. ๋‘ ๊ฐ€์ง€ ๋ชจ๋‘ ์–ด๋–ป๊ฒŒ ๋ณด๋ฉด ์ž์—ฐ์Šค๋Ÿฝ๊ธฐ๋„ ํ•ด์„œ, ๋‘๊ฐ€์ง€ ๋ชจ๋‘ ๊ตฌํ˜„ํ•˜๋Š”๋ฐ ์„ฑ๊ณตํ–ˆ์œผ๋ฉด ์›”ํดํŒ€์ด ์•„๋‹ˆ์—ˆ๋‚˜ ์‹ถ์Šต๋‹ˆ๋‹ค.

์•ž์œผ๋กœ๋ฅผ ์œ„ํ•ด

ํ•ด์‹œ์ฝ”๋“œ๋ฅ˜ ๋Œ€ํšŒ๋Š” ์‚ฌ์‹ค ์ €ํฌ์—๊ฒŒ๋Š” ๋งค์šฐ ์žฌ๋ฐŒ๊ธฐ๋„ ํ•˜๊ณ , ์ด๋Ÿฐ ํ‰์†Œ์—๋Š” ์ƒ๊ฐํ•˜๊ธฐ ์–ด๋ ค์šด ๊ฒƒ๋“ค์„ ๊ณต๋ถ€ํ•˜๋Š” ๊ธฐํšŒ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‚˜๋ฆ„๋Œ€๋กœ ํŒ€์œผ๋กœ์จ ๊ณต๋ถ€ํ•˜๋Š” ์ฆ๊ฑฐ์›€์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜์„œ ์•„๋งˆ (์ ์–ด๋„ ๋‚ด๋…„์—๋Š”) ๊ฐ™์€ ํŒ€์œผ๋กœ ๋‚˜๊ฐˆ ์˜ˆ์ •์ธ๋ฐ, ๊ทธ๋•Œ๋ฅผ ์œ„ํ•ด, ๋˜๋Š” ๋‹ค๋ฅธ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๋Œ€ํšŒ๋ฅผ ์œ„ํ•ด์„œ๋ผ๋„ ์ด๋ฒˆ ๋Œ€ํšŒ๋ฅผ ํ†ตํ•œ ๊ตํ›ˆ์„ ๊ธฐ๋กํ•ด ๋‘๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

  • ๊ฒฐ๊ตญ์€ ๊ตฌํ˜„๋ ฅ์ด ์ค‘์š”ํ•ฉ๋‹ˆ๋‹ค. ํŠนํžˆ Hashcode๊ฐ€ ๋งค๋…„ ๊ทน๋„๋กœ ๊ตฌํ˜„์ด ๋นก์„ธ์ง€๊ณ  ์žˆ๊ณ , ์ œํ•œ์‹œ๊ฐ„ 4์‹œ๊ฐ„ (์‹ค์ œ๋กœ๋Š” 15๋ถ„๋™์•ˆ ์ŠคํŠธ๋ฆฌ๋ฐ์œผ๋กœ ์‹œ๊ฐ„์„ ๋‚ ๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— 3์‹œ๊ฐ„ 45๋ถ„) ๋™์•ˆ ๋ฌธ์ œ์˜ ๊ธฐ๋ณธ์ ์ธ ๊ทธ๋ฆฌ๋”” ์†”๋ฃจ์…˜์„ ์ œ์‹œํ•˜๊ธฐ์กฐ์ฐจ ์–ด๋ ค์›Œ์ง€๋Š” ํ˜„์ƒ์ด ๊ฐ€์†๋˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒฐ๊ตญ ์ด๋ฒˆ ๋Œ€ํšŒ์˜ ์ตœ์ƒ์œ„๊ถŒ ์ „๋žต ์ค‘ ํ•˜๋‚˜๋Š”, Demand-Proportional Scheduling ๊ณผ Dynamic Cycle Ordering ์ด๋ผ๋Š” ์ „ํ˜€ ๊ฒฐ์ด ๋‹ค๋ฅธ ๋‘๊ฐ€์ง€ ๋ฐฉ๋ฒ•์„ ๋ชจ๋‘ ์ฝ”๋”ฉํ•˜๋Š”๋ฐ ์„ฑ๊ณตํ•˜๋Š” ๊ฒƒ์ธ๋ฐ, ์ด๋ฅผ ์œ„ํ•ด์„œ๋Š” ์ ์–ด๋„ 2๋ช… ์ด์ƒ์˜ ํŒ€์›์ด ์•ˆ์ •์ ์œผ๋กœ ์†”๋ฃจ์…˜์„ ์ฝ”๋“œ๋กœ ์˜ฎ๊ธฐ๋Š” ๋Šฅ๋ ฅ์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค.
    • Dlwocks31์ด ์šฐ๋ฆฌ ์ค‘์—์„œ๋Š” ๊ตฌํ˜„์„ ๊ฐ€์žฅ ์ž˜ํ•˜์ง€๋งŒ, ๋‚˜๋จธ์ง€ 3๋ช…์˜ ๊ตฌํ˜„๋ ฅ์ด ํ˜„์ €ํžˆ ๋–จ์–ด์ง€๋Š” ๊ฒƒ์€ ๊ต‰์žฅํžˆ ํฐ ๊ฒฐ์ ์ž…๋‹ˆ๋‹ค. ์ด๋ฅผ ๋ณด์ถฉํ•˜๊ธฐ ์œ„ํ•ด, ์ตœ๋Œ€ํ•œ ์ €ํฌ๊ฐ€ (ํŠนํžˆ ๊ทธ๋‚˜๋งˆ C++ ๊ตฌํ˜„๋ ฅ์ด ๋‚˜์€ ์ œ๊ฐ€) dlwocks31์„ ๋ณด์กฐํ•ด์ฃผ๊ธฐ ์œ„ํ•ด ์ด๋ฒˆ์—๋Š” ํŒŒ์ผ์„ ๋‚˜๋ˆ„์–ด GIT์„ ์จ๋ณด๊ธฐ๋„ ํ–ˆ๋Š”๋ฐ, ๊ฒฐ๊ตญ ๋Œ€ํšŒ๊ฐ€ ๋๋‚˜๊ณ  ๋Š๋‚€ ๊ฒƒ์€ ์ด ๋ชจ๋“  ๋ฐฉ๋ฒ•์€ ๋ถ€์กฑํ•œ ๊ตฌํ˜„๋ ฅ์„ ๋ฉ”์›Œ๋ณด๋ ค๋Š” ์‹œ๋„์˜€๊ณ  ๊ทผ๋ณธ์ ์ธ ํ•ด๊ฒฐ์ฑ…์ด ๋˜์ง€ ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ์•„์ด๋””์–ด ์บ์นญ ์ดํ›„, ์ด๊ฑธ ๋ฐ”๋กœ ์ฝ”๋“œ๋กœ ์˜ฎ๊ฒจ์„œ ํ…Œ์ŠคํŠธํ•ด๋ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์‹ค์ œ๋กœ Coffeetea๊ฐ€ ์ œ์‹œํ•œ ๋งŽ์€ ํœด๋ฆฌ์Šคํ‹ฑํ•œ ๋ฐฉ๋ฒ•๋“ค์˜ ๋ฐ˜๋„ ์ฑ„ ์“ฐ์ง€ ๋ชปํ–ˆ๋Š”๋ฐ ์ด๊ฒƒ๋„ ๊ฒฐ๊ตญ ์‹œ๋„ํ•ด๋ด์•ผ ์•„๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์ž‘๋…„์—๋„ ๋น„์Šทํ•˜๊ฒŒ ํ–ˆ๋˜ ๋ง์ด์ง€๋งŒ, ๋Œ€ํšŒ ์ž์ฒด๋Š” ํ•ด๋ณด๋ฉด ์ •๋ง ์žฌ๋ฐŒ์Šต๋‹ˆ๋‹ค. ์†”๋ฃจ์…˜ ๊นŽ๋Š” ๊ณผ์ •์ด ๋ญ”๊ฐ€ ๋‹ค๋ฅธ PS๋Œ€ํšŒ๋ž‘ ๊ต‰์žฅํžˆ ์ด์งˆ์ ์ด๋ฉด์„œ๋„ ์ ์ˆ˜ ์˜ฌ๋ผ๊ฐˆ๋•Œ ์งœ๋ฆฟํ•œ ๊ทธ๋Ÿฐ ๋ง›์ด ์žˆ๋Š”๋ฐ, ๊ตฌํ˜„๋ณด๋‹ค๋Š” ์กฐ๊ธˆ๋” ์ตœ์ ํ™” ๋ง›์ด ๋‚˜๋Š” ๋Œ€ํšŒ๊ฐ€ ๋˜์—ˆ์œผ๋ฉด ํ•˜๋Š” ๊ธฐ๋Œ€๊ฐ€ ์žˆ์ง€๋งŒ ๋ฐ˜๋Œ€๋กœ ๊ฐ€๋Š”๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์—ฌ์ „ํžˆ ์ž‘๋…„ Library์ฒ˜๋Ÿผ, ์ถ”ํ•œ ํ…Œํฌ๋‹‰์œผ๋กœ ๊ฐ€๋ฅด๋”๋ผ๋„ ๊ฒฐ๊ตญ ์ง„์ถœ๊ถŒ์€ SAT๊ณผ MCMF์ตœ์ ํ™”๊ฐ€ ๊ฐ€๋ฅด๋Š” ๋ฉ”ํƒ€๊ฐ€ ์˜ณ๋‹ค๋Š” ๋ฏฟ์Œ์—๋Š” ๋ณ€ํ™”๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค. ๊ทธ์— ๋น„ํ•˜๋ฉด ์ด๋ฒˆ ๋Œ€ํšŒ๋Š” ์ง„์งœ ๊ตฌํ˜„์ปต์ธ๊ฒƒ ๊ฐ™์•„์„œ ์กฐ๊ธˆโ€ฆ ํ•˜์ง€๋งŒ ์ž‘๋…„์—๋„ ๊ทธ๋žฌ๋“ฏ์ด, ๊นŒ๋ณด๋ฉด ๋ˆ„๊ตฐ๊ฐ€ ์ด์ƒํ•œ ์ตœ์ ํ™”๋ฅผ ๋“ค๊ณ ์™”์„์ˆ˜๋„ ์žˆ์œผ๋ฏ€๋กœ ์•„์ง ์˜ˆ๋‹จํ•˜์ง€๋Š” ์•Š์œผ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

๊ตฌ์ฒด์ ์œผ๋กœ DEF์ค‘ ํ•˜๋‚˜์— ๋ญ”๊ฐ€ ํ”Œ๋กœ์šฐ๋กœ ์ตœ์ ํ™”ํ• ์ˆ˜ ์žˆ๋Š”๊ฒŒ ์žˆ์„๊ฑฐ๋ผ๊ณ  ์˜์‹ฌํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋ž˜ํ”„์—์„œ ๋ญ”๊ฐ€ ์ง€๋‚˜๊ฐ€๊ณ  ์–ด์ฉŒ๊ณ  ํ•˜๋Š”๊ฒŒ ๋”ฑ ํ”Œ๋กœ์šฐ ๋ƒ„์ƒˆ๊ฐ€ ๋‚˜์„œ์š”โ€ฆ

PS๋ฅผ ์ฆ๊ธด๋‹ค๋ฉด ๊ทธ๋ƒฅ ์ƒ‰๋‹ค๋ฅธ ๋Š๋‚Œ์œผ๋กœ ์ฆ๊ธธ๋งŒํ•œ, ๊ทธ๋ ‡์ง€ ์•Š๊ณ  ์›๋ž˜ Data Science ๋‚˜ Optimization์ชฝ์— ๊ด€์‹ฌ์ด ์žˆ๋”๋ผ๋„ ํ•œ๋ฒˆ์ฏค ํ•ด๋ณผ๋งŒํ•œ ๋Œ€ํšŒ๋ผ๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ๋‚ด๋…„์—๋„ ํŒŒ์ดํŒ…!

Little Piplup ์ˆ˜๊ณ  ๋งŽ์•˜์–ด์š” :) + @channelํŒ€์˜ ์›”ํŒŒ ์ง„์ถœ์„ ์‘์›ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค :)