๊ธ€ ์ž‘์„ฑ์ž: ๊ฐœ๋ฐœํ•˜๋Š” ํ›ˆ์ด

2021.09.04 ์˜ค๋Š˜์˜ ๋ฐฐ์›€

์˜ค๋Š˜ ํ•œ ์ผ.

  • ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€๊ธฐ

์˜ค๋Š˜ ์ƒˆ๋กœ ๋ฐœ๊ฒฌํ•œ ๊ฒƒ.

  • Set ์˜ intersection ํ•จ์ˆ˜์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(N)์ด๋‹ค.
  • Lower Bound ๋‚˜ Upper Bound๋ฅผ ๋น ๋ฅด๊ฒŒ ์ฐพ์•„์•ผํ•œ๋‹ค๋ฉด ์ด๋ถ„ํƒ์ƒ‰์„ ์‚ฌ์šฉํ•˜์ž.

์˜ค๋Š˜ ๋Š๋‚€ ๊ฒƒ.

  • ์˜ค๋Š˜์€ ์นด์นด์˜ค ๋ฌธ์ œ๋ฅผ ํ’€์—ˆ๋Š”๋ฐ, ์‰ฝ์ง€ ์•Š์•˜๋‹ค. ๊ฐ„๋‹จํ•˜๊ฒŒ ์ƒ๊ฐํ•˜๋ฉด ๋˜๋Š” ๊ฑธ ๋„ˆ๋ฌด ๋ณต์žกํ•˜๊ฒŒ ์ƒ๊ฐํ•˜๊ธฐ๋„ ํ•˜๊ณ , ์•Œ๊ณ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ธ๋ฐ ์ ์šฉ์„ ์ž˜ ๋ชปํ•˜๋Š” ๊ฒฝ์šฐ๋„ ๋งŽ์€ ๊ฒƒ ๊ฐ™๋‹ค. ์—ฐ์Šต์ด ๋” ํ•„์š”ํ•œ ๊ฒƒ ๊ฐ™๋‹ค.

์•ž์œผ๋กœ์˜ ๊ณ„ํš.

  • ๋‚ด์ผ๋„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ’€๊ณ  ๋””๋น„ ๊ณต๋ถ€๋ฅผ ์ข€ ํ•ด๋‘์ž.

์˜ค๋Š˜์˜ ๊ฐ์‚ฌ.

  • ํฌ๊ธฐํ•˜์ง€ ์•Š๊ณ  ๋ฌธ์ œ์— ์ง‘์ค‘ํ•  ์ˆ˜ ์žˆ๋Š” ํž˜์„ ์ฃผ์…”์„œ ๊ฐ์‚ฌํ•˜๊ณ , ์นœ๊ตฌ๋“ค์„ ๋งŒ๋‚˜ ํšŒ๋ณตํ•˜๋Š” ์‹œ๊ฐ„์„ ๊ฐ€์ง€๊ฒŒ ํ•˜์‹ฌ์— ๊ฐ์‚ฌํ•ฉ๋‹ˆ๋‹ค.