Tagged: 최대공약수

알고리즘 – 최대공약수(Great Common Divisor)

분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다.

약분, 최대공약수를 구하라.

최대공약수 구하기 1

최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다.

최대공약수를 구하는 무한대입법이라고 보시면 됩니다.

작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 이용하기 위해서 for 문을 이용했고, maxDiv 변수에 최대공약수 값을 저장하도록 했습니다.

근데, 이렇게하면 아시겠지만 아주 큰수의 경우에 아주 오래 걸립니다. for 문 그냥 막 돌아야하니까요.

최대공약수 구하기 2 – 뺄셈이용.

이 방법을 유클리드(Euclidean) 방법인지는 모르겠습니다. 유클리드 방법은 나눗셈을 이용하는 방법인데, 이것을 뺄셈으로 변환한 것으로 보이거든요.

두 숫자가 있다고 합시다. 두 숫자를 관호에 넣고 왼쪽엔 큰 숫자, 오른쪽엔 작은 숫자를 넣습니다. 그리고 이 둘을 뺀 값을 제수로 넣습니다. 그리고 다시 큰 수를 왼쪽에 넣고 다시 빼고 나온 값을 다시 제수로 넣고 이를 반복하다 보면 나머지가 0일때에 피제수값이 나오는데 이게 바로 최대공약수 입니다.

(3654, 1365)

이 둘을 빼면 2289 값이 나옵니다. 그러면 3654(제수)를 버리고 다음과 같이 적습니다.

(2289, 1365)

다시 둘을 빼면 다음과 같이 나옵니다.

(924, 1365)

왼쪽에는 항상 큰 숫자여야 해서 이 둘을 교환합니다.

(1365, 924)

이것을 한눈에 알아보도록 표기를 하면 다음과 같습니다.

위와 같은 방법이 되고 마지막에 (0, 21) 이니까 두수의 최대공약수는 21 이 되는 것입니다.

이 방법이 유클리드 호제법과 같다는 이유는 뺄셈하는 방법이지만 제수를 항상 나머지로 다시 넣기 때문입니다. 유클리드 호제법은 나눗셈을 이용해서 나온 나머지를 다시 제수로 넣는 방법인데 둘은 같습니다.

(3654, 1365) = (2289, 1365)

이를 공식으로 쓰면,,,

3654 = 1365*1 + 2289

이는 3654/1365 를 나눈 나머지 2289 랑 같습니다.

여기서 규칙은 한가지, 두수를 비교해서 큰수를 왼쪽에 넣어준다 입니다.

최대공약수 구하기 2 – 나눗셈이용.

이를 유클리드 호제법이라고 합니다. 앞에 뺄셈을 나눗셈으로 바꿔서 하는 방법입니다. 이게 뺄셈보다 좋은 점은 반복적인 뺄셈을 없애줍니다. 규측인 뺄셈과 같습니다.

위와같이 while 문을 이용해서 할수도 있지만 재귀호출(Recusive) 로도 다음과 같이 구현할 수 있습니다.

최대공약수(GCD)를 구했는데, 1이 값으로 나온다면 이는 최대공약수가 없다는 것을 의미합니다. 1은 모든수의 공약수이기 때문입니다.