◀️ 🌱 April 🌱 ▶️
일	월	목	금	토
		0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0

[Algorithm] 최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

2022. 11. 13. 13:52

728x90

최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

최대 공약수(GCD; Greatest Common Divisor(Factor))

두 개 이상의 자연수들의 공통인 약수들의 모임을 공약수(Common Divisor)라고 하고, 공약수 중에서 가장 큰 수를 최대 공약수(Greatest Common Divisor)라고 한다.
예) $12$ 의 약수는 $\{1, 2, 3, 4, 6, 12\}$ 이고 $18$ 의 약수는 $\{1, 2, 3, 6, 9, 18\}$ 일 때, 두 수 $12$ 와 $18$ 의 공약수는 $\{1, 2, 3, 6\}$ 이고 최대 공약수는 $6$ 이 된다.

코드


			
			
			
		
int gcd(int x, int y) {
    for (int i = (x > y ? y : x); i >= 1; i--) {    // 두 수의 최댓값부터 시작해서 1까지
        if (x % i == 0 && y % i == 0) {    // 두 수로 나누어 떨어질 경우
            return i;   
        }
    }
}

두 개의 정수 x와 y의 최대 공약수는 x와 y의 최솟값보다 클 수가 없기 때문에 for 문의 초기부 i는 두 개의 정수 x와 y 중에서 최솟값으로 초기화하고 초깃값부터 1까지 회전한다.
두 개의 정수 x와 y를 동시에 나눌 수 있는 첫 번째 정수가 두 수 x와 y의 가장 큰 공약수이므로, 첫 번째로 조건문을 만족하는 정수 i는 최대 공약수가 된다.

유클리드 알고리즘(Euclidean Algorithm) ; 유클리드 호제법

유클리드 알고리즘(Euclidean Algorithm) 또는 유클리드 호제법은 2개의 자연수의 최대 공약수(GCD)를 구하는 알고리즘이다.
유클리드(Euclid, BC330? ~ BC275?)가 기원전 300년 경에 쓴 『원론』 제 7권에 나오는 가장 오래된 알고리즘이다.
- "두 개의 자연수 A와 B에 대해서 A를 B로 나눈 나머지를 R이라고 하면(단, A ≥ B) A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다."
이 성질을 이용하여 B를 R로 나눈 나머지 R1을 구하고, 다시 R을 R1으로 나눈 나머지 R2를 구하고, 다시 R1을 R2로 나눈 나머지를 구하는 과정을 반복하다가 나머지가 0이 되었을 때 이 때 나누는 수 제수가 A와 B의 최대 공약수가 된다는 알고리즘이다.

그림으로 이해하기

8개의 상자가 놓여 있는 A 그룹과 3개의 상자가 놓여있는 B 그룹이 있을 때, 두 그룹 A와 B는 모두 1개의 상자의 배수이므로 두 그룹 A와 B의 최대 공약수는 1개의 상자가 된다.

A와 B 그룹은 둘 다 최대 공약수가 1개의 상자이므로, 1개의 상자의 배수이다.
A 그룹을 B 그룹으로 나눈 나머지는 2개의 상자가 나오고, 이 2개의 상자는 A 그룹에 있었던 상자이므로 나머지로 나온 2개의 상자도 최대 공약수인 1개의 상자의 배수가 된다.
다시 3개의 상자가 A 그룹이 되고, 나머지 2개의 상자가 B 그룹이 되어 같은 연산을 한다.

A와 B 그룹은 둘 다 최대 공약수인 1개의 상자의 배수의 배수이다.
A 그룹을 B 그룹으로 나눈 나머지는 1개의 상자가 나오고, 이 1개의 상자는 A 그룹에 있었던 상자이므로 나머지로 나온 1개의 상자도 최대 공약수인 1개의 상자의 배수가 된다.
다시 2개의 상자가 A 그룹이 되고, 나머지 1개의 상자가 B 그룹이 되어 같은 연산을 한다.

A와 B 그룹은 둘 다 최대 공약수인 1개의 상자의 배수의 배수이다.
A 그룹을 B 그룹으로 나누면 나머지는 0개의 상자가 나오고, B 그룹에 있던 1개의 상자가 지금까지 나누었던 모든 상자 그룹들을 나눌 수 있는 최대 상자이므로 마지막으로 남은 이 1개의 상자가 최대 공약수가 되는 것이다.
이것을 수학적으로 증명하면 다음과 같다.

수학적으로 증명하기

두 수 $A$ $A$ 와 $B$ $B$ 가 주어졌을 때 (단, $A \geq B$ $A ≥ B$ ), 두 수 A와 B의 최대 공약수를 $G$ $G$ 라고 하면 다음과 같이 나타낼 수 있다.

$A = Ga, \;B = Gb \; (\text{a와 b는 서로소})$

$A$ $A$ 를 $B$ $B$ 로 나눈 몫을 $Q$ $Q$ 라고 하고 나머지를 $R$ $R$ 이라고 한다면 다음과 같이 나타낼 수 있다.

$A = BQ + R$

여기서 $B$ $B$ 와 $R$ $R$ 의 최대 공약수가 $G$ $G$ 임을 증명하면 된다.
$B = G b$ $B = Gb$ 이고, $R = A - B Q = G a - G b Q = G (a - b Q)$ $R = A - BQ = Ga - GbQ = G(a - bQ)$ 가 된다.

$B = Gb, \; R = G(a - bQ)$

따라서 $B$ $B$ 와 $R$ $R$ 의 공약수는 $G$ $G$ 가 되는데, $b$ $b$ 와 $a - b Q$ $a - bQ$ 가 서로소임을 증명하면 공약수 $G$ $G$ 는 최대 공약수가 된다.
$b$ $b$ 와 $a - b Q$ $a -bQ$ 가 서로소임은 귀류법을 써서 증명할 수 있다.

만약 $b$ $b$ 와 $a - b Q$ $a - bQ$ 가 서로소가 아니라고 가정한다면, $b$ $b$ 와 $a - b Q$ $a - bQ$ 는 공통된 약수를 가지고 있을 것이고, 공통된 약수를 $p$ 라고 한다면 $b = np, \; a - bQ = mp$ 라 놓을 수 있다.
$a = mp + bQ$ 가 되고 $b = np$ 이므로 $a = mp + bQ = mp +npQ = p(m + nQ)$ 가 된다.
$a = p(m + nQ)$ 이고 $b = np$ 가 되기 때문에 $a$ $a$ 와 $b$ $b$ 는 공약수 $p$ $p$ 를 가진다.
이것은 $a$ $a$ 와 $b$ $b$ 가 서로소라는 가정에 모순이 되므로 $b$ $b$ 와 $a - b Q$ $a - bQ$ 는 서로소이다.

$b$ $b$ 와 $a - b Q$ $a - bQ$ 는 서로소이기 때문에 $B$ $B$ 와 $R$ $R$ 의 최대 공약수 $G$ $G$ 는 $A$ $A$ 와 $B$ $B$ 의 최대 공약수가 된다.
따라서 $A$ $A$ 를 $B$ $B$ 로 나눈 몫을 $Q$ $Q$ 라고 하고, 나머지를 $R$ 이라고 한다면 $gcd(A, B)$ 는 $gcd(B, R)$ 과 같다.


			
			
			
		
int gcd(int x, int y) {
    int r;
    
    while (y) {
        r = x % y;    // (1), (4), (7)
        x = y;        // (2), (5), (8)
        y = r;        // (3), (6), (9)
    }
    return x;
}

두 개의 정수 $12$ $12$ 와 $18$ $18$ 을 $x$ $x$ 와 $y$ $y$ 에 전달하고, $x$ $x$ 를 $y$ $y$ 로 나눈 나머지를 $r$ $r$ 이라고 할 때, $x$ $x$ 와 $y$ $y$ 의 최대 공약수는 $y$ $y$ 와 $r$ $r$ 의 최대 공약수와 같으므로 먼저 $x$ $x$ 를 $y$ $y$ 로 나눈 나머지 $r$ $r$ 을 구한 후, 같은 작업을 반복하기 위해서 $x$ $x$ 의 값에 $y$ $y$ 의 값을 대입하고 $y$ $y$ 의 값에 $r$ $r$ 의 값을 대입한다.
$x$ $x$ 를 $y$ $y$ 로 나눈 나머지가 $0$ $0$ 일 때, 제수 $y$ $y$ 가 최대 공약수가 되지만, 한 번 더 다음 과정을 진행하면 $x = y$ $x = y$ 에 의해서 $x$ $x$ 의 값은 $y$ $y$ 의 값이 되고, $y = r$ $y = r$ 에 의해서 $y$ $y$ 의 값은 $0$ $0$ 이 되므로 최대 공약수인 $x$ $x$ 의 값을 반환한다.

코드


			
			
			
		
#include <iostream>
using namespace std;
 
int gcd(int x, int y) {
    int r;
    
    while (r) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}
 
int main() {
    int a, b;
    
    cin >> a >> b;
    cout << gcd(a, b) << '\n';
    
    return 0;
}

최소 공배수(LCM; Least Common Multiple)

두 개 이상의 자연수들의 공통인 배수들의 모임을 공배수(Common Multiple)라고 하고, 공배수 중에서 가장 작은 수를 최소 공배수(Least Common Multiple)라고 한다.
예) $3$ 의 배수는 $\{3, 6, 9, 12, \cdots \}$ 이고 $4$ 의 배수는 $\{4, 8, 12, 16, \cdots \}$ 일 때, 두 수 $3$ $3$ 과 $4$ 의 공배수는 $\{ 12, 24, 36, \cdots \}$ 이고 최소 공배수는 $12$ 가 된다.

두 개의 자연수 $A$ $A$ 와 $B$ $B$ 의 최대 공약수를 $G$ $G$ 라고 하고 최소 공배수를 $L$ $L$ 이라고 하면 다음과 같은 관계식이 성립한다.

$A \times B = L \times G$

