유클리드 호제법

알고리즘 문제에서 최대공약수 또는 최소공배수 관련된 문제가 나오면 유클리드 호제법을 사용해야 한다.

 

유클리드 호제법이란... 최대공약수를 구하는 방법

 

두 정수 a와 b의 최대공약수(gcd)를 구하는 경우:

1. a를 b로 나눕니다. 나눈 나머지를 r에 저장
2. r이 0이면, b가 최대 공약수
3. r이 0이 아니면, a를 b로, b를 r로 대체하고, 다시 1번 단계로
4. r이 0이 될 때까지 1번과 2번을 반복합니다.

 

예시)

24와 18의 최대공약수 구하기

 

a=24  b=18

24/18 = 몫:1  나머지(r):6

r이 0이 아니기 때문에 a = b로 b = r

a=18  b=6

18/6 = 몫:3  나머지(r):0

r이 0이기 때문에 현재 b값, 6이 최대공약수이다.

 

참고로 나는 꼭 a>b 여야 하는 줄 알았는데 크기는 상관없다. 어떤 수가 a 또는 b가 되어도 같은 값이 나오기 때문에

 

 

파이썬 코드로 표현

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

 

 

사실 파이썬에는 내장 함수도 있다

import math

a = 48
b = 18

result = math.gcd(a, b)
print(result)