알고리즘 – 최대공약수(Great Common Divisor)
분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다.
약분, 최대공약수를 구하라.
최대공약수 구하기 1
최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다.
최대공약수를 구하는 무한대입법이라고 보시면 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
def GCDbyDivide(num1, num2): ''' 최대공약수를 구하는 알고리즘. 두수를 나눗셈으로해서 가장큰 약수를 구하는 방법. ''' if num1 < 0: raise RuntimeError('num1 must be above 0') if num2 < 0: raise RuntimeError('num2 must be above 0') miniNum = min(num1, num2) maxDiv = 1 for i in range(1,miniNum+1): if num1%i == 0 and num2%i == 0: maxDiv = i return maxDiv |
작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 이용하기 위해서 for 문을 이용했고, maxDiv 변수에 최대공약수 값을 저장하도록 했습니다.
근데, 이렇게하면 아시겠지만 아주 큰수의 경우에 아주 오래 걸립니다. for 문 그냥 막 돌아야하니까요.
최대공약수 구하기 2 – 뺄셈이용.
이 방법을 유클리드(Euclidean) 방법인지는 모르겠습니다. 유클리드 방법은 나눗셈을 이용하는 방법인데, 이것을 뺄셈으로 변환한 것으로 보이거든요.
두 숫자가 있다고 합시다. 두 숫자를 관호에 넣고 왼쪽엔 큰 숫자, 오른쪽엔 작은 숫자를 넣습니다. 그리고 이 둘을 뺀 값을 제수로 넣습니다. 그리고 다시 큰 수를 왼쪽에 넣고 다시 빼고 나온 값을 다시 제수로 넣고 이를 반복하다 보면 나머지가 0일때에 피제수값이 나오는데 이게 바로 최대공약수 입니다.
(3654, 1365)
이 둘을 빼면 2289 값이 나옵니다. 그러면 3654(제수)를 버리고 다음과 같이 적습니다.
(2289, 1365)
다시 둘을 빼면 다음과 같이 나옵니다.
(924, 1365)
왼쪽에는 항상 큰 숫자여야 해서 이 둘을 교환합니다.
(1365, 924)
이것을 한눈에 알아보도록 표기를 하면 다음과 같습니다.
|
1 2 3 4 5 6 7 8 9 10 11 |
(3654, 1365) = (2289, 1365) = (924, 1365) -> 위치교환 = (1365, 924) = (441, 924) -> 위치교환 = (924, 441*2) = (42, 441) -> 위치교환 = (441, 42*10) = (21, 42) -> 위치교환 = (42, 21) = (21, 21) = (0, 21) |
위와 같은 방법이 되고 마지막에 (0, 21) 이니까 두수의 최대공약수는 21 이 되는 것입니다.
이 방법이 유클리드 호제법과 같다는 이유는 뺄셈하는 방법이지만 제수를 항상 나머지로 다시 넣기 때문입니다. 유클리드 호제법은 나눗셈을 이용해서 나온 나머지를 다시 제수로 넣는 방법인데 둘은 같습니다.
(3654, 1365) = (2289, 1365)
이를 공식으로 쓰면,,,
3654 = 1365*1 + 2289
이는 3654/1365 를 나눈 나머지 2289 랑 같습니다.
여기서 규칙은 한가지, 두수를 비교해서 큰수를 왼쪽에 넣어준다 입니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
def GCDbyEuclidean1(num1, num2): ''' 만약 num1 > num2 이면 (3654, 1365) = (2289, 1365) = (924, 1365) -> 위치교환 = (1365, 924) = (441, 924) -> 위치교환 = (924, 441*2) = (42, 441) -> 위치교환 = (441, 42*10) = (21, 42) -> 위치교환 = (42, 21) = (21, 21) = (0, 21) 3654 = 174*21 1365 = 65*21 (3654 - 1365) = (174 - 65)*21 ''' if num1 < 0: raise RuntimeError('num1 must be above 0') if num2 < 0: raise RuntimeError('num2 must be above 0') while num1 !=0: if num1 < num2: num1, num2 = num2, num1 num1 = num1 - num2 return num2 |
최대공약수 구하기 2 – 나눗셈이용.
이를 유클리드 호제법이라고 합니다. 앞에 뺄셈을 나눗셈으로 바꿔서 하는 방법입니다. 이게 뺄셈보다 좋은 점은 반복적인 뺄셈을 없애줍니다. 규측인 뺄셈과 같습니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def GCDbyEuclidean2(num1, num2): if num1 < 0: raise RuntimeError('num1 must be above 0') if num2 < 0: raise RuntimeError('num2 must be above 0') while num2 != 0: if num1 < num2: num1, num2 = num2, num1 t = num1%num2 num1, num2 = num2, t return num1 |
위와같이 while 문을 이용해서 할수도 있지만 재귀호출(Recusive) 로도 다음과 같이 구현할 수 있습니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def GCDbyEuclidean3(num1, num2): if num1 < 0: raise RuntimeError('num1 must be above 0') if num2 < 0: raise RuntimeError('num2 must be above 0') if num1 < num2: num1, num2 = num2, num1 if num2 == 0: return num1 if num1%num2 == 0: return num2 else: return GCDbyEuclidean3(num2, num1%num2) |
최대공약수(GCD)를 구했는데, 1이 값으로 나온다면 이는 최대공약수가 없다는 것을 의미합니다. 1은 모든수의 공약수이기 때문입니다.