입력 받은 두 수 A, B에 대한 최대공약수와 최소공배수를 유클리드 호제법으로 처리하려고 한다. 제시된 <그림>의 괄호 안 내용 (1)~(5)에 가장 적합한 항목을 <답항 보기>에서 선택하여 답안지의 해당 번호 (1) ~ (5)에 각각 마크하시오.
<처리조건>
- <그림> 의 순서도에 제시되어 있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 구현될 수 있도록 답안을 선택하시오.
- 입력 받는 두수 A, B는 0이 아닌 서로 다른 양의 정수로 가정한다.
- MOD()는 괄호 안의 연산 수행하며 나머지를 구하는 함수이다. 예를 들어 MOD(5/3)의 값은 2이며, MOD(20/5)의 값은 0이다.
- 기호 “/” 는 나누기 연산 “*”는 곱셈 연산을 나타낸다.
최대공약수?
12의 약수 = 1, 2, 3, 4, 6, 12
18의 약수 = 1, 2, 3, 6, 9, 18
공약수: 공통된 약수를 보통 공약수라고 부른다.
12, 18의 공약수 : 1, 2, 3, 6
공약수 중에서 가장 큰 수가 최대공약수이다.
여기서는 6이다.
최소공배수?
2의 배수 = 2, 4, 6, 8, 10, 12, 14, 16, 18…
3의 배수 = 3, 6, 9, 12, 15, 18, 21, 24, 27…
공배수 = 6, 12, 18…
공배수 중에서 가장 작은 수가 최소 공배수이다.
유클리드 호제법?
큰수 / 작은수 -> 나머지
나머지가 0 이면 최대공약수 = 작은수, 최소공배수= 두수 곱/최대공약수
나머지가 0 이 아니면 큰수 = 작은 수, 작은 수 = 나머지
'정보처리기사 > 알고리즘' 카테고리의 다른 글
[06년11월] 10진수를 2진수로 변환 (0) | 2017.08.02 |
---|---|
[07년 2월] 평균과 석차 구하기 (0) | 2017.08.02 |
[07년4회] 그레이코드와 이진수간의 변환 (0) | 2017.08.02 |
[07년2회] 삽입 정렬 (0) | 2017.08.02 |
[09년] 구구단 (0) | 2017.08.02 |