MCP๋กœ ์—ฐ๊ฒฐ โ†’

๊ณ„์‚ฐ ์ž…๋ ฅ

์ž์ฃผ ์“ฐ๋Š” ๋ฌธ์ž ์ง‘ํ•ฉ ํฌ๊ธฐ: ์ˆซ์ž๋งŒ = 10, ์†Œ๋ฌธ์ž = 26, ์†Œ๋ฌธ์ž+๋Œ€๋ฌธ์ž = 52, ์†Œ๋ฌธ์ž+๋Œ€๋ฌธ์ž+์ˆซ์ž = 62, ๊ธฐํ˜ธ ์ถ”๊ฐ€ โ‰ˆ 94.

๊ณต์‹

๊ด‘๊ณ 

๊ฒฐ๊ณผ

๊ฐ€๋Šฅํ•œ ๋น„๋ฐ€๋ฒˆํ˜ธ ์กฐํ•ฉ ์ˆ˜
218,340,105,584,896
์ „์ฒด ๊ณ ์œ  ๋น„๋ฐ€๋ฒˆํ˜ธ ์ˆ˜
์—”ํŠธ๋กœํ”ผ(๋น„ํŠธ) 47.63 bits
๋ฌธ์ž ์ง‘ํ•ฉ ํฌ๊ธฐ 62
๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด 8

๋น„๋ฐ€๋ฒˆํ˜ธ ์กฐํ•ฉ ๊ณ„์‚ฐ๊ธฐ๋ž€?

์ด ๊ณ„์‚ฐ๊ธฐ๋Š” ๋ฌธ์ž ์ง‘ํ•ฉ ํฌ๊ธฐ์™€ ๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ๊ณ ์œ ํ•œ ๋น„๋ฐ€๋ฒˆํ˜ธ์˜ ์ด ๊ฐœ์ˆ˜๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ ๋น„๋ฐ€๋ฒˆํ˜ธ ๊ฐ•๋„๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ์ค€ ์ง€ํ‘œ์ธ ์—”ํŠธ๋กœํ”ผ๋ฅผ ๋น„ํŠธ ๋‹จ์œ„๋กœ ์•Œ๋ ค์ค๋‹ˆ๋‹ค. ๊ฐ€๋Šฅํ•œ ์กฐํ•ฉ์ด ๋งŽ์„์ˆ˜๋ก ๋ฌด์ฐจ๋ณ„ ๋Œ€์ž…(brute force) ๊ณต๊ฒฉ์œผ๋กœ ๋น„๋ฐ€๋ฒˆํ˜ธ๋ฅผ ๋šซ๊ธฐ๊ฐ€ ๊ทธ๋งŒํผ ์–ด๋ ค์›Œ์ง‘๋‹ˆ๋‹ค.

์‚ฌ์šฉ ๋ฐฉ๋ฒ•

๋จผ์ € ๋ฌธ์ž ์ง‘ํ•ฉ ํฌ๊ธฐ๋ฅผ ์ž…๋ ฅํ•˜์„ธ์š”. ์ด๋Š” ํ—ˆ์šฉ๋˜๋Š” ์„œ๋กœ ๋‹ค๋ฅธ ๋ฌธ์ž์˜ ๊ฐœ์ˆ˜์ž…๋‹ˆ๋‹ค(์˜ˆ: ์ˆซ์ž๋งŒ ์‚ฌ์šฉํ•˜๋ฉด 10, ์†Œ๋ฌธ์ž๋งŒ 26, ์˜๋ฌธ์ž์™€ ์ˆซ์ž๋ฅผ ํ•ฉ์น˜๋ฉด 62, ๊ธฐํ˜ธ๊นŒ์ง€ ํฌํ•จํ•˜๋ฉด ์•ฝ 94). ๊ทธ๋‹ค์Œ ๋น„๋ฐ€๋ฒˆํ˜ธ์— ๋“ค์–ด๊ฐ€๋Š” ๋ฌธ์ž ์ˆ˜์ธ ๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด๋ฅผ ์ž…๋ ฅํ•˜๋ฉด, ๊ณ„์‚ฐ๊ธฐ๊ฐ€ ์ด ์กฐํ•ฉ ์ˆ˜์™€ ์—”ํŠธ๋กœํ”ผ๋ฅผ ์•Œ๋ ค์ค๋‹ˆ๋‹ค.

๊ณต์‹ ์„ค๋ช…

