Back to : ps-weekly
Contents

August 16 - August 31, 2021

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

BOJ์˜ ๋ฌธ์ œ ์ค‘ [์ถœ์ฒ˜] ์— ๋Œ€ํšŒ๋ช…์ด ์ ํ˜€์žˆ์ง€ ์•Š์œผ๋ฉด ์ œ ๋ ˆํฌ์—์„œ๋Š” BOJ Original์— ์žˆ์Šต๋‹ˆ๋‹ค.

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

Recent Updates

  • Hackercup Qual round์— ์ฐธ์—ฌํ–ˆ์Šต๋‹ˆ๋‹ค.

Rounds

Facebook HackerCup, Qualification Round

  • Qual round๋ผ์„œ ๋ณ„๋กœ ํ• ๋ง์€ ์—†๋Š”๋“ฏ ํ•ฉ๋‹ˆ๋‹ค. C2๋Š” ์žฌ๋ฐŒ์ง€๋งŒ ๊ตฌํ˜„์„ ํฌ๊ธฐํ–ˆ๊ณ , C1๊นŒ์ง€๋Š” ์žฌ๋ฐŒ๊ฒŒ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.
  • FHC๋Š” ์ •๋ง ํ•ด๊ดดํ•œ ์ฑ„์  ๋ฐฉ์‹์„ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ใ…‹ใ…‹โ€ฆ

Problems


BOJ 1086 ๋ฐ•์„ฑ์›

  • ๋‚œ์ด๋„ Platinum V
  • Bitmask DP๋ฅผ ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. dp[BIT][REM] ์„, BIT ์— ํ•ด๋‹นํ•˜๋Š” ๋น„ํŠธ๋งˆ์Šคํฌ๋ฅผ ๋ถ™์—ฌ ๋‚˜๋จธ์ง€ REM์„ ๋งŒ๋“œ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋กœ ์ •์˜ํ•˜๊ณ , ์•„์ง ์“ฐ์ง€ ์•Š์€ ์›์†Œ๋“ค์„ DP๋กœ ์ž˜ ๊ด€๋ฆฌํ•ฉ๋‹ˆ๋‹ค.
  • ์ž์„ธํ•œ ๊ฒƒ์€ ์ฝ”๋“œ ์ฐธ๊ณ .

BOJ 1533 ๊ธธ์˜ ๊ฐœ์ˆ˜

  • ๋‚œ์ด๋„ Platinum IV
  • ๊ฐ€์ค‘์น˜ ์—†๋Š” ๊ทธ๋ž˜ํ”„์˜ ์ธ์ ‘ํ–‰๋ ฌ A์— ๋Œ€ํ•ด, $A^n$์„ ๊ณ„์‚ฐํ•˜๋ฉด, ๊ทธ $i, j$ ๋ฒˆ์งธ ์นธ์€ $i \to j$ ๋กœ $n$๊ฐœ์˜ ๊ฐ„์„ ์„ ์‚ฌ์šฉํ•ด์„œ ๋„๋‹ฌํ•˜๋Š” ๋ฐฉ๋ฒ•์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜์— ํ•ด๋‹นํ•œ๋‹ค๋Š” ์‚ฌ์‹ค์ด ์ž˜ ์•Œ๋ ค์ ธ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๊ฐ€์ค‘์น˜๊ฐ€ 5 ์ดํ•˜์ด๋ฏ€๋กœ, ์ •์ ์„ ๋ณต์‚ฌํ•˜๋Š” ํŠธ๋ฆญ์„ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค. ๋งŒ์•ฝ 1๋ฒˆ ์ •์ ์—์„œ 2๋ฒˆ ์ •์ ์œผ๋กœ 3์˜ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค๋ฉด, $(1, 0)$ ์—์„œ $(2, 0)$ ์œผ๋กœ ๊ทธ์–ด์ฃผ๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ, $(1, 0)$ ์—์„œ $(2, 2)$ ๋กœ, $(2, 2) \to (2, 1) \to (2, 0)$ ์œผ๋กœ ๊ฐ€๊ฒŒ ํ•ด์„œ 3๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฑฐ์น˜๋„๋ก ๊ฐ•์ œํ•ฉ๋‹ˆ๋‹ค.
  • ์ด์ œ ์œ„ ์‚ฌ์‹ค์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

2009 Baltic Olympiad of Informatics P2, BOJ 3356 ๋ผ๋””์˜ค ์ „์†ก

  • ๋‚œ์ด๋„ Platinum IV
  • ๋ฌธ์ œ์˜ ์ •์˜๋ฅผ ์ž˜ ์ฝ์–ด๋ณด๋ฉด, KMP ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹คํŒจํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์—ฌ $n - p[n]$ ์ด ๋‹ต์ž„์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

