알고리즘 문제를 풀다보면 최대 공약수와 최소 공배수를 가끔 볼 때가 있는데 이에 대해 정리를 좀 해보려고 한다. 먼저 최대 공약수 자바코드는 다음과 같다. public int GCD(int a, int b) { while(true) { if(a % b == 0) return b; int r = a % b; a = b; b = r; } } 여기서 최대 공약수를 구하기 위해 유클리드 호제법을 사용했는데 위키백과에 따르면 유클리드 호제법은 다음과 같다. 즉 a mod b를 했을 때 나머지를 r이라고 하면 a, b의 최대 공약수는 b와 r의 최대 공약수와 같고 r = 0이면 b가 최대 공약수라는 것이다. 이걸 코드로 표현하면 위와 같은데 여기서 a ≥ b라는 조건때문에 크기를 비교하여 a, b를 설정하는 코드를..
