๋จธ์ ๋ฌ๋ ์ ๋ฌธ ๊ธ ๋๋ฌด ์ข์์ต๋๋ค!ย ๊ธ์ด์ด ๋ถ๊ป ๊ฐ์ฌํ๊ณ ์.
ํน์ ์์ ๋๋ฌธ์ ์ดํด๊ฐ ์ ๋๋ค ์ถ์ ๋ถ๋ค์ ์ํด ์์ ํด์ค์ ํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
์๊ธ๊ณผ ๊ฐ์ด ๋ณด๊ธฐ๋ฅผ ๊ถํฉ๋๋ค๋ง ๋ชจ๋ฐ์ผ์ด๋ผ๋ฉด ๋ญ... ์ด์ฉ ์ ์์ฃ .
์, ๊ณ 1 ์์ค ์งํฉ ๊ธฐํธ๋ค์ ์์์ฃ ? ๊ทธ๊ฑด ๋ฐ๋ก ์ค๋ช ์ํฉ๋๋ค~
๋จผ์ ์ด๊ฑด, '๊ตต์ x' (ํฐ X ๋ง๊ณ )์ x1, x2๋ผ๋ ๋ ๊ฐ์ง ์ ๋ณด๋ฅผ ์ ์ฅํด๋๋ ๊ฐ๋ ์ผ๋ก ์ดํดํ์๋ฉด ํธํฉ๋๋ค.
๊ทธ๋ฌ๋ฉด ๋งจ ์์ ํฐ X๋ ๋ญ๋? ๊ฐ๋ฅํ '๊ตต์ x'๋ค์ ๋ชจ์กฐ๋ฆฌ ๋ชจ์๋ ๊ฒ์ ๋๋ค!ย
'๊ตต์ x'๋ ์ด๋ค ๊ธ ํ๋, ํฐ X๋ ์ฐ๋ฆฌ๊ฐ ํ์ฌ ์๊ณ ์๋ ๋ชจ๋ ๊ธ๋ค์ ๋ชจ์๋์ ์งํฉ์ย ์๋ฏธํ๋ค๊ณ ์๊ฐํ์๋ฉด ๋๊ฒ ๋ค์.
๋ฌผ๋ก ์๋ฐํ๊ฒ๋ ๊ทธ ๊ธ์ ์ ๋IP, ์ ๋ชฉ์ด๋ผ๋ ๋ ๊ฐ์ง ํน์ฑ์ ์๋ฏธํฉ๋๋ค.
๋์ด๊ฐ์ฃ . ์ฌ๊ธฐ์ ์๋ฅผ ๋ค์ด์ (x1, y1)์์, x1์ด '๊ตต์ x'์ฃ ? ์ ๋ IP๊ฐ ์๋๋๋ค!ย
์ฆ, ์ฌ๋ฌ ๊ฐ์ '๊ตต์ x'๊ฐ ์๋๋ฐ, x1์ ๊ตต์ x ์ค ์ฒซ๋ฒ์งธ, ์ฆ ์ฒซ๋ฒ์งธ ๊ธ. x2๋ ๋๋ฒ์งธ ๊ธ... ์ด๋ฐ ์์ผ๋ก ์ดํดํ๋ฉด ํธํฉ๋๋ค.
๊ทธ๋ฌ๋๊น (x1, y1)=((x1,x2),y1). ๋์ถฉย ์ด๋ฐ ๊ฐ๋ ์ด๋ค ์ ๋.
๊ทธ๋ฆฌ๊ณ ์ด์ ๋ (x1, y1)์ด ํ๋์ ๊ธ(์ ํํ๋, ๊ทธ ๊ธ์ ์ธ ๊ฐ์ง ํน์ฑ. ์ ๋IP, ์ ๋ชฉ, ๋ถํ๊ธ์ธ์ง ์ ๋ณด๊ธ์ธ์ง)์ ์๋ฏธํฉ๋๋ค.ย
S๋ ๊ทธ๋ฐ ๊ธ๋ค, ์ฐ๋ฆฌ๊ฐ ๊ฐ์ง ์๋ฃ๋ค์ ๋ชจ์๋์ ๋์๊ด ๊ฐ๋ ์ด๊ณ ์.
์, X ๊ณฑํ๊ธฐ Y๋ผ๋ ๊ฒ ์ค๋ฅธ์ชฝ์ ๋ณด์ด์ค ๊ฒ๋๋ค. ๊ฑฐ๊ธฐ์ ๊ณฑํ๊ธฐ๋ ๋ฐ์นด๋ฅดํธ๊ณฑ์ด๋ผ๊ณ ํ๋๋ฐ,
์๋ฅผ ๋ค์ด์ ์งํฉ A={1,2}, B={1,3,4}๊ฐย ์์ผ๋ฉด,
A ๋ฐ์นด๋ฅดํธ๊ณฑ B๋ {(1,1), (1,3), (1,4), (2,1), (2,3), (2,4)}์ ๋๋ค. ํ๋์ฉ ๊ณจ๋ผ์ ๋ฌถ์ด๋๋ ๊ฐ๋ ์ด๋ผ๊ณ ๋ณด์๋ฉด ๋ฉ๋๋ค.
h๋ผ๋ ํจ์๋ x์ ๋ ๊ฐ์ง ํน์ฑ(์ ๋IP, ์ ๋ชฉ)์ ์ ๋ ฅํด์ฃผ๋ฉด, y(๋ถํ๊ธ์ธ๊ฐ, ์ ๋ณด๊ธ์ธ๊ฐ?)๋ฅผ ์ถ๋ ฅํด์ฃผ๋ ํจ์์ ๋๋ค.
์๋์ f๋ผ๋ ํจ์๋ '์ ๋ต'์ด๊ณ , h๋ ์ฐ๋ฆฌ๊ฐ ์ธ์ด ๊ฐ์ค์ด๋ค, ๊ทธ๋ฌ๋๊น ํ๋ฆด ์๋ ์์ต๋๋ค.
def๋ ์ ์๋ฅผ ์๋ฏธํฉ๋๋ค. ์ ๊ฑธ ๊ทธ๋ฅ ์ค ์ธ ๊ฐ ๊ธ๋ ๊ฑธ๋ก ์ฐ๊ธฐ๋ ํ๋๋ฐ, ๊ทธ๋ฌ๋๊น L์ด๋ผ๋ ํจ์๋ฅผ ์ค๋ฅธ์ชฝ์ ์๋ ์์๊ณผ ๊ฐ์ด ์ ์ํ๊ฒ ๋ค๋ ๋ป์ ๋๋ค.
P(h(x)=/f(x))๋ ์์์ ๊ตต์ x๋ฅผ ์ ๋ ฅํ์ ๋(์ฆ, ์ด๋ค ๊ธ์ ๋ฐ์ดํฐ๋ก ๋ฃ์์ ๋), ๊ฐ์ค์ ๋ฐ๋ฅธ ๋ต๊ณผ, ์ ๋ต์ด ๋ค๋ฅธ ํ๋ฅ ์ ์๋ฏธํฉ๋๋ค.
D๋ f๋ S๋ ์๋์ฒจ์๋ค์ด ์ฌ๋ฟ ์๋๋ฐ, D๋ผ๋ ํ๋ฅ ๋ถํฌ ํ์์ ๋ฐ์ดํฐ๋ฅผ ์ถ์ถํด์... ์ด์ฉ๊ณ ์ ์ฉ๊ณ . ๊ทธ๋ฅ ์๋ฉด ์ข๊ธด ํ๋ฐ ๋ณ ์ ๊ฒฝ ์ ์ฐ์ ๋ ๋ฉ๋๋ค.
๊ทผ๋ฐ ์ฐ๋ฆฌ๊ฐ ์ ๋ต์ ๊ตฌํ๋ ค๊ณ h๋ผ๋ ๊ฐ์ค์ ์ธ์ด ๊ฑด๋ฐ, ์ ๋ต์ธ f๋ฅผ ์ด๋ป๊ฒ ์๊ณ h๋ ๊ฐ์์ง ๋ค๋ฅธ์ง ๋น๊ต๋ฅผ ํฉ๋๊น?
๊ทธ๋์ ์์ ์ด๋ ๊ฒ ์์ ๋ฉ๋๋ค. ์ฆ, m๊ฐ์ ๊ธ์ด ์๋๋ฐ, ๊ทธ ๊ธ์ ๋ชจ๋ h๋ผ๋ ๊ฐ์ค์ ์ ๋ ฅํด๋ด ๋๋ค.
์ฌ๊ธฐ์ ๋ถ์๋ ํ๋ฆฐ ๊ฒ์ ๊ฐ์๋ฅผ ์๋ฏธํฉ๋๋ค. (ํ๋ฆฐ ๊ฒ ์)/(์ ์ฒด ๊ธ ์)๊ฐ ๋ญก๋๊น? ์ค๋ต๋ฅ ์ด์ฃ .
์ด๋ ๊ฒ ์ฌ์ฐจ์ ์ฐจํด์, S๋ผ๋ ๋ฐ์ดํฐ๋ฅผ ์ด๋ป๊ฒ ์ ๋ถ์ํด์,ย ์ค๋ต๋ฅ ์ด ์ต์๊ฐ ๋๋ ๊ฐ์ค h๋ฅผ ์ฐพ์ต๋๋ค.ย
argmin์ '์ต์๋ก ๋ง๋ค์ด์ฃผ๋'. ์ฆ ์ค๋ต๋ฅ ์ ์ต์๋ก ๋ง๋ค์ด์ฃผ๋ ๊ฐ์ค h๋ฅผ ์ฐพ์ผ๋ผ ์ด ๋ง์ ๋๋ค.
์ด๊ฑด 'S์ ํฌํจ๋์ด ์๋ ๊ฑฐ๋ฉด yi๋ฅผ, ํฌํจ๋์ด ์์ง ์์ ์๋ก์ด ์๋ฃ๋ฉด '์ ๋ณด๊ธ'์ ์ถ์ถํด๋ผ!'
๊ทผ๋ฐ S์ ํฌํจ๋์ด ์์ผ๋ฉด ์ด๋ฏธ ์ฐ๋ฆฌ๊ฐ ์ ๋ต์ ์๋ ๊ฑฐ๋๊น ์ ๋ต์ด ๋์ค๋ ๊ฒ ๋น์ฐํ๊ณ ...
์ ์ด์ ์ฐ๋ฆฌ๋ S์ ํฌํจ๋์ด ์์ง ์์ ์๋ฃ๋ฅผ ๋ณด๊ณ , ๊ทธ๊ฒ ์ ๋ณด๊ธ์ธ์ง ๋ถํ๊ธ์ธ์ง ์ถ๋ก ํ๊ธฐ ์ํด h๋ผ๋ ๊ฐ์ค์ ์ฐ๋ ๊ฒ๋๋ค.
๊ทผ๋ฐ ๊ทธ๋ฐ ๊ฑธ ์น ๋ค ์ ๋ณด๊ธ๋ก ํ์ ํด๋ฒ๋ฆฌ๋ฉด? ์ผ์ผ์ด ๋ค์ด๊ฐ์ ํ์ธํด๋ณด๋ผ๋ ์๋ฆฌ์ฃ .
...๊ทธ๊ฑด ๋๋ ํ๊ฒ ๋ค.
์ด์์ ๋๋ค.
ํด์ค์ถ!
๋ญ๋ผ๋๊ฑฐ๋ ธ