์ด ๋น๋ฐ๋ฒํธ ์์ฑ๊ธฐ๋ ๋ฌด์์ ํ๋์?
์ด ๋๊ตฌ๋ ์ฌ์ฉ์๊ฐ ์ ํํ ๋ฌธ์ ์ข ๋ฅ(์๋ฌธ์, ๋๋ฌธ์, ์ซ์, ๋ฌธ์ฅ๋ถํธ, ๊ดํธ ๋ฐ ๊ธฐํธ)๋ฅผ ์กฐํฉํด ์ต๋ 50์๋ฆฌ์ ๋๋ค ๋น๋ฐ๋ฒํธ๋ฅผ ๋ง๋ค์ด ์ค๋๋ค. ๋น๋ฐ๋ฒํธ๋ ํ์ฌ ๋ธ๋ผ์ฐ์ ์ธ์ ์์์๋ง ์์ฑ๋๋ฉฐ ์ด๋์๋ ์ ์ฅ๋๊ฑฐ๋ ์ ์ก๋์ง ์์ผ๋ฏ๋ก, ๋ชจ๋ ๊ฒฐ๊ณผ๋ ์ง๊ธ ๋ณด๊ณ ์๋ ํ๋ฉด์๋ง ์กด์ฌํฉ๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
ํฌํจํ๊ณ ์ถ์ ๋ฌธ์ ์ข ๋ฅ์ ์ฒดํฌํ๊ณ , ๋ฌธ์๋ฅผ ์ด๋ค ๋ฐฉ์์ผ๋ก ๋ฝ์์ง ์ ํ ๋ค์, ๋น๋ฐ๋ฒํธ ๊ธธ์ด๋ฅผ ์ค์ ํ๊ณ ์์ฑํ๋ฉด ๋ฉ๋๋ค. ๋ค์ฏ ๊ฐ์ง ์ข ๋ฅ๋ฅผ ์์ ๋กญ๊ฒ ์กฐํฉํ ์ ์์ต๋๋ค. ํฌํจํ๋ ์ข ๋ฅ๊ฐ ๋ง์์๋ก ๊ฒฝ์ฐ์ ์๊ฐ ์ปค์ง๊ณ , ๊ทธ๋งํผ ์ถ์ธกํ๊ธฐ ์ด๋ ค์ด ๋น๋ฐ๋ฒํธ๊ฐ ๋ฉ๋๋ค.
๊ท ๋ฑํ๊ฒ ์ ํ ์ต์ ์๋ ๋ ๊ฐ์ง ๋ฐฉ์์ด ์์ต๋๋ค. ์ ํํ ๋ชจ๋ ๋ฌธ์๋ ํ์ฑํํ ๋ชจ๋ ์ข ๋ฅ๋ฅผ ํ๋์ ํ๋ก ํฉ์น ๋ค, ๊ทธ ์์์ ๊ฐ ๋ฌธ์๋ฅผ ๋ฌด์์๋ก ๊ท ๋ฑํ๊ฒ ๋ฝ์ต๋๋ค. ์ ํํ ๊ฐ ์ข ๋ฅ๋ณ๋ก๋ ํ์ฑํํ ์ข ๋ฅ๋ฅผ ์์๋๋ก ๋ฒ๊ฐ์ ์ฌ์ฉํด, ๊ฐ ์ข ๋ฅ๊ฐ ๊ฐ๋ฅํ ํ ๊ณ ๋ฅด๊ฒ ํฌํจ๋๋๋ก ํ ๋ค ๋ง์ง๋ง์ ์์น๋ฅผ ์์ด(์ ํ) ๋ฌด์์ํํฉ๋๋ค. ์ด๋ ๊ฐ ์ข ๋ฅ์์ ๋ฝ๋ ๋ฌธ์ ์๋ \( n_j \in \left\{ \left\lfloor \tfrac{L}{k} \right\rfloor, \left\lceil \tfrac{L}{k} \right\rceil \right\} \) ์ ๋๋ค.
๊ณต์ ์ดํดํ๊ธฐ
๋น๋ฐ๋ฒํธ์ ๋ณด์ ์์ค์ ํํ '๊ฒฝ์ฐ์ ์(search space)'๋ก ์ค๋ช ํฉ๋๋ค. ์ด๋ ์ต์ ์ ๊ฒฝ์ฐ ๊ณต๊ฒฉ์๊ฐ ๋ชจ๋ ์๋ํด ๋ด์ผ ํ๋ ๊ฐ๋ฅํ ๋น๋ฐ๋ฒํธ์ ์ด ๊ฐ์์ ๋๋ค. ์๋ก ๋ค๋ฅธ ๋ฌธ์๊ฐ P๊ฐ์ธ ํ์์ ๊ธธ์ด๊ฐ L์ธ ๋น๋ฐ๋ฒํธ๋ฅผ ๋ง๋ค๋ฉด, ๊ฒฝ์ฐ์ ์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
$$ \text{Search Space} = P^{L} $$๋ฌธ์ ํ๋๋ฅผ ๋ ๋๋ฆฌ๋ฉด(\(L\) ์ฆ๊ฐ) ๊ฒฝ์ฐ์ ์๊ฐ \(P\)๋ฐฐ๊ฐ ๋๊ณ , ๋ฌธ์ ์ข ๋ฅ๋ฅผ ๋ํ๋ฉด \(P\)๊ฐ ์ปค์ง๋ฏ๋ก, ๊ธธ์ด์ ๋ค์์ฑ ๋ชจ๋ ๋ณด์์ ๊ธฐํ๊ธ์์ ์ผ๋ก ๊ฐํํฉ๋๋ค.
์ค์ ์์
์๋ฌธ์(26), ๋๋ฌธ์(26), ์ซ์(10)๋ฅผ ์ผ๊ณ ์ ํํ ๊ฐ ์ข
๋ฅ๋ณ๋ก๋ฅผ ๊ณ ๋ฅธ ๋ค 8์๋ฆฌ๋ฅผ ์์ฒญํ๋ค๊ณ ํด ๋ด
์๋ค. ์ข
๋ฅ๊ฐ \(k=3\)๊ฐ์ด๋ฏ๋ก 0,1,2,0,1,2,0,1 ์์๋ก ๋์๊ฐ๋ฉฐ ์๋ฌธ์ 3๊ฐ, ๋๋ฌธ์ 3๊ฐ, ์ซ์ 2๊ฐ๊ฐ ๋ง๋ค์ด์ง๋๋ค. ํผ์
-์์ด์ธ (Fisher-Yates) ์
ํ์ ๊ฑฐ์น๋ฉด kT4mQ7pR ๊ฐ์ ๊ฒฐ๊ณผ๋ฅผ ์ป์ ์ ์์ต๋๋ค. ํ ํฌ๊ธฐ๋ \( P = 26+26+10 = 62 \)์ด๋ฏ๋ก, ๊ฒฝ์ฐ์ ์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
์ ๋น๋ฐ๋ฒํธ๊ฐ ์ ์ฅ๋๋์? ์๋์. ๋ชจ๋ ๋น๋ฐ๋ฒํธ๋ ํ๋ฉด ํ์์ฉ์ผ๋ก๋ง ์์ฑ๋๋ฉฐ ์ ์ฅ๋๊ฑฐ๋ ๊ธฐ๋ก๋์ง ์์ต๋๋ค.
๋น๋ฐ๋ฒํธ๋ ๋ช ์๋ฆฌ๊ฐ ์ ๋นํ๊ฐ์? ์ฌ๋ฌ ๋ฌธ์ ์ข ๋ฅ๋ฅผ ์์ด ์ต์ 12~16์๋ฆฌ๋ฅผ ๋ชฉํ๋ก ํ์ธ์. ๋ฌธ์ ํ๋๋ฅผ ๋ํ ๋๋ง๋ค ๊ฒฝ์ฐ์ ์๊ฐ ๊ณฑ์ ๋ก ๋์ด๋๋ฏ๋ก ๊ธธ์๋ก ํญ์ ๋ ์์ ํฉ๋๋ค.
'์ ํํ ๊ฐ ์ข ๋ฅ๋ณ๋ก'๋ ๋ฌด์์ ๋ณด์ฅํ๋์? ์ ํํ ์ข ๋ฅ ์ ๋ฐ์ ๋ฌธ์๋ฅผ ์ต๋ํ ๊ณ ๋ฅด๊ฒ ๋ฐฐ๋ถํด ์ค๋๋ค. ์๋ฌธ์, ์ซ์, ๊ธฐํธ๋ฅผ ๋ฐ๋์ ์์ด์ผ ํ๋ ์ฌ์ดํธ์ ๋น๋ฐ๋ฒํธ ๊ท์น์ ์ถฉ์กฑํ๋ ๋ฐ ๋์์ด ๋ฉ๋๋ค.