๋ฐฑ์ค26091 ์ต๋๊ณต์ฝ์(GCD), ์ต์๊ณต๋ฐฐ์(LCM) ๊ตฌํ๊ธฐ ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ ์๊ณ ๋ฆฌ์ฆ :: ์ฝ๋์๋ชฝ ์ต๋๊ณต์ฝ์ GCD(Greatest Common Divisor) ์ต๋๊ณต์ฝ์๋ ๋ ์์ฐ์์ ๊ณตํต๋ ์ฝ์ ์ค ๊ฐ์ฅ ํฐ ์๋ฅผ ์๋ฏธํ๋ค. ex) 72 ์ 30์ ์ต๋๊ณต์ฝ์๋ 6์ด๋ค. ์ต์๊ณต๋ฐฐ์ LCM(Least Common Multiple) ์ต์๊ณต๋ฐฐ์๋ ๋ ์์ฐ์์ ๊ณตํต๋ ๋ฐฐ์ ์ค ๊ฐ์ฅ ์์ ์๋ฅผ ์๋ฏธํ๋ค. ์ต์๊ณต๋ฐฐ์ = ๋ ์์ฐ์์ ๊ณฑ / ์ต๋๊ณต์ฝ์ ex) 72 ์ 30์ ์ต์๊ณต๋ฐฐ์๋ 360์ด๋ค. ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ(Euclidean Algorithm) 2๊ฐ์ ์์ฐ์๋ฅผ ๋ฐ์ ์ต๋๊ณต์ฝ์๋ฅผ ๋ฐ๊ธฐ ์ํด 2๋ถํฐ ๋ ์์ฐ์ ์ค ์์ ์์ฐ์๊น์ง ๋ชจ๋ ๋๋์ด๋ณด๋ฉด์ ๊ฐ์ฅ ํฐ ๊ณต์ฝ์๋ฅผ ๊ตฌํ ์ ์๋ค. ์์ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ๋ฉด ์๊ฐ๋ณต์ก๋๋ O(N)์ด ๋๋ค. ๋์ ๋ฐฉ๋ฒ์ ์๋์ง๋ง ํจ์จ์ ๋์ด๊ธฐ ์ํด ์ ํด๋ฆฌ๋ ํธ์ ๋ฒ์ด๋ ์๊ณ ๋ฆฌ์ฆ.. 2019. 12. 22. ์ด์ 1 ๋ค์