Algorithm/์๊ณ ๋ฆฌ์ฆ
[Algorithm] ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ (Two Pointers)
1. ํฌ ํฌ์ธํฐ(Two Pointers) ์๊ณ ๋ฆฌ์ฆ ๋ฐฐ์ด์ ํน์ ์ฐ์๋ ๊ตฌ๊ฐ์ ์ฒ๋ฆฌํ๋ ๊ฒฝ์ฐ ์ฌ์ฉ ๋ฆฌ์คํธ์ ์์ฐจ์ ์ผ๋ก ์ ๊ทผํด์ผ ํ ๋, ๋๊ฐ์ ์ ์ ์ด์ฉํด ์์น๋ฅผ ๊ธฐ๋กํ๋ฉด์ ์ฒ๋ฆฌํ๋ ๊ธฐ๋ฒ $O(N)$ 2. ์์ ๋ฌธ์ [1,2,3,2,5] ํฉ์ด 5 ์ธ ๋ถ๋ถ ์ฐ์ ์์ด์ ๊ฐ์ ๊ตฌํ์์ค ๊ฐ ์ง์ ์์ ๊ตฌ๊ฐ์ ๋๋ ค๊ฐ๋ฉฐ ์ฐ์๋๋ ์๋ฅผ ํ์ธํ๋ ๋ฐฉ๋ฒ? ์๊ฐ ๋ณต์ก๋ : $O(n^2)$ ๋ฐ์ดํฐ์ ๊ฐ์๊ฐ ๋ง์์ง๋ฉด ์๊ฐ์ด ๋ง์ด ๊ฑธ๋ฆผ $O(N)$์ผ๋ก ํ๋ ค๋ฉด? ํฌ ํฌ์ธํฐ ์๊ณ ๋ฆฌ์ฆ ์ฌ์ฉํ๊ธฐ 3. ํ์ด start, end ํฌ์ธํฐ๋ฅผ ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค๋ฅผ ๊ฐ๋ฆฌํค๋๋ก! ํฉ์ด 5๋ณด๋ค ์์ผ๋ฉด end ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ (ํฉ์ ๋๋ฆผ) ํฉ์ด 5๋ณด๋ค ํฌ๋ฉด start๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ (ํฉ์ ์ค์) ํฉ์ด 5๊ฐ๋๋ฉด count, start๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ ..