[Algorithm] 알고리즘 : 유클리드 호제법(최대공약수 구하는 알고리즘)

유클리드 호제법으로 최대공약수 구하기

 

 

유클리드 호제법 개념

---

최대공약수를 구하는 하나의 알고리즘(문제 해결 방식)

                    ㄴHow? 큰 수를 작은 수로 나누어 나머지가 0이 되도록 만들어 주는 수가 최대공약수(GCD)

 

 

 

 

 

왜 나오게 됬을까?

---

일반적으로, 최대공약수를 구할 때에는 두 수 각각을 소인수 분해하여 공통된 소수를 찾으면 된다.

 

16 = 2 * 2 * 2 * 2

24 = 2 * 2 * 2 * 3

 

최대공약수 : 8

 

 

컴퓨터의 세계에서 두 수가 적을 때에 위의 방식은 정말 편하다. 하지만 엄청난 큰 수로 구하려고 한다면 어떻게 될까?

(23123과 1231424 등)

 

엄청난 큰 수를 쪼개고 쪼개고 하게 된다면 시간적 소모가 크고, 메모리적 낭비가 발생할 수밖에 없다.

(시간 대비 결과, 메모리 공간적 대비 결과가 낭비가 된다.)

 

    Ex)

    1분이면 끝낼 수 있는 일을, 10시간 동안 잡고 일을 한다.

 

    Ex2)

    작은 그릇으로 담을 수 있는 양을, 큰 그릇에 담아 불필요한 공간을 낭비한다.

 

 

이러한 문제를 해결하고자, 보다 편하고 빠르게 나온 하나의 문제 해결 기법인 것이다.

 

 

 

코드로 살펴보기 전, 개념 확인하기

---

Q)

16과 24의 최대공약수?


2 ㅣ 16 ㅣ 24
   ㄴㅡㅡㅡㅡㅡ
2 ㅣ 8  ㅣ 12
   ㄴㅡㅡㅡㅡㅡ
2 ㅣ  4  ㅣ  6
   ㄴㅡㅡㅡㅡㅡ
       2  ㅣ  3

 

 

Q)
* 최대공약수(GCD)

: 2 * 2 * 2 = 8

 

Q)

* 최소공배수

 

: 8 * 6 = 8(최대공약수) * 2 * 3


Q)
* 최대공약수를 이용한 원래 수(16, 24 쪼개기)

: 16 = 8 * 2(마지막에 있는 2)

: 24 = 8 * 3(마지막에 있는 3)

 

 

 

 

 

"유클리드 호제법 방법"

---

 

유클리드 호제법

< 설 명 >

 

1. 우선 16과 24를 비교한다.

 

2. 24를 16으로 나눈다

 

3. 나머지가 8이 된다.

 

4. 이 나머지 8을 다시 16으로 나눈다.

 

5. 나눈 나머지가 0이다.

 

6. 8이 최대공약수이다.

 

 

 

 

 

그렇다면 최소 공배수는?

---

16과 24의 최소공배수(LCM)를 구했을 때는 48

 

 

 16 = 8(최대공약수) * 2

 24 = 8(최대공약수) * 3

위의식과 아래식을 곱하면

16*24 = 8*8*2*3

8(최대공약수)로 나누면

(16*24)/8 = 8 * 2 * 3 = 48 같다

 

 

수식으로 살펴보기

---

두 자연수 A, B라 할 때

 

* GCD(A,B) = 최대공약수

Greatest

Common

Divisor

 

* LCM(A,B) = 최소공배수

 

 

Least

Common

Multiple

 

* A = GCD(A,B) * Ra(remain A, 나머지)
:16 = 8 * 2


* B = GCD(A,B) * Rb(remain B, 나머지)
:24 = 8 * 3

* GCD(A,B) :  A,B의 최대공약수

* (A * B) / GCD(A,B) = GCD(A,B) * Ra * Rb = LCM(A,B)(최소공배수)
:(16 * 24) / 8 = 8 * 2 * 3 = 48

 

 

 

코드로 살펴보기(파이썬, C)

---

1. 파이썬 코드(자리 바꾸기 temp대체)

 

 

def gcd(a, b): 
    if a < b: 
        (a, b) = (b, a)  
    while b != 0: 
        (a, b) = (b, a % b) 
    return a
 
def lcm(a, b):
    return a*b//(gcd(a,b))
 
# gcd(16,24)
# 8
 
# lcm(16,24)
# 48

: 기준을 잡아준다. 
a 쪽에 큰 값이 오게끔 한다.

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지와
최대공약수와 같기 때문에, 나머지가 0이 될 때까지 작업을 반복해준다. 

b(=나머지)가 0일 때의 a값이 a, b의 최대공약수가 된다.

 

 

< < 파이썬 자리 바꾸기(temp 대체) 링크 > >

 

2020/10/11 - [* Programming Language/Python] - [Python] 파이썬 변수값 바꾸기(Swap)

[Python] 파이썬 변수값 바꾸기(Swap)

2. C 코드(재귀)
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

#include <stdio.h> 
#include <stdlib.h> 
 
int gcd(int, int); 
int lcm(int, int); 
 
int main() 
{ 
    int m,n; 
    scanf("%d %d", &m, &n); 
    printf("최대공약수: %d\n", gcd(m,n)); 
    printf("최소공배수: %d", lcm(m,n)); 
} 
 
int gcd(int a, int b){ 
    if(b==0){ 
        return a; 
    } 
    gcd(b, a%b); 
 
} 
 
int lcm(int a, int b){ 
return a * b /gcd(a,b); 
} 

: 단지 재귀의 방식이라는 차이

 

 

 

< < 재귀 설명 링크 > >

 

2020/10/13 - [* Data Structure] - [Data Structure] 자료구조 : 재귀(Recursion)란?

[Data Structure] 자료구조 : 재귀(Recursion)란?

 

 

 

정 리

---

1. 유클리드 호제법

 

: 최대공약수를 구하는 하나의 알고리즘(문제 해결 방식)

                    ㄴHow? 큰 수를 작은 수로 나누어 나머지가 0이 되도록 만들어 주는 수가 최대공약수(GCD)

 

2. 키보드에 손 올려서 코딩하기 전 노트와 팬을 들고 적어나가면서 학습