유클리드 호제법

유클리드 호제법

---

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.

이 알고리즘은 두 수를 나눈 나머지를 이용해 최대공약수를 구하는 방법이다.

 

먼저, 큰 수를 작은 수로 나눈 나머지를 구하고, 작은 수를 이전에 구한 나머지로 나눈 나머지를 구한다.

이 과정을 나머지가 0이 될 때까지 반복하다 마지막으로 구한 나머지가 최대공약수가 된다.

 

조금 더 구체적으로 예를 들자면 49와 21가 있다고 생각해보자

49를 21로 나누어 떨어지지 않으니까 49를 21로 나눈 나머지 값은 7이다.

21을 7로 나누면 나누어 떨어진다.(나머지가 0이 될 때까지 반복한다는 것이 이 뜻)

즉 7이 최대공약수가 되는 것

 

아래 백준 문제를 풀다가 보게 된 수학공식? 알고리즘? 인데

코드로는 아래처럼 볼 수 있다.

 

 

[백준] 2609번 - 최대공약수와 최소공배수

---

# 최대공약수(유클리드 호제법)
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

# 최소공배수(두 수를 곱하여 최대공약수로 나누면 된다.)
def lcm(a, b):
    return a * b // gcd(a, b)

 

Notion Link : https://solar-textbook-084.notion.site/75fb6c83a5d84ab3ada2669139276ab7