Computer Science/Algorithm
[Algorithm] 최소공배수, 최대공약수와 유클리드 알고리즘 (GCD, LCM)
최대공약수(GCD, Greatest Common Divisor) 최대 공약수란 두 자연수의 공통된 약수 중 가장 큰 수 이다. 두 개 이상의 정수의 최대공약수는 해당 정수들의 공통된 약수 중 가장 큰 값이다. 예를 들어, 8과 12의 최대공약수는 4 이다. 최소 공배수(LCM, Least Common Multiple) 최소 공배수란 두 자연수의 공통된 배수 중 가장 작은 수이다. 두 개 이상의 정수의 최소공배수는 주어진 정수들 중에서 모든 정수가 동시에 나누어 떨어지는 가장 작은 정수이다. 예를 들어, 8과 12의 최소공배수는 24이다. 유클리드 알고리즘 유클리드 알고리즘은 두 정수의 최대공약수를 구하는데 사용되는 알고리즘이다. 두 정수 a와 b에 대해서, a를 b로 나눈 나머지를 구하고, 그 나머지를 ..
