c언어 유클리드호제법 최대공약수와 최소공배수 알고리즘

오래전에 정리한 정보처리기사 실기 기출문제에 출제되었던, 유클리드호제법 최대공약수와 최소공배수 알고리즘에 대해서 설명드릴려고 합니다.


개인적으로 독학을 통해서 배운거라, 정확도가 떨어질수도 있겠지만, 어차피 알고리즘이라는게 이해를 위해서 시작하는것이기도 합니다.


중간과정도 중요하지만 결과도 중요하기 때문에 공부하시는 분들 난이도에 맞춰서 최대한 쉽게 설명드리겠습니다.


[최대공약수]


최대공약수는 두개 이상의 자연수의 공통된 약수를 뜻합니다. 이 공약수 중에서 가장 큰 공약수를 우리는 최대공약수라고 합니다.


설명 드리면 이렇습니다.


최대공약수를 알게되면 공약수를 손쉽게 얻어낼수 있습니다. 바로 최대공약수의 약수가 바로 공약수이기 때문입니다. 공약수를 구할 때 최대공약수를 구한 다음에 최대공약수의 약수를 구하는 방법입니다.


예를 들어 12와 18의 최대공약수를 알아보겠습니다.


12의 약수: 1, 2, 3, 4, 6, 12

18의 약수: 1, 2, 3, 6, 9, 18


두 수의 공약수는 1, 2, 3, 6이고 이 중 가장 큰 공약수, 최대공약수가 6 입니다. 여기서 6의 약수가 바로 1, 2, 3, 6이며, 이 네 숫자는 12와 18의 공약수와 같습니다.


어떤 두 수의 공약수는 두 수의 최대공약수의 약수와 같다는 걸 알 수 있습니다.


[최소공배수]


두 개 이상의 자연수의 공통인 배수를 공배수라고 하며, 공배수 중 가장 작은 수를 최소공배수라고 합니다. 모든 수의 공배수는 무수히 많으므로 가장 큰 공배수를 찾는 것은 의미가 없기 때문에 최대공배수란 말은 쓰지는 않습니다.


손쉽게 예를들어 설명드리겠습니다.


어떤 형제가 테니스를 하러 테니스장에 가는데 형은 2일에 한 번씩 가고, 동생은 3일에 한 번씩 갑니다. 오늘 같이 운동을 한 뒤, 다음에 함께 운동을 하러 가는 날은 6일째, 12일째, ...되는 날입니다.



그러므로 처음 같이 운동을 하고 나서 다시 운동을 같이 하는 최초의 날은 6일째 되는 날입니다. 이를 수로 나타내면 2의 배수는 2, 4, 6, 8, 10, 12, ...이고, 3의 배수는 3, 6, 9, 12, ...이므로, 2와 3의 공배수는 6, 12, ...입니다.


이들 공배수 중 가장 작은 공배수인 6이 최소공배수가 됩니다. 그리고 2개 이상의 자연수의 공배수는 그 수들의 최소공배수의 배수입니다. 위에서 2와 3의 공배수 6, 12, 18, ...은 최소공배수 6의 배수가 됩니다.


그럼 최대공약수와 최소공배수를 유클리드 호제법을 이용해서 알고리즘 순서도를 한번 살펴보겠습니다. 정보처리기사 기출문제에 출제되었던 문제입니다.


[순서도]


순서도를 살펴보기전에 알아야될 공식이 있습니다. 



바로 유클리트호제법의 공식입니다. 최대공약수를 구하는 알고리즘을 작성할때에 반드시 필요합니다.


- B가 A로 나눠서 떨어지면 두수의 최대 공약수는 B입니다.

- A를 B로 나눴을때 나머지가 R이면 두수의 최대공약수는 R과 B의 최대공약수와 같습니다.


이 공식대로 순서도를 살펴보면 쉽게 알고리즘을 유추할수 있습니다. 첫번째 분기문에서는 어떤 입력된 값중에서 큰수 와 작은수를 구분하기위한 분기점 부분입니다.



예를들어서 A를 24입력, B를 16 입력하였다면, HIGH 와 LOW에 저장되는 데이터가 달라지게 됩니다. 두번째 분기점은 실질적인 최대,최소 공배수를 구별하는 분기점 입니다. 


MOD 함수를 이용해서(MOD는 나머지를 구하는 방식입니다.) 24/16를 했을경우 나머지 8 을 R에 저장하게 되죠. R이 0이 아니기 때문에 다시 분기점에서 돌아옵니다.


그럼 16/8 을 나누면 나머지 0이 됩니다.(이부분은 위에 제시된 공식에 따라 가게 됩니다.) 나머지가 0이기 때문에 다시 분기점에서 0 > 0 이라는 의미가 나타나서 NO 방향으로 가게 됩니다.


L=(A*B)/HIGH 부분은 최소공배수를 구하는 공식입니다. 그럼 순서도를 작성한 부분을 c언어로 코딩을 해보겠습니다.


[코딩]


순서도와 거의 비슷하다고 볼수 있습니다. 단지 c언어에서는 while 문을 사용하였는데요, 이부분이 순서도에서 분기문 이라고 생각 하시면 편합니다.


[결과]


두 수를 입력해서 최소,최대 공약수 값이 정상적으로 나타나게 됩니다.