[Python 알고리즘 공부] 유클리드 호제법 최대공약수 구하기, 기약분수 구하기

유클리드 호제법

• 두 개의 정수나 자연수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 대표적인 알고리즘
• 두 수의 나머지를 구하고, 이 나머지를 이용해 다시 나눗셈을 반복하여 나머지가 0이 될 때까지 계속하는 원리
• 나머지가 0이 되었을 때의 나누는 수(divisor)가 바로 두 수의 최대공약수

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

 

기약 분수 구하기

• 분자와 분모를, 유클리드 호제법으로 찾은 최대공약수로 나누어 기약분수 형태로 만듦 

def reduce_fraction(a, b):
    gcd_value = gcd(a, b)
    a_reduced = a // gcd_value
    b_reduced = b // gcd_value
    return a_reduced, b_reduced