[c++] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐœ๋…๊ณต๋ถ€ :: ์ •๋ ฌ (๊ฐœ์š”)

์ •๋ ฌ

 ์–ด๋–ค ๋ฐ์ดํ„ฐ๋“ค์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ์ด๋ฅผ ์ •ํ•ด์ง„ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ '์ •๋ ฌ'์ด๋‹ค. ๋ณดํ†ต ์ปดํ“จํ„ฐ์—์„œ๋Š” ํƒ์ƒ‰์„ ์œ„ํ•ด์„œ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•œ๋‹ค. ํƒ์ƒ‰์€ ์ •๋ ฌ์„ ํ†ตํ•ด ํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋” ๊ฐ•๋ ฅํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์žˆ์ง€๋งŒ, ํ•œ ๋ฒˆ ๋ฐ์ดํ„ฐ๋ฅผ ์ •๋ ฌํ•ด๋‘๋ฉด ๋‹ค์Œ๋ถ€ํ„ฐ๋Š” ์ด์ง„ ํƒ์ƒ‰์ด๋ผ๋Š” ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ช‡ ๋ฒˆ์ด๊ณ  ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์œ ์šฉํ•˜๋‹ค.

 ๊ทธ๋ž˜์„œ ์ฃผ์–ด์ง„ ๋ฌด์ž‘์œ„์˜ ๋ฐ์ดํ„ฐ๋ฅผ ์ •๋ ฌํ•˜๋Š” ๊ฒƒ์— ๋งŽ์€ ์—ฐ๊ตฌ์ž๋“ค์ด ๋ฐฉ๋ฒ•์„ ๋‚ด๋†“์•˜๋Š”๋ฐ, ์•ž์œผ๋กœ ์„ค๋ช…ํ•  6๊ฐœ์˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๊ทธ ์™ธ์—๋„ ๋งŽ์€ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์กด์žฌํ•œ๋‹ค.

 ๋ชจ๋“  ์ •๋ ฌ์˜ ์„ค๋ช…์— ์•ž์„œ์„œ ์˜ˆ์ œ๋กœ ์„ค๋ช…ํ•  ๋ฐ์ดํ„ฐ๋Š” ๋‹ค์Œ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๋ฌด์ž‘์œ„๋กœ ๋ฐฐ์น˜๋˜์–ด์žˆ๋Š” 1~7์˜ ๋ฐ์ดํ„ฐ์ด๋‹ค.

 ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ๋น„๊ต + ์ด๋™์œผ๋กœ ์ธก์ •ํ•œ๋‹ค.

 

ํŠน์„ฑ

์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์—ฌ๋Ÿฌ ๊ธฐ์ค€์— ๋”ฐ๋ผ ๋‚˜๋‰  ์ˆ˜ ์žˆ๋‹ค.

  • ์‹œ๊ฐ„ ๋ณต์žก๋„์— ๋”ฐ๋ฅธ ๋ถ„๋ฅ˜
    • ๋‹จ์ˆœํ•˜์ง€๋งŒ ๋น„ํšจ์œจ์ ์ธ O(n^2) ์•Œ๊ณ ๋ฆฌ์ฆ˜ : ์‚ฝ์ž… ์ •๋ ฌ, ์„ ํƒ ์ •๋ ฌ, ๋ฒ„๋ธ” ์ •๋ ฌ ๋“ฑ
    • ๋ณต์žกํ•˜์ง€๋งŒ ํšจ์œจ์ ์ธ O(nlgn) ์•Œ๊ณ ๋ฆฌ์ฆ˜ : ํ€ต ์ •๋ ฌ, ํžˆํ”„ ์ •๋ ฌ, ํ•ฉ๋ณ‘ ์ •๋ ฌ, ๊ธฐ์ˆ˜ ์ •๋ ฌ ๋“ฑ
  • ์•ˆ์ •์„ฑ์— ๋”ฐ๋ฅธ ๋ถ„๋ฅ˜
    • ์•ˆ์ • ์ •๋ ฌ : ์ •๋ ฌ ํ›„์—๋„ ๋™์ผํ•œ ํ‚ค ๊ฐ’์„ ๊ฐ–๋Š” ์›์†Œ์˜ ์ƒ๋Œ€์  ์œ„์น˜๊ฐ€ ๋ฐ”๋€Œ์ง€ ์•Š์Œ
    • ๋ถˆ์•ˆ์ • ์ •๋ ฌ : ์•ˆ์ • ์ •๋ ฌ๊ณผ ๋ฐ˜๋Œ€

์„ ํƒ ์ •๋ ฌ, ๋ฒ„๋ธ” ์ •๋ ฌ, ์‚ฝ์ž… ์ •๋ ฌ

ํ€ต ์ •๋ ฌ, ํ•ฉ๋ณ‘ ์ •๋ ฌ

ํž™ ์ •๋ ฌ, ์‰˜ ์ •๋ ฌ

๋ฐ˜์‘ํ˜•