์ผ๋ฐ์ ์ผ๋ก A์ B์ ์ต๋๊ณต์ฝ์๋ฅผ ๊ตฌํ๋ ๊ฐ์ฅ ์ฌ์ด ๋ฐฉ๋ฒ์ A์ B๋ฅผ 2๋ถํฐ A์ B์ค ๋ ์์ ์ ๊น์ง ๋ชจ๋ ์์ฐ์๋ก ๋๋๋ ๊ฒ์ด๋ค. ์ด ๋ฐฉ๋ฒ์ ์๊ฐ ์ปค์ง์๋ก ์๊ฐ์ด ์ค๋๊ฑธ๋ ค ๋นํจ์จ์ ์ด๋ฉฐ, ๋ชจ๋ ์๋ก ๋๋ ์ผ ํ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ O(n)์ด ๋๋ค. ์ด๋ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ ์ฌ์ฉํ๋ค. ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ (Euclidean Algorithm) : ๋ ์ ์์ ์ต๋๊ณต์ฝ์(Greatest Common Divisor)๋ฅผ ๊ตฌํ๋ ์๊ณ ๋ฆฌ์ฆ A > B ์ผ ๋1. A % B = C2. B % C = D3. ์ ๊ณผ์ ์ ๊ณ์ ๋ฐ๋ณต4. X % Y = 0, Y๊ฐ A์ B์ ์ต๋๊ณต์ฝ์ ๊ทธ๋ฆผ์ผ๋ก ํํํด ๋ณด์ ๋ ์ ์ A, B๋ฅผ ์ง์ฌ๊ฐํ์ ๋ ๋ณ์ ๊ธธ์ด๋ผ๊ณ ์๊ฐํ๋ฉด ์ง์ฌ๊ฐํ์ ์ ์ฌ๊ฐํ์ผ๋ก ์์ ํ ์ฑ์ฐ๋ ค๊ณ ํ ๋ ์ ์ฌ๊ฐํ์ ๊ฐ์ฅ ๊ธด ๋ณ์ ๊ธธ..