[KO]๐งฟ ์ฃผ์ญ๊ณผ ์ด์ง๋ฒ – ์ 3ํธ: ๊ด์ ๋ณํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
๐งฟ ์ฃผ์ญ๊ณผ ์ด์ง๋ฒ – ์ 3ํธ: ๊ด์ ๋ณํ์ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
๐ชท ์๋ฌธ: ๊ณ ๋์ ๋ณํ, ํ๋์ ์ํ
์ด์ ๊ธ์์๋ ์ฃผ์ญ์ 64๊ด๊ฐ ์ด์ง์ ๊ตฌ์กฐ๋ฅผ ๋ฐ๋ฅด๋ฉฐ, ๊ฐ ๊ด๊ฐ ๋นํธ ๋จ์์ ๋ณํ๋ก ์ ์ด๋ ์ ์๋ค๋ ์ฌ์ค์ ํ์ธํ์ต๋๋ค.
์ด๋ ์ฃผ์ญ์ด ๋จ์ง ์์ง์ฒด๊ณ๊ฐ ์๋, ๋ช
ํํ ๋
ผ๋ฆฌ์ ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๊ณ ์๋ค๋ ๊ฒ์ ๋ณด์ฌ์ฃผ๋ ํต์ฌ์
๋๋ค.
์ด๋ฒ ํธ์์๋, ๊ฐ ๊ด๋ค์ด ์ด๋ป๊ฒ ์ํ์ ์ผ๋ก ๋ณํํ๋ฉฐ, ๊ทธ ๋ณํ๊ฐ ํ๋์ ์๊ณ ๋ฆฌ์ฆ์ฒ๋ผ ๊ตฌ์ฑ๋ ์ ์๋๊ฐ์ ๋ํด ์ดํด๋ณด๊ฒ ์ต๋๋ค.
์ด ๊ตฌ์กฐ๋ ๋จ์ํ ์ ์ ์น๋ ๋๊ตฌ๊ฐ ์๋๋ผ, ์ ๋ณด ํ๋ฆ์ ํด์ํ๋ ์ฒ ํ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ฃผ์ญ์ ๋ฐ๋ผ๋ณด๋ ์๋ก์ด ๊ด์ ์ ์ด์ด์ค๋๋ค.
๐ ๊ด์ ๋ณํ๋ ๋ฌด์์ธ๊ฐ?
์ฃผ์ญ์์๋ ๊ฐ ๊ด๊ฐ **๋ณํ(่ฎ)**๋ฅผ ์ ์ ๋ก ํฉ๋๋ค.
์ด ๋ณํ๋ ‘ํจ(็ป)’๋ผ ๋ถ๋ฆฌ๋ ๊ฐ๊ฐ์ ์ ํ๋๊ฐ ์์์ ์์ผ๋ก, ํน์ ์์์ ์์ผ๋ก ๋ฐ๋๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค.
์๋ฅผ ๋ค์ด:
์ด ๋ณํ๋ ๋จ ํ ์ค๋ง ๋ฐ๊พธ๋ 1๋นํธ ๋ณํ๋ก ์ดํดํ ์ ์์ผ๋ฉฐ,
์ด๋ฅผ ํตํด 64๊ด๋ ๋ง์น **ํ์ดํผํ๋ธ(hypercube)**์ฒ๋ผ ๋ชจ๋ ๊ด๊ฐ ์๋ก ์ฐ๊ฒฐ๋ ๋คํธ์ํฌ ๊ตฌ์กฐ๋ฅผ ํ์ฑํฉ๋๋ค.
๐ ํ์ดํผํ๋ธ์ 64๊ด์ ๊ตฌ์กฐ
6๋นํธ๋ก ์ด๋ฃจ์ด์ง 64๊ฐ์ ๋
ธ๋๋, ์ํ์ ์ผ๋ก ๋ณด๋ฉด 6์ฐจ์ ํ์ดํผํ๋ธ์ ์ ์ ์
๋๋ค.
๊ฐ ์ ์ (๊ด)์ ์ด 6๊ฐ์ ์ธ์ ๋
ธ๋๋ฅผ ๊ฐ์ง๋ฉฐ, ์ด๋ ํ๋์ ์ (๋นํธ)์ด ๋ณํ ๋ ๋๋ฌํ๋ ๊ด์
๋๋ค.
์ด ๊ตฌ์กฐ๋ ๋ค์๊ณผ ๊ฐ์ ํน์ฑ์ ๊ฐ์ง๋๋ค:
-
๊ฐ ๊ด๋ 6๊ฐ์ ๋ณํ ๊ฐ๋ฅ์ฑ์ ๊ฐ์ง
-
๊ทธ ๋ณํ๋ ๋ชจ๋ ๋ ผ๋ฆฌ์ ์ผ๋ก ์์ธก ๊ฐ๋ฅ
-
๊ด์ ๋ณํ๋ ๋๋ค์ด ์๋, ์ํ์ ์ ์ด(transition)
์ด๋ฌํ ๊ตฌ์กฐ๋ฅผ ํตํด ์ฐ๋ฆฌ๋ ์ฃผ์ญ์ ๋ณํ๊ฐ ๋ณต์กํ์ง๋ง, ์์ ํ ์ถ์ ๊ฐ๋ฅํ ์ฒด๊ณ์์ ์ ์ ์์ต๋๋ค.
๐ ๊ด ๋ณํ์ ์ํ์ฑ๊ณผ ์๊ณ ๋ฆฌ์ฆํ
๊ด์ ๋ณํ๋ ํน์ ๊ท์น์ ๋ฐ๋ผ ์ํ์ ์ผ๋ก ๋ฐฐ์ด๋ ์ ์์ต๋๋ค.
๋ํ์ ์ธ ์๋ก๋ ๊ทธ๋์ด ์ฝ๋(Gray Code) ๋ฐฉ์์ด ์์ต๋๋ค.
๐น Gray Code๋?
Gray Code๋ ์ด์ํ ์ซ์๋ค์ด ๋จ 1๋นํธ๋ง ๋ค๋ฅด๋๋ก ๋ฐฐ์ด๋ ์ด์ง์์
๋๋ค.
์ฆ, 000000 → 000001 → 000011 → … → 111111
์ ์์๋ก ๋ฐฐ์ด๋๋ฉฐ,
๊ฐ ๋จ๊ณ๋ง๋ค ํ๋์ ๋นํธ๋ง ๋ณํํฉ๋๋ค.
์ด๋ ์ฃผ์ญ์ ๊ด๊ฐ ํ ์ค๋ง ๋ฐ๋์ด ๋ค์ ๊ด๋ก ๋์ด๊ฐ๋ค๋ ์ ์์ ๋๋ผ์ธ ์ ๋๋ก ์ ์ฌํฉ๋๋ค.
๐ธ Gray Code๋ก 64๊ด ๋ฐฐ์ดํ๊ธฐ
์ด ๋ฐฉ์์ผ๋ก ๊ด๋ฅผ ๋ฐฐ์ดํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์ด์ ์ด ์์ต๋๋ค:
-
๋ณํ์ ํ๋ฆ์ด ์์ฐ์ค๋ฝ๊ณ ์์ฐจ์ ์
-
์ ํ ๊ณผ์ ์ ๋ช ํํ ์ถ์ ํ ์ ์์
-
์ปดํจํฐ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ฝ๊ฒ ๊ตฌํ ๊ฐ๋ฅ
์ด๋ ๊ฒฐ๊ตญ ์ฃผ์ญ์ ๋ณํ ์๋ฆฌ๋ฅผ ํ๋ ์ ๋ณด ์์คํ ์ ํ๋ฆ๊ณผ ์ ๋ชฉํ ์ ์๋ ๊ธฐ๋ฐ์ด ๋ฉ๋๋ค.
๐ฉบ ํ์ํ์์์ ์ ์ฉ ๊ฐ๋ฅ์ฑ
์ด๋ฌํ ๊ด์ ์ํ์ฑ๊ณผ ์ ์ด ๊ตฌ์กฐ๋ ํ์ํ ์ง๋จ์ ๋ณ์ฆ ์์คํ ๊ณผ ๋งค์ฐ ํก์ฌํฉ๋๋ค.
์ง๋จ ์, ์/์์ด๋ ํ/๋ฆฌ ๋ฑ์ ์ํ ๋ณํ๋ ๋จ์ํ ๊ณ ์ ๋ ์ํ๊ฐ ์๋ ํ๋ฆ์ ์ผ๋ถ๋ก ํด์๋ฉ๋๋ค.
๊ด ๋ณํ๋ ์ด๋ฌํ ํ๋ฆ์ ๊ตฌ์กฐํ๋ ํํ๋ก ๋ณด์ฌ์ฃผ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ ๋ณผ ์ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด, ํ ์ฆ์์ด 'ํ์ด → ํํ'
์ผ๋ก ์ ์ด๋๋ค๋ฉด, ์ด๋ ๋นํธ ํ ๊ฐ๊ฐ ๋ฐ์ ๋๋ ๊ตฌ์กฐ์ ๊ฐ์ต๋๋ค.
์ฃผ์ญ์ ๋จ์ง ์์ง์ ์ธ์ด๊ฐ ์๋, ๋ณํ์ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค.
ํ์ํ๋ ์ด๋ฌํ ๋ณํ๋ฅผ ์ถ์ ํ๊ณ ๋ถ์ํ๋ ์์คํ ์ ์ฌ๊ณ ์์ ์ ์์ต๋๋ค.
๐ ๋ง๋ฌด๋ฆฌ: ๊ณ ๋์์ ๋์งํธ๋ก
์ด๋ฒ 3ํธ์ ๊ฑธ์น ์ฐ์ฌ๋ฅผ ํตํด ์ฐ๋ฆฌ๋ ๋ค์์ ์ฌ์ค์ ์ ๋ฆฌํ ์ ์์ต๋๋ค:
-
์ฃผ์ญ์ ๊ด๋ ์ด์ง์ ๊ตฌ์กฐ์ ์ ํํ ์ผ์นํ๋ค.
-
๊ด์ ๋ฐฐ์ด๊ณผ ์ ์ด๋ ๋ ผ๋ฆฌ์ , ์ํ์ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ๊ตฌ์ฑ๋ ์ ์๋ค.
-
์ด ๊ตฌ์กฐ๋ ๋จ์ํ ์ ์ ์ฒด๊ณ๋ฅผ ๋์ด, ํ๋์ ์ฌ๊ณ ์ฒด๊ณ์๋ ์ฐ๊ฒฐ๋๋ค.
-
ํ์ํ์ ์ง๋จ, ํนํ ๋ณ์ฆ์ ์ด๋ฌํ ๊ตฌ์กฐ์ ๋ณํ์ ๊น์ด ์ฐ๊ฒฐ๋์ด ์๋ค.
๐ ์ฃผ์ญ์ ํ๋์ ์ ๊ทผ, ๊ทธ๋ฆฌ๊ณ ๋ค์
์ด๋ฒ ์ฐ์ฌ๋ ์ฃผ์ญ์ด ๊ฐ์ง ๊ณ ๋์ ์งํ์ ํ๋์ ๋
ผ๋ฆฌ์ฑ์ ์ ์ ์ ํ์ํ๋ ค๋ ์๋์์ต๋๋ค.
์ด ๋
ผ์๋ฅผ ํ์ฅํ์ฌ, ๊ด์ ์กฐํฉ๊ณผ ์ง๋ณ ์ ํ์ ๋์, ๋๋ ๋์งํธ ํฌ์ค ์์คํ
์์์ ํ์ฉ ๊ฐ๋ฅ์ฑ์ ์๊ฐํด ๋ณผ ์๋ ์์ ๊ฒ ๊ฐ์ต๋๋ค.
์ฆ๋ช
์ค์ฌ์ ํ๋ ๊ณผํ๊ณผ, ์ฌ์ ์ค์ฌ์ ๊ณ ๋ ์ฒ ํ์ด ๋ง์ด ๋ค๋ฅด๋ค๊ณ ๋๋ผ์๋์?
๊ทธ๋ฌ๋ ๊ทธ ์ฌ์ด์ ๋์ธ ์ด์ฑ๊ณผ ์์ง, ๊ตฌ์กฐ์ ํด์์ ์์ญ์์ ์ฐ๋ฆฌ๋ ๋ ์ธ๊ณ๋ฅผ ์๋ ๊ณตํต์ ์ธ์ด๋ฅผ ์ฐพ์ ์ ์์ต๋๋ค.
๋๊ธ
๋๊ธ ์ฐ๊ธฐ