------------------------------------------------------------ 이 포스팅과 관련된 포스팅
- 2차원 배열 ㄹ자 알고리즘 및 c언어 로 코딩.
- 화폐 단위별 매수 알고리즘(정보처리기사) c언어 소스 포함.
- 버블정렬 알고리즘(정보처리기사) c언어 코딩 포함.
- A배열에서 B배열로 옮기는 알고리즘 A(3,4) -> B(4,3) 정보처리기사 (C언어 코딩 포함)
[유클리드 호제법을 이용한 최대공약수,최소공배수 알고리즘]
이틀 연속 글을 쓰는것 같습니다. 한동안 못한 숙제를 몰아서 하는 기분(?) 이 드네요 ㅎ
요즘들어서 알고르즘, DB, 언어 등 학부생때에 공부하였던 부분을 다시 한번 되세기는 시기를 마련해볼려고 하는데요, 특별한 이유는 없습니다. 머리를 쓰고, 고민하는 습관을 들이기 위해서 랄까요? 직장생활을 하다보면, 업무특성상 머리를 쓰지 못하는 경우도 생길수도 있습니다. 그냥 멍~ 때리는 경우가 많아지죠. 그래서 이번에 마음먹고 데일리 습관을 들어볼려고 합니다.
서두가 길었네요 ㅎ
그럼 일단 진행하기 전에 우리가 초등학교때 배웠던 최대공약수와 최소공배수를 한번 살펴볼까요?
[최대공약수]
공약수는 두 개 이상의 자연수의 공통된 약수입니다. 이 공약수 중에서 가장 큰 공약수를 바로 최대공약수라고 합니다.
최대공약수를 알면 공약수를 쉽게 구할 수 있는데요, 바로 최대공약수의 약수가 바로 공약수거든요. 공약수를 구할 때 최대공약수를 구한 다음에 최대공약수의 약수를 구하는 방법을 이용합니다.
예를 들어 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의 배수이다.
이틀 연속 글을 쓰는것 같습니다. 한동안 못한 숙제를 몰아서 하는 기분(?) 이 드네요 ㅎ
요즘들어서 알고르즘, DB, 언어 등 학부생때에 공부하였던 부분을 다시 한번 되세기는 시기를 마련해볼려고 하는데요, 특별한 이유는 없습니다. 머리를 쓰고, 고민하는 습관을 들이기 위해서 랄까요? 직장생활을 하다보면, 업무특성상 머리를 쓰지 못하는 경우도 생길수도 있습니다. 그냥 멍~ 때리는 경우가 많아지죠. 그래서 이번에 마음먹고 데일리 습관을 들어볼려고 합니다.
서두가 길었네요 ㅎ
그럼 일단 진행하기 전에 우리가 초등학교때 배웠던 최대공약수와 최소공배수를 한번 살펴볼까요?
[최대공약수]
공약수는 두 개 이상의 자연수의 공통된 약수입니다. 이 공약수 중에서 가장 큰 공약수를 바로 최대공약수라고 합니다.
최대공약수를 알면 공약수를 쉽게 구할 수 있는데요, 바로 최대공약수의 약수가 바로 공약수거든요. 공약수를 구할 때 최대공약수를 구한 다음에 최대공약수의 약수를 구하는 방법을 이용합니다.
예를 들어 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 문을 사용하였는데요, 이부분이 순서도에서 분기문 이라고 생각 하시면 편합니다.
그럼 결과값이 어떻게 나오나 볼까요?
[결과]
두 수를 입력해서 최소,최대 공약수 값이 제대로 나왔네요.