최대공약수/ 최소공배수_ 백준 2609번/1934번

지금은 코드플러스에서 기초 알고리즘 강의를 구매해서, 관련 문제를 푸는 중인데 백준 2609번이랑 1934번이 비슷한 문제인거 같아서 한번에 정리해보려고 한다. 먼저, 최대공약수의 경우에는 유클리드 호제법을 이용하는 방법을 사용하는 것이 좋다. 여기서 유클리드 호제법이란, a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a,b) = GCD(b,r)인 것을 활용하여, r의 값이 0이 되면 그때의 b의 값이 최대 공약수라는 것을 활용한다. 최소공배수의 경우에는 위에서 구한 최대공약수를 활용하여 구할 수 있다. 최소공배수는 두수의 공통된 배수 중 가장 작은 정수이기 때문에, 두수 a, b의 최대공약수가 g라고했을 때 최소공배수 = g * (a/g) * (b/g)가 된다. 2609번 #include #inc..