유클리드 호제법

안녕하세요. 오늘은 최대공약수를 찾는 효율적인 방법인 유클리드 호제법에 대해 함께 알아보도록 하겠습니다. 수학과 프로그래밍에서 많이 사용되는 이 알고리즘을 이해하고 활용한다면, 여러분의 문제 해결 능력을 한 단계 높일 수 있을 것입니다.

 

유클리드 호제법이란?

유클리드 호제법은 두 개의 자연수나 다항식의 최대공약수를 구하는 알고리즘입니다. 

유클리드 호제법 : 두 자연수의 최대 공약수(GCD)를 구하는 알고리즘에 대해 설명드리겠습니다.

1. 최대 공약수(GCD)란 두 개 이상의 자연수의 공통된 약수 중 가장 큰 수를 말합니다.
2. 최소 공배수(LCM)은 두 개 이상의 자연수의 공통된 배수 중 가장 작은 수를 말합니다.

 

유클리드 호제법의 원리

유클리드 호제법의 기본 원리는 이렇습니다: "두 수 a, b (a > b)의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다"입니다. 이 원리를 반복적으로 적용하면, 'a를 b로 나눈 나머지'가 0이 되는 순간의 'b'가 a와 b의 최대공약수(GCD)가 됩니다.

 

예를 들어 두 수 24와 18의 최대공약수를 과정을 유클리드 호제법을 사용하여 살펴봅시다.

1. 24를 18로 나누면, 몫이 1이고 나머지가 6이 됩니다. 따라서 '18과 6의 최대공약수'는 24와 18의 최대공약수와 같습니다.

2. 다음으로, 18을 6으로 나누면, 몫이 3이고 나머지가 0이 됩니다. 따라서 '6과 0의 최대공약수'는 18과 6의 최대공약수와 같습니다.

3. 마지막으로 6과 0의 최대공약수는 6이므로 24와 18의 최대공약수는 6임을 알 수 있습니다.

Python에서는 'math' 모듈의 'gcd()' 내장 함수를 사용하여 최대공약수를 구할 수 있습니다. 하지만 만약 모듈을 사용할 수 없는 상황에서 직접 구현해야 한다면 아래에 제공하는 코드를 참조해주시기 바랍니다. 이를 통해 GCD와 LCM을 구하는 방법을 배울 수 있습니다.

Python 코드

import math

a = 12
b = 18
gcd = math.gcd(a, b)
print(gcd)  # 6 출력

# 최대 공약수 직접구현
def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a
    
# 최소 공배수
lcm = n * m // gcd(a, b)


# 완전탐색
def gcd(a, b):
    gcd = 0
    min_val = min(a, b)
    for i in range(1, min_val + 1):
        if a % i == 0 and b % i == 0:
            gcd = i

    return gcd

이 코드를 보면, while 반복문 안에서 'a를 b로 나눈 나머지'를 계속해서 b에 할당하고, a에는 이전의 b 값을 할당하는 과정이 반복되는 것을 볼 수 있습니다. 이 과정이 반복되다 보면, 'a를 b로 나눈 나머지'가 결국 0이 되고, 그 때의 b 값이 최대공약수가 되는 것입니다.

 

마무리

이렇게 유클리드 호제법을 이용하면, 최대공약수를 효율적으로 찾을 수 있습니다.
유클리드 호제법은 그 자체로도 유용하지만, 이런 기본적인 알고리즘을 이해하고 활용하는 능력은 프로그래밍 뿐만 아니라 문제 해결 능력을 향상시키는 데에 큰 도움이 됩니다.

다음에도 유익한 내용으로 찾아뵙겠습니다. 감사합니다!