2013 ํ•œ๊ตญ์ •๋ณด์˜ฌ๋ฆผํ”ผ์•„๋“œ ์ง€์—ญ๋ณธ์„  ๊ณ ๋“ฑ๋ถ€ 5๋ฒˆ, BOJ 7575 ๋ฐ”์ด๋Ÿฌ์Šค

  • ๋‚œ์ด๋„ Platinum V
  • $N$๊ฐœ์˜ ๋ฌธ์ž์—ด ๊ฐ๊ฐ์— ๋Œ€ํ•ด, ๊ธธ์ด๊ฐ€ $K$์ธ ๋ชจ๋“  ๋ถ€๋ถ„ ๋ฌธ์ž์—ด๊ณผ ๊ทธ ์—ญ ๋ฌธ์ž์—ด์„ ์ €์žฅํ•  ์ˆ˜ ์žˆ๋‹ค๋ฉด
  • ์ด๋“ค์„ ๋น„๊ตํ•ด์„œ ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.
  • ์‹œ๊ฐ„ ๋ณต์žก๋„์ƒ ์ด๋ฅผ ์ง์ ‘ ๋น„๊ตํ•  ์ˆ˜๋Š” ์—†์ง€๋งŒ, ํ•ด์‹œ๊ฐ’์„ ๋น„๊ตํ•  ์ˆ˜๋Š” ์žˆ์Šต๋‹ˆ๋‹ค.
  • ๋งค์šฐ ๋Š๋ฆฌ์ง€๋งŒ set_intersection์„ ์“ฐ๋ฉด ๊ตฌํ˜„์ด ๋งค์šฐ ์‰ฝ๊ณ , ์ด ๋ฌธ์ œ๋ฅผ ํ†ต๊ณผํ•˜๊ธฐ์—๋Š” ์ถฉ๋ถ„ํ•ฉ๋‹ˆ๋‹ค.

2017 ์—ฐ์„ธ๋Œ€ํ•™๊ต ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ฒฝ์ง„๋Œ€ํšŒ, BOJ 14574 ํ—ค๋ธ์Šค ํ‚ค์นœ

  • ๋‚œ์ด๋„ Platinum V
  • ๋Œ€๊ฒฐ์—์„œ ์Šน๋ฆฌํ•œ ์ชฝ์ด ์Šน์ฒœํ•ด๋ฒ„๋ฆฌ๊ธฐ ๋•Œ๋ฌธ์— ํ•œ ๋…ธ๋“œ๋ฅผ ๋‘ ๋ฒˆ ํฌํ•จํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.
  • ์ฆ‰โ€ฆ ๋Œ€์ง„ํ‘œ๊ฐ€ Spanning tree๋ฅผ ์ด๋ฃจ์–ด์•ผ๊ฒ ์Šต๋‹ˆ๋‹ค.
  • ์ฃผ์–ด์ง„ ์ ์ˆ˜ ํ•จ์ˆ˜๋กœ complete graph๋ฅผ ๋งŒ๋“ค๊ณ , ๊ทธ maximum spanning tree๋ฅผ ์“ฐ๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค.
  • ๊ทธ๋Ÿฐ๋ฐ, ์ด ํŠธ๋ฆฌ๋กœ ์˜ฌ๋ฐ”๋ฅธ ๋Œ€์ง„ํ‘œ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ์„๊นŒ์š”?
  • ๋„ค. DFS๋ฅผ ๋”ฐ๋ผ ๋Œ๋ฉด์„œ, ๋ฆฌํ”„ ๋…ธ๋“œ์™€ ๋ฆฌํ”„๊ฐ€ ์•„๋‹Œ ๋…ธ๋“œ ๊ฐ„์˜ ๊ฒฝ๊ธฐ์— ๋Œ€ํ•ด์„œ๋Š” ๋ฆฌํ”„ ๋…ธ๋“œ๊ฐ€ ์Šน๋ฆฌํ•˜๊ณ  ์Šน์ฒœํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. (๋ฆฌํ”„๊ฐ€ ์•„๋‹Œ ๋…ธ๋“œ๋Š” ๋‚˜์ค‘์— ๋˜ ์จ์•ผ ํ•˜๋ฏ€๋กœ). ์ด์ œ, ์ƒˆ๋กญ๊ฒŒ ๋ฆฌํ”„๊ฐ€ ๋œ ๋…ธ๋“œ๊ฐ€ ์žˆ๋‹ค๋ฉด ์ด ๋…ธ๋“œ๋Š” ์ž๊ธฐ parent ๋…ธ๋“œ์™€์˜ ๋Œ€๊ฒฐ์—์„œ ์Šน๋ฆฌํ•ด์„œ ์Šน์ฒœํ•ด๋„ ๋ฉ๋‹ˆ๋‹ค.
  • DFS๋ฅผ ์ด์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ๊ตฌํ˜„ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค.