์กฐํ•ฉ์˜ ์ˆ˜๋Š” ๋ฌธ์ž ์ง‘ํ•ฉ ํฌ๊ธฐ๋ฅผ ๊ธธ์ด๋งŒํผ ๊ฑฐ๋“ญ์ œ๊ณฑํ•œ ๊ฐ’์œผ๋กœ ๊ฐ„๋‹จํžˆ ๊ตฌํ•ฉ๋‹ˆ๋‹ค: $$C = N^{L}$$ \(L\)๊ฐœ์˜ ๊ฐ ์ž๋ฆฌ๋งˆ๋‹ค \(N\)๊ฐœ์˜ ๋ฌธ์ž ์ค‘ ์–ด๋А ๊ฒƒ์ด๋“  ๋…๋ฆฝ์ ์œผ๋กœ ์˜ฌ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ๊ฐ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ณฑํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ์—”ํŠธ๋กœํ”ผ๋Š” $$E = L \times \log_{2}(N)$$ ์œผ๋กœ ๊ตฌํ•˜๋ฉฐ, ํƒ์ƒ‰ ๊ณต๊ฐ„์˜ ํฌ๊ธฐ๋ฅผ ๋น„ํŠธ๋กœ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค. ๋น„ํŠธ๊ฐ€ 1์”ฉ ๋Š˜์–ด๋‚  ๋•Œ๋งˆ๋‹ค ๋ฌด์ฐจ๋ณ„ ๋Œ€์ž…์— ํ•„์š”ํ•œ ์ž‘์—…๋Ÿ‰์€ ๋‘ ๋ฐฐ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚จ์— ๋”ฐ๋ผ ๋น„ํŠธ ๋‹จ์œ„ ๋น„๋ฐ€๋ฒˆํ˜ธ ์—”ํŠธ๋กœํ”ผ๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๋ง‰๋Œ€ ๊ทธ๋ž˜ํ”„
๋ฌธ์ž ์ง‘ํ•ฉ์ด ๊ณ ์ •๋œ ๊ฒฝ์šฐ ๋น„ํŠธ ๋‹จ์œ„ ์—”ํŠธ๋กœํ”ผ๋Š” ๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด์— ๋”ฐ๋ผ ์„ ํ˜•์œผ๋กœ ์ฆ๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
ํฌ๊ธฐ N์˜ ๋ฌธ์ž ์ง‘ํ•ฉ์ด L๊ฐœ์˜ ๋น„๋ฐ€๋ฒˆํ˜ธ ์นธ์„ ์ฑ„์šฐ๊ณ , ์ด ์กฐํ•ฉ ์ˆ˜๊ฐ€ N์˜ L์ œ๊ณฑ์œผ๋กœ ํ‘œ์‹œ๋œ ๋‹ค์ด์–ด๊ทธ๋žจ
๋น„๋ฐ€๋ฒˆํ˜ธ์˜ \(L\)๊ฐœ ์œ„์น˜ ๊ฐ๊ฐ์— \(N\)๊ฐœ์˜ ๋ฌธ์ž ์ค‘ ํ•˜๋‚˜๊ฐ€ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ์–ด ์ด \(N^{L}\)๊ฐœ์˜ ์กฐํ•ฉ์ด ๋งŒ๋“ค์–ด์ง‘๋‹ˆ๋‹ค.

์‹ค์ „ ์˜ˆ์ œ

์†Œ๋ฌธ์ž์™€ ์ˆซ์ž๋ฅผ ์‚ฌ์šฉํ•˜๊ณ (\(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๋น„ํŠธ ์ด์ƒ์„ ๊ถŒ์žฅํ•ฉ๋‹ˆ๋‹ค. ๋น„๋ฐ€๋ฒˆํ˜ธ ๊ธธ์ด๋ฅผ ๋Š˜๋ฆฌ๋Š” ๊ฒƒ์ด ๋ฌธ์ž ์ง‘ํ•ฉ์„ ํ‚ค์šฐ๋Š” ๊ฒƒ๋ณด๋‹ค ์—”ํŠธ๋กœํ”ผ๋ฅผ ๋” ๋น ๋ฅด๊ฒŒ ๋†’์—ฌ์ค๋‹ˆ๋‹ค.

์ด ๊ณ„์‚ฐ ๊ฒฐ๊ณผ๊ฐ€ ๋‚ด ๋น„๋ฐ€๋ฒˆํ˜ธ์˜ ์•ˆ์ „์„ ๋ณด์žฅํ•˜๋‚˜์š”? ์•„๋‹™๋‹ˆ๋‹ค. ์ด ๊ณ„์‚ฐ์€ ์ด๋ก ์ ์ธ ๋ฌด์ฐจ๋ณ„ ๋Œ€์ž… ์ €ํ•ญ๋ ฅ๋งŒ ์ธก์ •ํ•  ๋ฟ์ž…๋‹ˆ๋‹ค. ์˜ˆ์ธกํ•˜๊ธฐ ์‰ฌ์šด ๋‹จ์–ด, ๋น„๋ฐ€๋ฒˆํ˜ธ ์žฌ์‚ฌ์šฉ, ๋ฐ์ดํ„ฐ ์œ ์ถœ ๋“ฑ์€ ์—”ํŠธ๋กœํ”ผ๊ฐ€ ๋†’์€ ๋น„๋ฐ€๋ฒˆํ˜ธ๋„ ๋ฌด๋ ฅํ™”ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ตœ์ข… ์—…๋ฐ์ดํŠธ: