프로그래머스 알고리즘 유클리드 호제법(최대공약수, 최소공배수)

유클리드 호제법

 

- 유클리드 호제법(Euclidean algorithm)은 두 개의 정수의 최대공약수(GCD, Greatest Common Divisor)를 찾는 알고리즘, 이 알고리즘은 오래 전에 유클리드(Euclid)에 의해 개발되었으며, 지금까지도 매우 효율적으로 사용됩니다.

 

- 유클리드 호제법은 나누고 남은 나머지를 계속해서 구하다가 나머지가 0이 될 때까지 반복합니다. 그러면 0이 아닌 나머지를 얻게 되고, 그 때의 나머지가 두 정수의 최대공약수가 됩니다.

 

 

 

 

-> 여기서 m = 27, n = 5이라고 가정해보자. 나머지(r)가 0이 될때까지 반복한다.

 

r = 27 % 5이므로 나머지인 2가 r이된다.

 

나눈수인 5가 m이 되고 나머지인 2가 n이 된다.

 

m = 5, n = 2;

 

r이 0이되면 while문이 종료되기 때문에 다시 위로 올라가서

 

r = 5 % 2이므로 나머지인 1이 r이된다.

 

여기서 다시 m = 2, n = 1;

 

r = 2 % 1, r은 0이되어서 반복문이 종료되고 최대공약수를 담아주는 변수인 num1에 n값이 담긴다. 즉 27과 5의 최대공약수는 1이된다.

 

최소공배수를 구하는 방식은 아주 간단한데, plus변수에는 m*n(27 * 5)의 값이 담겨있다. 두 수를 곱한값에 최대공약수를 나누면 그 값이 최소공배수가 된다.

 

27 * 5 / 1 == 최소공배수