์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- ์คํ๋ง
- ์คํ
- ์ฅ๊ณ
- R
- ์ฝ๋์
- Deque
- ํ
- ํ์ด์ฌ
- counter
- ๋ฐฑ์ค
- MySQL
- ๊ฐ๋ฆ
- 2๋จ๊ณ
- ํ๋ก๊ทธ๋๋จธ์ค
- 1๋จ๊ณ
- ์ฝ๋ฉํ ์คํธ
- ๋ฐฑ์ค c++
- ์ํด๋ฆฌ ์ฑ๋ฆฐ์ง
- Lambda
- ํด์
- Servlet
- ๋ฐฐ์ด
- JSP
- JavaScript
- ๋ ์์ ํฉ
- Set
- ์๋ฐ
- hash
- jquery
- ํฌ ํฌ์ธํฐ
- Today
- Total
๋ชฉ๋ก๋ ์์ ํฉ (2)
Development
์ฝ๋ฉํ ์คํธ๋ฅผ ํ๋ค๋ณด๋ฉด ํฌ ํฌ์ธํฐ๋ก ํ์ด์ผํ๋ ๋ฌธ์ ๋ค์ ์์ฃผ ๋ณผ ์ ์์ต๋๋ค. ์ค๋์ ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด ์์๋ด ์๋ค. [ํฌ ํฌ์ธํฐ(Two Pointers) ์๊ณ ๋ฆฌ์ฆ] ๋ฆฌ์คํธ์ ์์ฐจ์ ์ผ๋ก ์ ๊ทผํด์ผ ํ ๋ ๋๊ฐ์ ์ ์ ์์น๋ฅผ ๊ธฐ๋กํ๋ฉด์ ์ฒ๋ฆฌํ๋ ์๊ณ ๋ฆฌ์ฆ ๋ฆฌ์คํธ์ ๋ด๊ธด ๋ฐ์ดํฐ์ ์์ฐจ์ ์ผ๋ก ์ ๊ทผํด์ผ ํ ๋๋ ์์์ ๊ณผ ๋์ 2๊ฐ์ ์ ์ผ๋ก ์ ๊ทผํ ๋ฐ์ดํฐ์ ๋ฒ์๋ฅผ ํํํ ์ ์๋ค. ์ ๊ทธ๋ฆผ๊ณผ๊ฐ์ด ๋ ๊ฐ์ ํฌ์ธํฐ(์ )์ ์์น๋ฅผ ๊ธฐ๋กํ๋ฉด์ ์ฒ๋ฆฌํ๋ค. [์๊ฐ๋ณต์ก๋] O(N) ๋งค ๋ฃจํ๋ง๋ค ํญ์ ๋ ํฌ์ธํฐ ์ค ํ๋๋ 1์ฉ ์ฆ๊ฐํ๊ณ ๊ฐ ํฌ์ธํฐ๊ฐ n๋ฒ ๋์ ์ฆ๊ฐํด์ผ ์๊ณ ๋ฆฌ์ฆ์ด ๋๋๋ค. ๊ฐ๊ฐ ๋ฐฐ์ด ๋์ ๋ค๋ค๋ฅด๋๋ฐ O(N)์ด๋ผ ๋์ ํฉํด๋ ์ฌ์ ํ O(N)์ด๋ค. [์์ ] ๋ฐฑ์ค 3237 ๋ ์์ ํฉ์ด ํฌ ํฌ์ธํฐ์ ์์ ์ ๋๋ค. ht..
๋ฌธ์ https://www.acmicpc.net/problem/3273 3273๋ฒ: ๋ ์์ ํฉ n๊ฐ์ ์๋ก ๋ค๋ฅธ ์์ ์ ์ a1, a2, ..., an์ผ๋ก ์ด๋ฃจ์ด์ง ์์ด์ด ์๋ค. ai์ ๊ฐ์ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 1000000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์์ด๋ค. ์์ฐ์ x๊ฐ ์ฃผ์ด์ก์ ๋, ai + aj = x (1 ≤ i < j ≤ n)์ ๋ง์กฑํ๋ www.acmicpc.net ํ์ด ๋ฌธ์ ํธ๋ ๋ฐฉ์์ ๊ฐ์ง๋ง ๋ค๋ฅธ์ฌ๋ ์ฝ๋๊ฐ ๋ ๊น๋ํ์ฌ ๊ฐ์ ธ์๋ค. ์ด ๋ฌธ์ ๋ start์ end๋ฅผ ์ฌ์ฉํ๋ ํฌ ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํด์ผํ๋ค. ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ์ ํด์ฃผ๊ณ ์ ๋์์ ํฉ์ ๊ตฌํด๊ฐ๋ฉด์ ๋ต์ ์ฐพ๋ ๋ฐฉ์์ด๋ค. start๋ฅผ ์ฒซ ์ธ๋ฑ์ค, end๋ฅผ ๋ง์ง๋ง ์ธ๋ฑ์ค๋ก ์ง์ ํ๊ธฐ์ํด start = 0, end = n-1์ ํด์ค๋ค. start๋ณด๋ค ..