[문제] https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net [풀이] 1. 최대공약수 (GCD: Greates Common Divisor) 최대공약수를 구할 때 반복문을 사용해 알고리즘을 짰었는데 언뜻 봐도 시간복잡도가 O(n)이나 된다.. 시간복잡도를 줄일 다른 알고리즘을 찾아보니 유클리드 호제법(Euclidean algorithm)이 있었다!! 유클리드 호제법(Euclidean algorithm) 원리 : a, b의 최대공약수 == b와 a%b의 최대공약수 -> GCD(a, b) = GCD(b, a%b) a%b..
