[기사 기출]3. 최대공약수, 최소공배수 (10년1회, 16년 1회 출제)

안녕하십니까 유건아빠입니다.

오늘은 정보처리기사-실기-알고리즘 [최대공약수,최소공배수] 구하는 순서도를 공부보겠습니다.

최대공약수와 최소공배수 구하기는 중1 수학에 나오는 내용이니 다들 기억하시죠?

최대공약수 : 두 개 이상의 자연수들의 공약수 중에서 가장 큰 수

   - 공약수 : 두 개 이상의 자연수들의 공통인 약수

   - 약수 : 어떤 자연수를 나누어떨어지게 하는 수

 최소공배수 : 두 개 이상의 자연수들의 공배수 중에서 가장 작은 수

   - 공배수 : 두 개 이상의 자연수들의 공통인 배수

   - 배수 : 어떤 자연수 N에 자연수 1, 2, 3, ... 을 곱하여 나온 수

우리는 소인수분해로 최대공약수오 최소공배수를 쉽게 구할수 있죠.

예를 들면 아래와 같이 두수 15와 12 가 있을경우 두 수를 공통으로 나눌수 있는 3으로 나누어 더이상 나눌수 없을때

3은 최대 공약수가 되고, 3 으로 두수를 나눠 각각 나머지가 5와 4가 되고 이를 최대공약수인 3과 모두 곱하면 3*5*4 = 60 이 최소 공배수가 됩니다.

이렇게 구하는 방법은 사람이 구하는 방식이고 이걸 컴퓨터가 계산할수 있도록 하는 방법이 바로 유클리드호제법이라고 합니다.

유클리드호제법

'X를 Y로 나눈 나머지 값을 R이라고 했을때 X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다.'

좀 헷갈릴수 있으나, 아래처럼 잘 정리해서암기 하시면 기사시험때 최대공약수,최소공배수는 쉽게 해결 하실수 있습니다. 

자 그러면 기출문제를 실제로 보도록 하겠습니다.

최대공약수,최소공배수 (10년1회, 16년1회 동일하게 출제)

(1). HIGH = B  -> 큰수 결정하는 부분으로서  A>B 비교해서 NO일때는  A가 작은수 B가 큰수가 됩니다.

(2). R -> 큰수를 작은수로 나눈 나머지를 저장하는 변수

(3). LOW -> 유클리드호제법에서 나머지가 0이 아니면 큰수=작은수, 작은수=나머지  설정은 하는것이므로  답은  LOW입니다.

(4). LOW = R -> (3)에서 큰수를 LOW로 설정하듯이 LOW는 나머지인 R을 대입합니다.

(5). A * B -> 유클리드호제법에서 나머지가 0일경우, 최대공약수=작은수, 

최소공배수는 = 두수의 곱/ 최대공약수 이므로  L= (A*B )/ HIGH

제 포스팅이 도움이 되셨다면

로그인이 필요없는 ↓♡공감↓ 꾸~욱 부탁드려요^^ 

더 나은 포스팅에 큰 힘이 됩니다.