์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- ๋์ ํฉ
- ๊น์ด์ฐ์ ํ์
- ๋๋น์ฐ์ ํ์
- ํฐ์คํ ๋ฆฌ์ฑ๋ฆฐ์ง
- ํ์ด์ฌ
- ๋ค์ด๋๋ฏนํ๋ก๊ทธ๋๋ฐ
- SQL
- ์์ํ์
- ์ค๋ธ์
- ๋ณํฉ์ ๋ ฌ
- ๊ทธ๋ํ
- ์๊ณ ๋ฆฌ์ฆ
- ๊ตฌํ
- ๋ฐ์ดํฐ๋ฒ ์ด์ค
- ์ฐ์ ์์ํ
- ๋์ ๊ณํ๋ฒ
- skala
- LIS
- DP
- ๋จธ์ง์ํธ
- skala1๊ธฐ
- ํ๋ก๊ทธ๋๋จธ์ค
- ๊ทธ๋ํํ์
- BFS
- ๊ทธ๋ฆฌ๋
- DFS
- ์ํ
- ๋ฐฑ์ค
- db
- ์ ๋ ฌ
- Today
- Total
๋ชฉ๋ก์ ์ฒด ๊ธ (117)
๐๐ญ๐ฐ๐ธ ๐ฃ๐ถ๐ต ๐ด๐ต๐ฆ๐ข๐ฅ๐บ
๋ฌธ์ 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๋ฒ ๋ฌธ์ ํ๋๋ ์ด์ง๋ง ๋ค๋ฅด๊ฒ ..
๋ฌธ์ 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,..

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..