2016 Nordic Collegiate Programming Contest, BOJ 13355 Bless You Autocorrect

  • ๋‚œ์ด๋„ Platinum I
  • ์†”์งํžˆ ์ด์ •๋„๋กœ ์–ด๋ ค์šด์ง€๋Š” ์ž˜ ๋ชจ๋ฅด๊ฒ ์Šต๋‹ˆ๋‹ค.
  • Trie๋ฅผ ๊ณจ์ž๋กœ ํ•œ ๊ทธ๋ž˜ํ”„๋ฅผ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ๋‹จ, autocomplete ๊ธฐ๋Šฅ์„ ์ด์šฉํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ๋ฌธ์ œ์˜ ์ •์˜์— ํ•ฉ๋‹นํ•˜๊ฒŒ TABํ‚ค๋ฅผ ๊ธธ์ด๊ฐ€ 1์ธ ๊ฐ„์„ ์œผ๋กœ ํ‘œํ˜„ํ•ด์ฃผ๊ณ , BACKSPACEํ‚ค๋„ ๊ธธ์ด๊ฐ€ 1์ธ ๊ฐ„์„ ์œผ๋กœ ํ‘œํ˜„ํ•ด ์ค๋‹ˆ๋‹ค.
  • ์ด๋ ‡๊ฒŒ ๋งŒ๋“  ๊ทธ๋ž˜ํ”„ ์œ„์—์„œ BFS๋ฅผ ๋Œ๋ ค์„œ, ๋ชจ๋“  ๋…ธ๋“œ๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋ฅผ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.
  • ์ด์ œ, query string์ด ์ฃผ์–ด์ง€๋ฉด, ์ด query string์˜ ์–ด๋””๊นŒ์ง€๋ฅผ trie ์œ„์—์„œ ์ฐพ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ๋ณด๊ณ , ๊ทธ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๋”ฐ ์˜จ ๋‹ค์Œ, ๋‚˜๋จธ์ง€๋Š” ์ผ์ผํžˆ ํƒ€์ดํ•‘ํ•ด์ฃผ๋ฉด ๋์ž…๋‹ˆ๋‹ค.
  • ๊ตฌํ˜„๋Ÿ‰์ด ๋งŽ์ง€๋งŒ ๊ฐ๊ฐ์„ ๋”ฐ๋กœ ๊ตฌํ˜„ํ•ด์„œ ํ•ฉ์น  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ๋ณ„๋กœ ์–ด๋ ต์ง€๋Š” ์•Š์Šต๋‹ˆ๋‹ค. ์ €๋Š” ๊ตฌํ˜„์˜ ํŽธ์˜๋ฅผ ์œ„ํ•ด ํŠธ๋ผ์ด์™€ ๊ทธ๋ž˜ํ”„๋ฅผ ๋”ฐ๋กœ๋”ฐ๋กœ ๋งŒ๋“ค์—ˆ์ง€๋งŒ, ๊ตฌํ˜„์„ ์กฐ์‹ฌํ•ด์„œ ํ•œ๋‹ค๋ฉด ํŠธ๋ผ์ด๋ฅผ ๋”ฐ๋กœ ๋งŒ๋“ค์ง€ ์•Š๊ณ  ๋ฐ”๋กœ ์ ์ ˆํžˆ ๊ทธ๋ž˜ํ”„๋ฅผ (ํŠธ๋ผ์ด๋ฅผ ๋ผˆ๋Œ€ ์‚ผ์•„) ๊ตฌํ˜„ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

2017 Central European Olympiad in Informatics, BOJ 15246 One Way Streets

  • ๋‚œ์ด๋„ Platinum II
  • IOI๋ฅผ ์ œ์™ธํ•˜๊ณ  ๊ฐ€์žฅ ์–ด๋ ค์šด OI์ค‘ ํ•˜๋‚˜์ธ CEOI์˜ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์†”์งํžˆ ์ €๋Š” P2๋ณด๋‹ค ํ›จ์”ฌ ์–ด๋ ต๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.
  • ๋ณ„๋„๋กœ ํฌ์ŠคํŒ…ํ•  ์˜ˆ์ •์ž…๋‹ˆ๋‹ค.