[알고리즘/파이썬] 유클리드 호제법 - 최대공배수 최대공약수 쉬운 설명

학교에서 배운 최대공배수 구하는 방법과

유클리드 호제법 알고리즘을 사용해서 코드를 구현하는 방법은 다르다.

 

나처럼 유클리드 호제법이 뭔데? 라고 생각한 분들을 위해

5분 안에 쉽게 이해되도록 설명해보겠다.

 

최소공배수를 구하는 공식에 최대공약수가 들어가므로

최대공약수 먼저 알아보겠다.

 

 

※ 유클리드 호제법 - 최대 공약수

 

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

먼저 MOD 연산을 알고 있어야 하는데 MOD는 두 수의 나머지를 구하는 연산이다.

예를 들어 파이썬에서 나머지를 구하는 연산은 % 이며, 10 % 6 = 4 가 나온다.

 

유클리드 호제법으로 108과 138의 최대공약수를 구해보겠다.

이해하기 쉽게 그림으로 풀어봤다.

 

 

1. 큰 수를 작은 수로 MOD 연산 실행

2. 전 단계에서의 작은 수와 나머지(결과값)로 MOD 연산 실행

3. 나머지가 0이 될 때까지 재귀함수로 반복

4. 나머지가 0이 나왔을 때 작은 수가 두 수의 최대 공약수

 

 

최대공약수 코드

 

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

def gcd(x, y):
    if y == 0:      # y가 0이면 x가 최대공약수
        return x
    else:
        return gcd(y, x % y)    # 재귀로 구현

if a > b:
    res = gcd(a, b)
else:
    res = gcd(b, a)
    
print(res)

 

 

※ 최소 공배수

 

최소공배수의 공식은 두 수 A와 B가 입력값으로 주어졌을때,

A * B / 최대공약수 이다.

 

A가 6, B가 10인 경우 최소 공배수를 구하는 방법은 아래 그림과 같다.

 

최소공배수 코드

 

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)

print(int(a*b/gcd(a, b)))		# 최소공배수 공식

 

 

알고리즘 문제 풀기

 

이제 유클리드 호제법 알고리즘으로 백준 최대공약수, 최소공배수 문제를 풀어보겠다.

대표적으로 1850번과 1934번이 있고 풀이 코드는 아래 링크를 참조하면 된다.

 

[백준 1850번 최대공약수 문제]

[백준] 1850번 최대공약수 파이썬 Python / 유클리드 호제법 풀이

 

[백준 1934번 최소공배수 문제]

[백준] 1934번 최소공배수 - 유클리드 호제법 풀이 파이썬 Python