๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์ „์ฒด ๊ธ€ (117)

๐˜š๐˜ญ๐˜ฐ๐˜ธ ๐˜ฃ๐˜ถ๐˜ต ๐˜ด๐˜ต๐˜ฆ๐˜ข๐˜ฅ๐˜บ

[๋ฐฑ์ค€] 11651๋ฒˆ: ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ 2 - C++

๋ฌธ์ œ 2์ฐจ์› ํ‰๋ฉด ์œ„์˜ ์  N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ขŒํ‘œ๋ฅผ y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ, y์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ์ •๋ ฌํ•œ ๋‹ค์Œ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ ์˜ ๊ฐœ์ˆ˜ N (1 โ‰ค N โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” i๋ฒˆ์ ์˜ ์œ„์น˜ xi์™€ yi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (-100,000 โ‰ค xi, yi โ‰ค 100,000) ์ขŒํ‘œ๋Š” ํ•ญ์ƒ ์ •์ˆ˜์ด๊ณ , ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๋‘ ์ ์€ ์—†๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ ์„ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋ ฌ์„ ์ด์šฉํ•˜์—ฌ ํ‘ธ๋Š” ๋ฌธ์ œ. 11650๋ฒˆ ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ ์™€ ๋™์ผํ•˜๊ฒŒ ํ’€๋ฉด ๋œ๋‹ค. ๋ณ‘ํ•ฉ ์ •๋ ฌ์„ ์‚ฌ์šฉํ•˜์—ฌ ํ’€์—ˆ๊ณ , y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ - y์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์•ผ๋˜๊ธฐ ๋•Œ๋ฌธ์— 11650๋ฒˆ ๋ฌธ์ œ ํ’€๋•Œ๋ž‘ ์‚ด์ง๋งŒ ๋‹ค๋ฅด๊ฒŒ ..

[๋ฐฑ์ค€] 11650๋ฒˆ: ์ขŒํ‘œ ์ •๋ ฌํ•˜๊ธฐ - C++

๋ฌธ์ œ 2์ฐจ์› ํ‰๋ฉด ์œ„์˜ ์  N๊ฐœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ขŒํ‘œ๋ฅผ x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ, x์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์„œ๋กœ ์ •๋ ฌํ•œ ๋‹ค์Œ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— ์ ์˜ ๊ฐœ์ˆ˜ N (1 โ‰ค N โ‰ค 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” i๋ฒˆ์ ์˜ ์œ„์น˜ xi์™€ yi๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (-100,000 โ‰ค xi, yi โ‰ค 100,000) ์ขŒํ‘œ๋Š” ํ•ญ์ƒ ์ •์ˆ˜์ด๊ณ , ์œ„์น˜๊ฐ€ ๊ฐ™์€ ๋‘ ์ ์€ ์—†๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์ ์„ ์ •๋ ฌํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์ •๋ ฌ์„ ์ด์šฉํ•˜์—ฌ ํ‘ธ๋Š” ๋ฌธ์ œ. ๋ณ‘ํ•ฉ ์ •๋ ฌ์„ ์‚ฌ์šฉํ•˜์—ฌ ํ’€์—ˆ๊ณ , x์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ - x์ขŒํ‘œ๊ฐ€ ๊ฐ™์œผ๋ฉด y์ขŒํ‘œ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆœ์œผ๋กœ ์ •๋ ฌํ•ด์•ผ๋˜๊ธฐ ๋•Œ๋ฌธ์— ์กฐ๊ฑด๋ฌธ์„ ํ•˜๋‚˜ ๋” ๋ถ™์˜€๋‹ค. ์ฝ”๋“œ #include void merge(int** sorted,..

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ์ด๋ถ„ ํƒ์ƒ‰(Binary Search)

1. ์ด๋ถ„ ํƒ์ƒ‰ ; Binary Search 1.1 ๊ฐœ๋… ๋ฒ”์œ„๋ฅผ ์ ์  ์ขํ˜€๊ฐ€๋ฉฐ ํƒ์ƒ‰์„ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์ด์ง„ ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ํ•œ๋‹ค. ํ•˜๋‚˜์”ฉ ์ฐพ๋Š” ๊ฒƒ์ด ์•„๋‹Œ left์™€ right ์–‘์ชฝ์—์„œ ํƒ์ƒ‰์„ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ผ๋ฐ˜ ํƒ์ƒ‰์— ๋น„ํ•ด ์†๋„๊ฐ€ ๋น ๋ฅด๋‹ค. ์‹œ๊ฐ„๋ณต์žก๋„๋Š” ์ผ๋ฐ˜ ํƒ์ƒ‰์ด O(n), ์ด๋ถ„ ํƒ์ƒ‰์ด O(log n)์ด๋‹ค. ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ž‘๋™ํ•˜๋Š” ๋ฐฉ์‹์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค. ๋ฏธ๋ฆฌ ์ •๋ ฌ๋œ ๋ฐฐ์—ด์—์„œ, ์ •ํ•ด๋†“์€ ์ธ๋ฑ์Šค ์œ„์น˜์ธ left์™€ right๋กœ mid ๊ฐ’์„ ์ •ํ•ด์คŒ(mid = (left + right) / 2) mid๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ฐ’๊ณผ ๋ชฉํ‘œ ๊ฐ’(result)์„ ๋น„๊ตํ•œ๋‹ค. mid > result, right = mid - 1 mid๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ฐ’๋ณด๋‹ค ๋ชฉํ‘œ ๊ฐ’์ด ๋” ์ž‘์„ ๊ฒฝ์šฐ, ๋ชฉํ‘œ ๊ฐ’์ด ์ ˆ๋ฐ˜ ์•„๋ž˜์ชฝ์— ํฌํ•จ๋œ ๋ฒ”์œ„ ์•ˆ์— ๋“ค์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— ri..