[#85][자격증] 정보처리기사 실기 알고리즘 (유클리드 호제법 최대공약수, 최소공배수)
정보처리기사 실기 알고리즘 (유클리드 호제법 최대공약수, 최소공배수)
두 수 A, B에 대한 최대 공약수와 최소 공배수를 유클리드 호제법으로 처리하려고 한다.
<처리 조건>
1. 순서도에 제시되어 있는 미완성 알고리즘을 분석하여, 가장 적합한 로직으로 연계되어 구현될 수 있도록 답안 선택 시 유의하시오.
2. 입력받는 두 수 A, B는 0이 아닌 서로 다른 양의 정수로 가정한다.
3. MOD()는 괄호 안의 연산을 수행하며 나머지를 구하는 함수이다.
ex) MOD(5/3) = 2, MOD(20/5) = 0
4. 기호 "/"는 나누기 연산, "*"는 곱하기 연산을 나타낸다.
유사한 문제(https://dailyddubby.blogspot.kr/2018/03/19-n.html)
----------------------------정답----------------------------------
① HIGH = B
② R
③ LOW
④ LOW = R
⑤ A * B
-------------------------------------------------------------------
▶유클리드 호제법?
a, b (a>b)
a%b==0 이면 최대공약수는 b
a%b!=0이면 a=b, b = a%b
gcd(a,b)라는 함수가 있을 때
a%b==0이면 return b;
a%b!=0이면 return gcd(b, a%b);
//최대공약수
long long gcd(long long a, long long b){
return a%b==0 ? b : gcd(b, a%b);
}
| cs |
▶최소공배수 구하기
a * b = 최대공약수 * 최소공배수
최소공배수 = (a * b) / 최대공약수
C++구현
#include <iostream>
using namespace std;
int main(){
int HIGH, LOW, L, A, B, R = 1;
cin >> A >> B;
if (A > B) {
HIGH = A;
LOW = B;
}
else {
LOW = A;
HIGH = B;
}
while (R > 0) {
R = HIGH % LOW;
HIGH = LOW;
LOW = R;
}
//최소공배수
L = (A*B) / HIGH;
cout << HIGH << " " << L << endl;
return 0;
}
| cs |
댓글
댓글 쓰기