최대공약수 (GCD, Greatest Common Divisor)
예를 들어서 10과 14가 있을 때 10의 약수 = 1,2,5,10 Brute force (무차별 대입) 로 구하는 방법Brute force 방식은 두 수 중 작은 수를 선택한 다음 1부터 작은 자연수까지의 모든 수로 두 수를 나누면서 동시에 나누어 떨어지는 가장 큰 수를 구하는 방법입니다.
시간복잡도는 O(N) 입니다. 유클리드 호제법을 사용해서 구하는 방법유클리드 호제법은 x, y 의 최대공약수는 y, r 의 최대공약수와 같다는 원리를 이용하는 것입니다. 즉, 계속해서 x 값에는 y 값을 대입하고 y 값에는 r 값을 대입하다보면 언젠가는 r 이 0 이 되는데 이때에 y 값에 있는 값이 최대공약수 입니다. 위처럼 10과 15가 있을 때 계속적으로 대입하고 나누다보면 y 가 5일 때 r 이 0이 되기때문에 최대공약수는 5가 됩니다. 수식으로 나타냈을 때에는 다음과 같습니다.
재귀 함수
반복문 사용
최소공배수 (LCM)
예를 들어서 6과 9가 있을 때 6의 배수 = 6, 12, 18, 24, 30, 36 ... 공식 사용하기최소공배수는 두 자연수의 곱 / 최대 공약수 라는 공식으로 구할 수 있습니다.
백준 문제2609번 최대공약수와 최소공배수 🙇🏻♀️ 레퍼런스최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽 |