최소공배수1 [알고리즘] 유클리드 알고리즘(최대공약수, 최소공배수 구하기) 일반적으로 최대공약수(Greatest Common Factor)와 최소공배수(Lowest Common Multiple)를 구할 때 소인수분해를 해서 구한다. 하지만 프로그래밍을 통해서 구할 때는 특정한 알고리즘 없이 직접적으로 구하기 까다롭다. 여기서 유클리드 알고리즘은 최대공약수를 구하는 특별한 알고리즘이다! ※ 유클리드 알고리즘이란? 주어진 두 수 사이에 최대공약수(GCD)를 구하는 알고리즘 유클리드 알고리즘은 "두 수 A, B가 주어졌을 때(단 A > B) A를 B로 나눈 나머지 r에 대해서 GCD(A, B) = GCD(B, r)이고, 여기서 나머지 r이 0이면 B가 두 수의 최대공약수이다!"라는 원리를 이용한 알고리즘이다. 알고리즘을 구현하는 방법은 재귀를 이용하는 방법과 반복문을 이용하는 방법 .. 2021. 7. 3. 이전 1 다음