목차
1. 유클리드 알고리즘이란?
- 2개의 자연수 혹은 두 다항식의 최대 공약수를 구하는 방법
- 서로 나누어 해를 구하므로 유클리드 호제법(互除法 : 합(互)하고 나누는(除) 방법(法))이라고도 한다.
2. 로직
가. 최대 공약수
두개의 자연수 a,b (a>b)에 대하여 a를 b로 나눈 나머지가 r일 때,
a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
이에 따라 b와 r에 대해서 나머지 r2를 구하고
r을 r2로 나누는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대 공약수가 된다.
나. 최소 공배수
최소 공배수는 최대 공약수를 이용하여 구할 수 있다.
두개의 자연수 a,b (a>b)에 대하여 a와 b의 최소 공배수는a와 b의 곱을 a와 b의 최대 공약수로 나눈 값이다.
3. 구현하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
//최대 공약수
int GCD(int a, int b) // 재귀로서 나누어 떨어질 때 까지 반복한다.
{
int r = a % b; // 두개의 자연수 a,b (a>b)에 대하여 a를 b로 나눈 나머지가 r일 때
if (r == 0) // 나누어 떨어질 경우 나누는 b가 최대 공약수가 된다.
return b;
return GCD(b, r); // a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
}
//최소 공배수
int LCM(int a, int b) // a와 b의 최대 공배수는 a와 b의 곱을 a,b의 최대 공약수로 나눈 값이다.
{
return a * b / GCD(a, b);
}
|
cs |
※ 참조
위키 백과 유클리드 호제법
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
'C++ > 알고리즘' 카테고리의 다른 글
| [C++] 알고리즘 #2 백트래킹 알고리즘 (Backtracking algorithm) (0) | 2023.07.09 |
|---|