๋น๋ฐ๋ฒํธ ์กฐํฉ ๊ณ์ฐ๊ธฐ๋?
์ด ๊ณ์ฐ๊ธฐ๋ ๋ฌธ์ ์งํฉ ํฌ๊ธฐ์ ๋น๋ฐ๋ฒํธ ๊ธธ์ด๋ฅผ ๋ฐํ์ผ๋ก ๋ง๋ค ์ ์๋ ๊ณ ์ ํ ๋น๋ฐ๋ฒํธ์ ์ด ๊ฐ์๋ฅผ ๊ณ์ฐํฉ๋๋ค. ๋ํ ๋น๋ฐ๋ฒํธ ๊ฐ๋๋ฅผ ๋ํ๋ด๋ ํ์ค ์งํ์ธ ์ํธ๋กํผ๋ฅผ ๋นํธ ๋จ์๋ก ์๋ ค์ค๋๋ค. ๊ฐ๋ฅํ ์กฐํฉ์ด ๋ง์์๋ก ๋ฌด์ฐจ๋ณ ๋์ (brute force) ๊ณต๊ฒฉ์ผ๋ก ๋น๋ฐ๋ฒํธ๋ฅผ ๋ซ๊ธฐ๊ฐ ๊ทธ๋งํผ ์ด๋ ค์์ง๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
๋จผ์ ๋ฌธ์ ์งํฉ ํฌ๊ธฐ๋ฅผ ์ ๋ ฅํ์ธ์. ์ด๋ ํ์ฉ๋๋ ์๋ก ๋ค๋ฅธ ๋ฌธ์์ ๊ฐ์์ ๋๋ค(์: ์ซ์๋ง ์ฌ์ฉํ๋ฉด 10, ์๋ฌธ์๋ง 26, ์๋ฌธ์์ ์ซ์๋ฅผ ํฉ์น๋ฉด 62, ๊ธฐํธ๊น์ง ํฌํจํ๋ฉด ์ฝ 94). ๊ทธ๋ค์ ๋น๋ฐ๋ฒํธ์ ๋ค์ด๊ฐ๋ ๋ฌธ์ ์์ธ ๋น๋ฐ๋ฒํธ ๊ธธ์ด๋ฅผ ์ ๋ ฅํ๋ฉด, ๊ณ์ฐ๊ธฐ๊ฐ ์ด ์กฐํฉ ์์ ์ํธ๋กํผ๋ฅผ ์๋ ค์ค๋๋ค.
๊ณต์ ์ค๋ช
์กฐํฉ์ ์๋ ๋ฌธ์ ์งํฉ ํฌ๊ธฐ๋ฅผ ๊ธธ์ด๋งํผ ๊ฑฐ๋ญ์ ๊ณฑํ ๊ฐ์ผ๋ก ๊ฐ๋จํ ๊ตฌํฉ๋๋ค: $$C = N^{L}$$ \(L\)๊ฐ์ ๊ฐ ์๋ฆฌ๋ง๋ค \(N\)๊ฐ์ ๋ฌธ์ ์ค ์ด๋ ๊ฒ์ด๋ ๋ ๋ฆฝ์ ์ผ๋ก ์ฌ ์ ์์ผ๋ฏ๋ก ๊ฐ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ณฑํ๋ฉด ๋ฉ๋๋ค. ์ํธ๋กํผ๋ $$E = L \times \log_{2}(N)$$ ์ผ๋ก ๊ตฌํ๋ฉฐ, ํ์ ๊ณต๊ฐ์ ํฌ๊ธฐ๋ฅผ ๋นํธ๋ก ๋ํ๋ ๋๋ค. ๋นํธ๊ฐ 1์ฉ ๋์ด๋ ๋๋ง๋ค ๋ฌด์ฐจ๋ณ ๋์ ์ ํ์ํ ์์ ๋์ ๋ ๋ฐฐ๊ฐ ๋ฉ๋๋ค.
์ค์ ์์
์๋ฌธ์์ ์ซ์๋ฅผ ์ฌ์ฉํ๊ณ (\(N = 62\)), 8์๋ฆฌ ๋น๋ฐ๋ฒํธ(\(L = 8\))๋ฅผ ์ด๋ค๊ณ ๊ฐ์ ํด ๋ด ์๋ค. ์กฐํฉ ์๋ $$62^{8} = 218{,}340{,}105{,}584{,}896$$ ์ฆ 218์กฐ ๊ฐ์ง๊ฐ ๋์ต๋๋ค. ์ํธ๋กํผ๋ $$8 \times \log_{2}(62) \approx 47.63 \text{ bits}$$ ๋ก ์ค๊ฐ ์์ค์ด๋ฉฐ, ๋ณด์ ์ ๋ฌธ๊ฐ๋ค์ ๋ฏผ๊ฐํ ๊ณ์ ์๋ ํํ 60๋นํธ ์ด์์ ๊ถ์ฅํฉ๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
๋ฌธ์ ์งํฉ ํฌ๊ธฐ๋ ์ด๋ป๊ฒ ์ ํ๋์? ๋น๋ฐ๋ฒํธ์ ๋ค์ด๊ฐ ์ ์๋ ๋ชจ๋ ๋ฌธ์์ ๊ฐ์๋ฅผ ์ฌ์ฉํ์ธ์: 10(์ซ์), 26(์๋ฌธ ํ ์ข ๋ฅ), 52(๋์๋ฌธ์ ํผํฉ), 62(๋์๋ฌธ์ ํผํฉ + ์ซ์), ์ฝ 94(์ฌ๊ธฐ์ ์์ฃผ ์ฐ๋ ๊ธฐํธ ์ถ๊ฐ).
์ํธ๋กํผ ๋ช ๋นํธ๋ฉด "๊ฐ๋ ฅํ" ๋น๋ฐ๋ฒํธ์ธ๊ฐ์? ์ผ๋ฐ์ ์ธ ๊ธฐ์ค์ผ๋ก ์ผ์ ๊ณ์ ์ 50~60๋นํธ, ์ค์ํ ๋น๋ฐ ์ ๋ณด๋ 80๋นํธ ์ด์์ ๊ถ์ฅํฉ๋๋ค. ๋น๋ฐ๋ฒํธ ๊ธธ์ด๋ฅผ ๋๋ฆฌ๋ ๊ฒ์ด ๋ฌธ์ ์งํฉ์ ํค์ฐ๋ ๊ฒ๋ณด๋ค ์ํธ๋กํผ๋ฅผ ๋ ๋น ๋ฅด๊ฒ ๋์ฌ์ค๋๋ค.
์ด ๊ณ์ฐ ๊ฒฐ๊ณผ๊ฐ ๋ด ๋น๋ฐ๋ฒํธ์ ์์ ์ ๋ณด์ฅํ๋์? ์๋๋๋ค. ์ด ๊ณ์ฐ์ ์ด๋ก ์ ์ธ ๋ฌด์ฐจ๋ณ ๋์ ์ ํญ๋ ฅ๋ง ์ธก์ ํ ๋ฟ์ ๋๋ค. ์์ธกํ๊ธฐ ์ฌ์ด ๋จ์ด, ๋น๋ฐ๋ฒํธ ์ฌ์ฌ์ฉ, ๋ฐ์ดํฐ ์ ์ถ ๋ฑ์ ์ํธ๋กํผ๊ฐ ๋์ ๋น๋ฐ๋ฒํธ๋ ๋ฌด๋ ฅํํ ์ ์์ต๋๋ค.