Back to : ps-weekly

July 19 - July 28, 2021

์ด ๊ธ€์— ๊ตฌํ˜„์ฝ”๋“œ ๋งํฌ๊ฐ€ ์—†๋”๋ผ๋„ PS ๋ ˆํฌ ๋งํฌ ์— ๊ฐ€์„œ ๋Œ€ํšŒ ๋‹จ์œ„๋กœ ๋“ค์–ด๊ฐ€๋ฉด ๋ณดํ†ต ์˜ฌ๋ ค๋†“์€ ์ฝ”๋“œ๋ฅผ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

7์›” ๋งˆ์ง€๋ง‰ ์ฃผ๋Š” ์ผ๋ฐ˜์ƒ๋ฌผํ•™ ์‹œํ—˜์„ ๋น„๋กฏ, ๋ช‡๊ฐ€์ง€ ํ• ์ผ์ด ์žˆ์–ด์„œ PS๋ฅผ ๊ฑฐ์˜ ๋ชปํ• ๋“ฏ ํ•ฉ๋‹ˆ๋‹ค :(

์ฝ๋Š” ์‚ฌ๋žŒ์ด ๋ฌธ์ œ๋ฅผ ์ฝ๊ณ  ์กฐ๊ธˆ ์ƒ๊ฐํ•ด๋ดค๋‹ค๊ณ  ๊ฐ€์ •ํ•˜๊ณ , ๋Œ€๋žต์ ์ธ ์•„์ด๋””์–ด๋งŒ ๊ฐ„๋‹จํžˆ ์ ์„ ์ƒ๊ฐ์ž…๋‹ˆ๋‹ค ใ…Žใ…Ž

Recent Updates

  • ์–ด๋ฆฌ์„์€ ์‹ค์ˆ˜๋กœ UCPC์— ์ฐธ๊ฐ€ํ•˜์ง€ ๋ชปํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.
  • ๋ญ”๊ฐ€ SCPC 2์ฐจ ์ค€๋น„๋Š” ๋งˆ๋•…ํžˆ ํ• ์ˆ˜์žˆ๋Š”๊ฒŒ ์—†๊ณ  ํ•ด์„œโ€ฆ ์ˆœ์ˆ˜ํ•˜๊ฒŒ ์žฌ๋ฐŒ๋Š” ๊ณต๋ถ€๋ฅผ ํ•˜๋ ค๊ณ  ๋…ธ๋ ฅ ์ค‘์ž…๋‹ˆ๋‹ค.
  • ICPC ์ฒ ์ด ๋˜๋ฉด ํŒ€์›๋“ค๊ณผ ํ•จ๊ป˜ ๋˜ ์žฌ๋ฐŒ๊ฒŒ ํ• ์ˆ˜์žˆ์„๋“ฏ ํ•ฉ๋‹ˆ๋‹ค. ํŒ€์—ฐ์Šต์ด ์ œ์ผ ์žฌ๋ฐŒ๋Š”๊ฑฐ ๊ฐ™์•„์š”
  • ์˜ฌํ•ด PS ์„ฑ๊ณผ๋Š” ์ฝ”๋“œ์žผ R3 ๊ฐ„๊ฑธ๋กœ ๋งˆ๋ฌด๋ฆฌํ•˜๊ฒŒ ๋ ๋“ฏโ€ฆ


(Testing) Codeforces Global Round 15

  • Global Round 15์— ํ…Œ์Šคํ„ฐ๋กœ ์ฐธ์—ฌํ–ˆ์Šต๋‹ˆ๋‹ค.
  • ์ œ๊ฐ€ ํ…Œ์ŠคํŒ…ํ–ˆ์„๋•Œ๋ž‘ ๋น„๊ตํ•˜๋ฉด, B๋ฒˆ ๋ฌธ์ œ๊ฐ€ ์ƒˆ๋กœ ์ƒ๊ฒผ๊ณ , ์›๋ž˜์˜ B๋ฒˆ์ด D๋ฒˆ์œผ๋กœ ์ด๋™ํ–ˆ์Šต๋‹ˆ๋‹ค. ํ…Œ์ŠคํŒ…ํ–ˆ์„๋•Œ๋„ B (์ง€๊ธˆ์˜ D) ๊ฐ€ ๋„ˆ๋ฌด ์–ด๋ ค์šด๊ฑฐ ๊ฐ™๋‹ค๋Š” ์ƒ๊ฐ์€ ๋“ค์—ˆ์—ˆ์Šต๋‹ˆ๋‹ค.


๊ทธ๋ž˜ํ”„ ์—ฐ์Šต.

BOJ 1766 ๋ฌธ์ œ์ง‘

  • ๋‚œ์ด๋„ Gold 2
  • ์‚ฌ์šฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์— ๋Œ€ํ•œ ์ดํ•ด๋งŒ ๋ช…ํ™•ํ•˜๋ฉด ์‰ฝ์Šต๋‹ˆ๋‹ค.
  • BFS๋กœ ๋…ธ๋“œ๋“ค์„ ์œ„์ƒ ์ •๋ ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ๋”ฐ๋ฅด๋˜
  • queue ๋Œ€์‹  ํ•ญ์ƒ ๊ฐ€๋Šฅํ•œ ์‰ฌ์šด ๋ฌธ์ œ๋ฅผ ํ’€๋ผ๋Š” ์กฐ๊ฑด์ด ์žˆ์œผ๋ฏ€๋กœ BFS์—์„œ Queue ๋Œ€์‹  Priority Queue๋ฅผ ์“ฐ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

POI 1994 Ones and Zeros (BOJ 8111 0๊ณผ 1)

  • ๋‚œ์ด๋„ Platinum 5
  • ์–ด๋–ค ์ˆ˜์˜ ๋’ค์— 0๊ณผ 1์„ ์ด์–ด์„œ ๋‹ค์Œ ์ˆ˜๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ 0๋ถ€ํ„ฐ $N-1$๊นŒ์ง€์˜ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉด ๋‚˜๋จธ์ง€๊ฐ€ $r$์— ์„œ, $10r$ ๋˜๋Š” $10r + 1$ ๋กœ ๋…ธ๋“œ๊ฐ€ ์ด์–ด์ ธ ์žˆ์Œ์„ ๊ด€์ฐฐํ•ฉ๋‹ˆ๋‹ค.
  • ์ด์ œ 1์—์„œ BFS๋ฅผ ํ†ตํ•ด ๋…ธ๋“œ๋“ค์„ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ, 0์ด 100-step ์ด๋‚ด์— ๋ฐฉ๋ฌธ ๊ฐ€๋Šฅํ•œ์ง€ ํ™•์ธํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

BOJ 1602 ๋„๋ง์ž ์›์ˆญ์ด

  • ๋‚œ์ด๋„ Platinum 5
  • ๋…ธ๋“œ ๊ฐ€์ค‘์น˜๋Š” ํ•ฉ์ด ์•„๋‹ˆ๋ผ, ๊ฒฝ๋กœ ์ƒ์˜ ๊ฐ€์ค‘์น˜์˜ max๋งŒ ํ•œ ๋ฒˆ ๋”ํ•ฉ๋‹ˆ๋‹ค.
  • ์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ๋ฒ•์€, ๊ทธ๋ƒฅ ๋…ธ๋“œ ์ˆœ์„œ๋Œ€๋กœ โ€˜์ค‘๊ฐ„ ๋…ธ๋“œโ€™ ๋ฅผ ์“ฐ๋Š” F-W์™€๋Š” ๋‹ฌ๋ฆฌ ๋…ธ๋“œ ๊ฐ€์ค‘์น˜๊ฐ€ ์ž‘์€ ๊ฒƒ๋ถ€ํ„ฐ ์ค‘๊ฐ„ ๋…ธ๋“œ๋กœ ์จ์„œ ์—…๋ฐ์ดํŠธํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ์ƒˆ๋กœ์šด ๋…ธ๋“œ๋ฅผ ์“ฐ๋Š” ๊ฒฝ์šฐ ํ•ญ์ƒ ๋…ธ๋“œ๊ฐ€์ค‘์น˜๋Š” ์ƒˆ ๋…ธ๋“œ์˜ ๊ฒƒ์„ ๋”ฐ๋ผ๊ฐ€๊ฒŒ ๋˜๋ฏ€๋กœ, ๋น„๊ต์  ์‰ฝ๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

ICPC Germany Regional (GCPC) 2010 D Field Plan (BOJ 3977 ์ถ•๊ตฌ ์ „์ˆ )

  • ๋‚œ์ด๋„ Platinum 4
  • ๊ทธ๋ž˜ํ”„๋ฅผ SCC๋กœ ๋ฌถ์–ด์„œ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ๊ฐ™์€ SCC์— ์žˆ๋Š” ์ •์ ๋ผ๋ฆฌ๋Š” ์–ธ์ œ๋“  ์„œ๋กœ ์˜ค๊ฐˆ ์ˆ˜ ์žˆ๊ธฐ ๋–„๋ฌธ์ž…๋‹ˆ๋‹ค.
  • ์ด์ œ, indegree๊ฐ€ 0์ธ SCC๋ฅผ ์ฐพ์•„์„œ, ๊ทธ SCC๋กœ๋ถ€ํ„ฐ ์ถœ๋ฐœํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ๋‹จ, indegree๊ฐ€ 0์ธ SCC๊ฐ€ ์—ฌ๋Ÿฌ๊ฐœ์ด๋ฉด ์ด ๋‘๊ฐœ๋ฅผ ์„œ๋กœ ์˜ค๊ฐˆ์ˆ˜๊ฐ€ ์—†์–ด์„œ, ๋ถˆ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.
  • SCC ๊ตฌํ˜„์€ Tarjan ์•„๋‹ˆ๋ฉด Kosaraju์ธ๋ฐ, Tarjan์ด ๊ตฌํ˜„ํ• ๊ฒŒ ์ ๊ณ  ์ข€๋” ๋น ๋ฆ…๋‹ˆ๋‹ค. Kosaraju๋Š” ์ตœ์†Œ 2๋ฒˆ ์ด์ƒ์˜ DFS๋ฅผ ๋Œ์•„์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.
  • ๋ณ„๊ฐœ๋กœ ์ €๋Š” ์˜ˆ์ „์— ์งœ๋†“์€ Kosaraju๋ฅผ ๋Œ€์ถฉ ๋ฐ•์•„๋„ฃ์—ˆ์Šต๋‹ˆ๋‹ค.

BOJ 4196 ๋„๋ฏธ๋…ธ

  • ๋‚œ์ด๋„ Platinum 4
  • ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ, SCC๋ฅผ ๋ฌถ์€ ๋‹ค์Œ indegree๊ฐ€ 0์ธ SCC๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์œ„ ๋ฌธ์ œ์™€ ๊ฑฐ์˜ ๋˜‘๊ฐ™์Šต๋‹ˆ๋‹ค.
  • ๋‹ค๋งŒ ์ด๋ฒˆ์—” ๋ถˆ๊ฐ€๋Šฅํ•œ ๊ฒฝ์šฐ๊ฐ€ ์•„๋‹ˆ๋ผ, indegree๊ฐ€ 0์ธ ๋ชจ๋“  SCC๋ฅผ ์ง์ ‘ ๋„˜์–ดํŠธ๋ฆฌ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

ICPC Jakarta Regional 2018 Boomerangs (BOJ 16583)

  • ๋‚œ์ด๋„ Platinum 2
  • ๋จผ์ €, ํŠธ๋ฆฌ์— ๋Œ€ํ•ด ๋ฌธ์ œ๋ฅผ ํ’€์–ด ๋ด…์‹œ๋‹ค. ์–ด๋–ค ๋…ธ๋“œ์˜ child๊ฐ€ ์ง์ˆ˜๊ฐœ๋ผ๋ฉด, ์ง์ˆ˜๊ฐœ์˜ ์ž์‹๋…ธ๋“œ๋“ค๊ณผ ํ˜„์žฌ ๋…ธ๋“œ๋ฅผ ๋ถ€๋ฉ”๋ž‘์œผ๋กœ ์„œ๋กœ ์ด์–ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ํ™€์ˆ˜๊ฐœ๋ผ๋ฉด, ๋ฐฉ๊ธˆ์ „์ฒ˜๋Ÿผ ์ž‡๊ณ , ์ด์–ด์ง€์ง€ ์•Š์€ ํ•˜๋‚˜์˜ ๋…ธ๋“œ์™€ ํ˜„์žฌ ๋…ธ๋“œ, ํ˜„์žฌ ๋…ธ๋“œ์˜ ๋ถ€๋ชจ ๋…ธ๋“œ๋ฅผ ๋ถ€๋ฉ”๋ž‘์œผ๋กœ ์ด์–ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์ด๋•Œ, ๋ถ€๋ชจ ๋…ธ๋“œ์—๊ฒŒ ํ˜„์žฌ ๋…ธ๋“œ๋Š” ์ด๋ฏธ ์‚ฌ์šฉ๋˜์—ˆ์œผ๋ฏ€๋กœ ๋ถ€๋ชจ ๋…ธ๋“œ์˜ ์ž์‹๋…ธ๋“œ๋ฅผ ์ž‡๋Š” ๊ณผ์ •์— ์ฐธ์—ฌํ•˜๋ฉด ์•ˆ ๋œ๋‹ค๋Š” ์‚ฌ์‹ค์„ reportํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด, ํŠธ๋ฆฌ๋ฅผ DFS ์ˆœ์„œ๋กœ ๋Œ๋ฉด์„œ ๋ชจ๋“  ๊ฐ„์„ ์„ (๊ฐ„์„ ์ด ํ™€์ˆ˜๊ฐœ๋ฉด 1๊ฐœ ๋นผ๊ณ ) ๋ถ€๋ฉ”๋ž‘์— ์ฐธ์—ฌ์‹œํ‚ฌ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๋”ฐ๋ผ์„œ, ํŠธ๋ฆฌ์— ๋Œ€ํ•ด์„œ๋Š” ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์ด๋ฅผ ์ผ๋ฐ˜ํ™”ํ•ด์„œ ์ž„์˜ ๊ทธ๋ž˜ํ”„์— ๋Œ€ํ•ด ํ•ด๊ฒฐํ•ด ๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.
  • ์šฐ๋ฆฌ๋Š” ์ •์ ์ด ์ค‘์š”ํ•˜์ง€ ์•Š๊ณ , ๊ฐ„์„ ๋งŒ ์ค‘์š”ํ•˜๋ฏ€๋กœ, ๊ทธ๋ž˜ํ”„๋ฅผ ๊ฐ•์ œ๋กœ ํŠธ๋ฆฌ์ฒ˜๋Ÿผ ํŽด๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€, ์‚ฌ์ดํด์„ ์ด๋ฃจ๊ธฐ ์‹œ์ž‘ํ•˜๋Š” ๊ฐ„์„ ์„ ๋งŒ๋‚˜๋ฉด ๊ทธ ๊ฐ„์„ ์˜ ๋์— ์ƒˆ๋กœ์šด ์ •์ ์„ ๋งŒ๋“ค์–ด์„œ, ์‚ฌ์ดํด์„ ์ด๋ฃจ์ง€ ๋ชปํ•˜๊ฒŒ ๋ง‰์œผ๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ์ƒˆ๋กœ์šด ์ •์ ์€ ๋‚˜์ค‘์— ๋ถ€๋ฉ”๋ž‘์„ ๋งŒ๋“ค ๋•Œ ๋‹ค์‹œ ์›๋ž˜ ์ •์ ์œผ๋กœ ๋Œ๋ ค์ค˜์•ผ ํ•˜๊ธฐ์—, ์ด ์‚ฌ์‹ค์„ ๊ธฐ์–ตํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.
  • ๋ง์€ ๋ณต์žกํ•˜์ง€๋งŒ, ์ฝ”๋“œ๋Š” ๊ต‰์žฅํžˆ ๊น”๋”ํ•˜๊ฒŒ ๋‚˜์˜ต๋‹ˆ๋‹ค. build_tree(r, p) ํ•จ์ˆ˜๋ฅผ ๋ณด๋ฉด ๋ฉ๋‹ˆ๋‹ค.
  • ์ „์ฒด ๊ณผ์ •์„ DFS 2๋ฒˆ์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋‘๋ฒˆ์งธ BFS์ธ build_boo(r, p) ์—์„œ, child node ๋“ค ์ค‘ ์ด๋ฏธ ์‚ฌ์šฉํ•œ ๋…ธ๋“œ๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ๋“ฑ ๋””ํ…Œ์ผ์€ ์กฐ๊ธˆ ์ฃผ์˜ํ•ด์•ผ๊ฒ ์Šต๋‹ˆ๋‹ค.