개발/알고리즘
[알고리즘] GCD & LCM
최대 공약수 (Greatest Common Divisor)와 최소 공배수(least common multiple)를 구한다. 알고리즘으로는 유클리드 호재법을 사용하여 해결합니다. 큰 수를 작은수로 나눈 나머지를 0이 될때 까지 계속 나눕니다. 글로 적으니 복잡하네요. 아래의 코드를 보면 GCD 85를 51로 나눕니다. -> 나머지 34 51을 34으로 나눕니다. -> 나머지 17 34를 17로 나눕니다. -> 나머지 0 => 최대 공약수 : 17 LCM 두 수의 곱을 최대 공약수로 나눕니다. => 85 * 51 / 17 = 255 class Solution { @Test public void getGCD_LCD() { // given int x = 85; int y = 51; // when long gc..
