[알고리즘] 최대공약수(GCD), 최소공배수(LCM), 유클리드 호제법
최대공약수 GCD(Greatest Common Divisor) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최대공약수는 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값을 의미한다. 예를들어 24와 18 있다고 해보자. 최대공약수는 6이 된다. 최소공배수 LCM(Least Common Multiple) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최소공배수는 두 자연수들의 배수들 중에서 공통된 가장 작은수를 말한다. 참고로 최소공배수는 최대공약수를 통하여 바로구할 수 있다. 최소공배수 = 두 자연수의 곱 / 최대공약수 가 적용된다. 예를 들어 24와 18의 최소공배수는 72 이다. 유클리드 호제법 (Euclidean Algorit..