0. ๊ธ์ด ํ๋ฌ๊ฐ๋ ๋ฐฉํฅ
๋จผ์ ๊ฐ๋ ์ค๋ช ์ ํ๊ณ , ํฌ ํฌ์ธํฐ๋ฅผ ํ์ฉํ๋ ๋ํ์ ์ธ ๋ฌธ์ 2๊ฐ๋ฅผ ์ง์ ํ์ด๋ณด๋ฉฐ, ๊ฐ๋ ์ ๋ํ ๋ณด์ถฉ์ ํ๊ฒ ๋ค.
1. ๊ฐ๋
1์ฐจ์ ๋ฐฐ์ด์ ๋ ๊ฐ์ ํฌ์ธํฐ๋ฅผ ๋๊ณ , ๋ ํฌ์ธํฐ์ ์๋ฏธ๋ฅผ ๋ถ์ฌํ์ฌ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ธฐ์
๋ฐฐ์ด ์์์ ํน์ ์กฐ๊ฑด์ ๊ฐ์ ๊ตฌํ๋ ๋ฌธ์ ์์, ์ผ๋ฐ์ ์ผ๋ก ์๊ฐ ๋ณต์ก๋๊ฐ O((N^{2}))๊ฐ ๋ ๋ค๋ฉด, ํฌ ํฌ์ธํฐ ๊ธฐ๋ฒ์ ํ์ฉํ๋ฉด ์๊ฐ ๋ณต์ก๋๋ฅผ O(N)์ผ๋ก ์ค์ผ ์ ์๋ค. (์ด์ ๋ ํ์ฉ์ ์ดํด๋ณด๋ฉฐ ์ค๋ช
ํ๊ฒ ๋ค.)
(1) ์ ํ
ํฌ ํฌ์ธํฐ๋ฅผ ์ด์ฉํ๋ ์ ํ์๋ ํฌ๊ฒ 2๊ฐ์ง๊ฐ ์๋ค.
a.๋จ๋ฐฉํฅ ์ด์ฉ
L ํฌ์ธํฐ์ R ํฌ์ธํฐ๊ฐ ํ์ชฝ ๋ฐฉํฅ์ผ๋ก๋ง ์์ง์ด๋ ๊ฒ์ด๋ค. ์ฌ๋ผ์ด๋ฉ ์๋์ฐ์ ์๋์ ์๋ฏธํ๋ค๊ณ ๋ณด๋ฉด ๋๋ค. ์ฌ๋ผ์ด๋ฉ ์๋์ฐ์ ๋ค๋ฅธ ์ ์ ํฌ์ธํฐ์ ๋ฐ๋ผ ๊ตฌ๊ฐ์ ๊ธธ์ด๊ฐ ๊ฐ๋ณ์ ์ด๋ผ๋ ๊ฒ์ด๋ค.
b. ์๋ฐฉํฅ ์ด์ฉ
๋ ๊ฐ์ ํฌ์ธํฐ๋ฅผ ์๋ก ๋ง์ฃผ๋ณด๊ณ ์ต์ข ์ ์ผ๋ก ๋ง๋๋๋ก ํฌ์ธํฐ๋ฅผ ์ด์ฉํ๋ ๋ฐฉ๋ฒ์ด๋ค.
2. ํ์ฉ
(1) ์๋ค์ ํฉ2( ๋ฐฑ์ค 2003 )
์์์ ๋ณด๋ ๋จ๋ฐฉํฅ ์ด์ฉ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ๋ฉด๋๋ค.
๊ตฌ๊ฐ ๋ด์ ํฉ์ S, target ํฉ์ M์ด๋ผ๊ณ ํ ๋,S < M
: S๊ฐ ์ปค์ ธ์ผ ํจ์ผ๋ก, R์ ์์ง์ธ๋ค. (๊ตฌ๊ฐ ๋ด์ ํฉ ์ปค์ง๋๋ก)S >= M
: S๊ฐ ์์์ ธ์ผํจ์ผ๋ก, L์ ์์ง์ธ๋ค. ๋ง์ฝ S==M
์ด๋ฉด ๋ต์ด ๋ ์ ์๋ ๊ตฌ๊ฐ์์ผ๋ก ans_cnt๋ฅผ +1 ์ฌ๋ฆฐ๋ค.
๋ง์ฝ ํด๋น ๋ฌธ์ ๋ฅผ ์์ ํ์์ผ๋ก ํผ๋ค๋ฉด? :thinking:
์์ ํ์์ผ๋ก ํผ๋ค๋ ๊ฒ์ L๊ณผ R์ด ์ํ์ ๊ด๊ณ๊ฐ ์๋ ์์ง์ ๊ด๊ณ๊ฐ ๋๋ค๋ ์๋ฏธ์ด๋ค.
L์ ๋จผ์ ๊ณ ๋ฅด๊ณ , R์ ๋์ค์ ๊ณจ๋ผ์ ๊ทธ ๊ตฌ๊ฐ ๋ด์ ํฉ์ ๊ตฌํด์ผ ํ๋ค. L์ ๊ณ ๋ฅด๋ ํ์๋ O(N), R์ L ํฌ์ธํฐ๊ฐ ๊ฐ๋ฆฌํค๋ ๊ฐ๋ณด๋ค ํฐ ๊ฐ ์ค์์ ๊ณจ๋ผ์ผํจ์ผ๋ก ํ๊ท O(N/2)์ ๊ณ์ฐํ์๊ฐ ๋ค ๊ฒ์ด๋ค. L์ ๊ณ ๋ฅผ ๋๋ง๋ค, R์ ๋ค์ ๊ณจ๋ผ์ค์ผ ํจ์ผ๋ก, ์ด ๋์ ์ฐ์์ ์ด๋ค. ๋ฐ๋ผ์ O(N * N/2) ์ด์ฌ์, ์ต์
์ ์๊ฐ ๋ณต์ก๋๋ O(\(N^{2}\))
๊ฐ ๋ ๊ฒ์ด๋ค.
๋ฐ๋ฉด, ํฌ ํฌ์ธํฐ๋ฅผ ํ์ฉํ๋ค๋ฉด, L๊ณผ R ํฌ์ธํฐ๋ ์ํ์ ๊ด๊ณ
์ด๋ค. L์ ์์ง์ธ๋ค๊ณ ํด์ ํ์ฐ์ ์ผ๋ก R์ ์์ง์ด์ง ์๋๋ค. ๊ทธ ๋ฐ๋๋ ๋ง์ฐฌ๊ฐ์ง๋ค. ๋์ ๊ด๊ณ๋ ๋น์ฐ์์ ์ด๊ณ , ์ต์
์ ์ํฉ์ ๊ฐ์ ํด๋, L์ N๋ฒ ์์ง์ด๊ณ , R์ N๋ฒ ์์ง์ด๋ 2N๋ฒ์ ๊ณ์ฐ๋ง ํ๋ฉด ๋๋ค. ๋ฐ๋ผ์ ์ต์
์ ์๊ฐ๋ณต์ก๋๋ O(N)
์ด๋ค.
(2) ๋ ์ฉ์ก
๋ฌธ์ ์ ์๊ตฌ์ฌํญ์ ์ฉ์ก์ ๊ณ ์ ๊ฐ์ด ์ค๋ฆ์ฐจ์์ผ๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ด ์ค์์ 2๊ฐ์ ์ฉ์ก์ ๋ฝ์ ๊ณ ์ ๊ฐ์ ํฉํด์ 0์ ๊ฐ์ฅ ๊ฐ๊น์ด ๊ฒฝ์ฐ๋ฅผ ๊ตฌํ๋ ๊ฒ์ด๋ค. ํด๋น ๋ฌธ์ ๋ ์๋ฐฉํฅ ์ด์ฉ์ด ํ์ํ ๋ฌธ์ ์ด๋ค. ์ด์ ๋ ์์ ๊ฐ์ด ์
๋ ฅ์ ํฌํจ๋๊ธฐ ๋๋ฌธ
์ด๋ค.
๋จ๋ฐฉํฅ์ผ๋ก ํ์ด๋ณด๋ฉด ์ด๋จ๊น? ์์ ์๋ค์ ํฉ ๋ฌธ์ ๋ฅผ ํ๋ฏ์ด,
๋ ์ฉ์ก์ ํฉ < 0
์ด๋ฉด R ํฌ์ธํฐ๋ฅผ ์์ง์ธ๋ค.๋ ์ฉ์ก์ ํฉ >= 0
์ด๋ฉด L ํฌ์ธํฐ๋ฅผ ์์ง์ธ๋ค.
๋ผ๊ณ ๊ฐ์ ํด๋ณด์.
๋๊น์ง Rํฌ์ธํฐ๋ง ์์ง์์ผ๋ก ๋ต์ ๊ตฌํ ์ ์๋ค. ํด๋น ์์์์๋ 0์ด ๋์ค๋๋ก ๋ ์ฉ์ก์ ๊ณ ๋ฅด๋ ๊ฒฝ์ฐ์ ์๊ฐ ๋ง์๋ฐ๋ ๋ถ๊ตฌํ๊ณ ๋ง์ด๋ค. ๋ฐ๋ฉด ํฌ ํฌ์ธํฐ๋ฅผ ์๋ฐฉํฅ์์ ์ด์ฉํ๋ค๋ฉด ๋ ์ฝ๊ฒ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ฐพ์ ์ ์๋ค.
๋ ์ฉ์ก์ ํฉ < 0
: L ํฌ์ธํฐ๋ฅผ ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋๋ ์ฉ์ก์ ํฉ >= 0
: Rํฌ์ธํฐ๋ฅผ ์ผ์ชฝ์ผ๋ก ์ด๋