$A$ $A$ 와 $B$ $B$ 의 최대 공약수가 $G$ 이므로 $A = aG, \; B = bG$ ( $a, b$ $a, b$ 는 서로소)로 나타낼 수 있다.
그러면 두 수의 최소 공배수( $L$ $L$ )는 $abG$ 가 된다.
두 수 $A$ $A$ 와 $B$ 를 곱하면 $AB = aGbG$ 가 되고, 최대 공약수( $G$ $G$ )와 최소 공배수( $L$ $L$ )를 곱하면 $L G$ $LG$ 는 $a b G G$ $abGG$ 가 된다.
두 수 $A$ $A$ 와 $B$ $B$ 의 곱은 최소 공배수인 $L$ $L$ 과 최대 공약수인 $G$ $G$ 를 곱한 값과 같기 때문에 최소 공배수는 알고리즘을 따로 작성하여 구하는 것이 아니라, 두 수 $A$ $A$ 와 $B$ $B$ 를 곱한 후 최대 공약수 $G$ $G$ 로 나누면 구할 수 있다.

코드


			
			
			
		
#include <iostream>
using namespace std;
 
int gcd(int x, int y) {
    int r;
    
    while (r) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}
 
int main() {
    int a, b;
    
    cin >> a >> b;
    cout << a * b / gcd(a, b) << '\n';
    
    return 0;
}

재귀 함수를 이용하여 최대 공약수/최소 공배수 구하기

최대 공약수와 최소 공배수를 다음과 같이 재귀 함수를 이용하여 구할 수 있다.


			
			
			
		
// GCD : 최대공약수
int gcd(int x, int y) {
	if (x == 0) return y;
	else return gcd(y % x, x);
}
 
// LCM : 최소공배수
int lcm(int x, int y) {
	return (x * y) / gcd(x, y);
}

참고 사이트

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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란

ko.wikipedia.org

https://namu.wiki/w/%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

최소공배수 - 나무위키

예시로 두 수 10, 12의 공배수를 찾고 싶다고 하자. 먼저 두 수의 배수를 쭉 나열한다. 10: 10, 20, 30, 40, 50, 60, 70, ... 12: 12, 24, 36, 48, 60, 72, ... 여기서 위아랫줄 동시에 나타나는 수가 바로 공배수이다.

namu.wiki

https://namu.wiki/w/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

최대공약수 - 나무위키

예시로 두 수 12, 18의 공약수 및 최대공약수를 찾고 싶다고 하자. 간단하게, 두 수의 약수를 모두 나열한다. 12: 1, 2, 3, 4, 6, 12 18: 1, 2, 3, 6, 9, 18 여기서 위아랫줄 모두 같이 있는 숫자가 공약수가 된

namu.wiki

728x90

저작자표시 비영리 변경금지

'Computer Science > 알고리즘' 카테고리의 다른 글

[Algorithm] 백트래킹(Backtracking) (0)	2022.11.16
[Algorithm] 이항 계수(Binomial Coefficient) (0)	2022.11.15
[Algorithm] 브루트 포스(Brute Force) (0)	2022.11.03
[Algorithm] 하노이 탑(Tower of Hanoi) (0)	2022.11.03
[Algorithm] 스캐닝 메소드(Scanning Method) (0)	2022.10.26
[Algorithm] 부분합(Partial Sum) ; 누적합(Prefix Sum) (0)	2022.10.26
[Algorithm] 형상수(Figulate Number) (0)	2022.10.26
[Algorithm] 에라토스테네스의 체(Sieve of Erathosthenes) (0)	2022.10.25

Per ardua ad astra."Hello, World!" 🤖

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Per ardua ad astra.

"Hello, Wo

[Algorithm] 최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

최대 공약수(GCD)와 최소 공배수(LCM) ; 유클리드 호제법(Euclidean Algorithm)

최대 공약수(GCD; Greatest Common Divisor(Factor))

코드

유클리드 알고리즘(Euclidean Algorithm) ; 유클리드 호제법

그림으로 이해하기

수학적으로 증명하기

코드

최소 공배수(LCM; Least Common Multiple)

코드

재귀 함수를 이용하여 최대 공약수/최소 공배수 구하기

참고 사이트

'Computer Science > 알고리즘' 카테고리의 다른 글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

	int gcd(int x, int y) {
	for (int i = (x > y ? y : x); i >= 1; i--) { // 두 수의 최댓값부터 시작해서 1까지
	if (x % i == 0 && y % i == 0) { // 두 수로 나누어 떨어질 경우
	return i;
	}
	}
	}

	int gcd(int x, int y) {
	int r;

	while (y) {
	r = x % y; // (1), (4), (7)
	x = y; // (2), (5), (8)
	y = r; // (3), (6), (9)
	}
	return x;
	}

	#include <iostream>
	using namespace std;

	int gcd(int x, int y) {
	int r;

	while (r) {
	r = x % y;
	x = y;
	y = r;
	}
	return x;
	}

	int main() {
	int a, b;

	cin >> a >> b;
	cout << gcd(a, b) << '\n';

	return 0;
	}

	// GCD : 최대공약수
	int gcd(int x, int y) {
	if (x == 0) return y;
	else return gcd(y % x, x);
	}

	// LCM : 최소공배수
	int lcm(int x, int y) {
	return (x * y) / gcd(x, y);
	}