최대 공약수는 a , b 둘 다 나누어떨어질수 있는 수 중에서 가장 큰 값이므로 1 ~ min(a,b)
를 전부 for 문 돌며 확인 하는 방법
여기서 시간을 조금더 줄이려면 for 문을 1부터 말고 뒤에서 부터 돌리게 된다면 가장 처음 발견 한
수가 최대 공약수!
하지만 서로서인 경우는 어차피 끝까지 가야하므로 똑같은 시간 복잡도
서로소 : 1 이외의 공약수가 없음을 이르는 말!
약수 : 어떤수를 나머지 없이 나눌수 있는 자연수
유클리드 호제법
2개의 자연수의 최대공약수를 구하는 알고리즘
a 를 b 로 나눈 나머지를 r 이라하면 (a > b), a와 b의 최대공약수는 b 와 r의 최대공약수와 같다는 성질 !
최대공약수 ( 24, 18 의 최대 공약수 6)
0이 아닌 두 정수나 다항식의 공통되는 약수 중 가장 큰 수 G
최대 공약수 G는 두 정수 24, 18 에 만족하는 x, y 존재 ( x, y는 6으로 나눈 값)
최소 공배수 643
O(log(min(a,b)) (나머지 연산자의 특성을 이용하여 log 시간 복잡도)
a mod b 라는 것은 [0,b-1] 이라는 범위를 가지게 되며, 평균적으로 해당 범위의 중간값을 가지게 됨
WonYong-Jang
commented
5 years ago
일반적인 최대공약수 구하기 ( Brute Force )
유클리드 호제법
최대공약수 ( 24, 18 의 최대 공약수 6)
최소공배수