[Python] gcd 함수 : 최대공약수

알고리즘 문제들을 풀다 보면 누구나 한 번쯤은 최대공약수, 최소공배수를 구해야 되는 문제를 만날 것입니다.

최대공약수와 최소공배수를 구하기 위해 사용하는 알고리즘으로 유클리드 호제법이 있습니다.

그래서 최대공약수, 최소공배수를 구할 때는 함수를 따로 선언하고

내부에서 유클리드 호제법을 직접 구현해서 최대공약수, 최소공배수를 반환하는 방법으로 많이들

최대공약수와 최소공배수를 구합니다.

 

파이썬에서는 위와 같이 따로 함수를 직접 구현하지 않더라도

최대공약수를 반환하는 함수 gcd, 최소공배수를 반환하는 함수 lcm을

math 모듈에서 제공합니다.

 

밑의 링크들은 백준에 있는 문제들 중 gcd, lcm 함수를 사용해서 푼 문제들입니다.

[백준][solved.ac][Silver 5][Python] 14914번 : 사과와 바나나 나눠주기

[백준][solved.ac][Silver 4][Python] 14490번 : 백대열

[백준][solved.ac][Silver 5][Python] 2609번 : 최대공약수와 최소공배수

[백준][solved.ac][Silver 5][Python] 9417번 : 최대 GCD

제 블로그에 위의 네 문제 말고도 gcd, lcm 함수를 활용해서 푼 문제들이 더 있으니

더 많은 풀이를 보시고 싶은 분은 블로그 내에서 gcd나 lcm으로 검색해 둘러보시면 됩니다.

 

이번 포스팅에서는 최대공약수를 반환하는 함수인 gcd 함수에 대해서 먼저 포스팅하겠습니다.

 

 

 

 

 

 

 

 

1. 최대공약수

약수는 어떤 정수가 있을 때, 그 정수를 정확히 나눌 수 있는 정수들을 말합니다.

공약수는 어떤 정수들이 있을 때, 그 정수들을 정확히 나눌 수 있는 공통된 약수들을 말합니다.

최대공약수는 공약수들 중에서 가장 큰 공약수입니다.

 

영어로는 Greatest Common Divisor라고 하며 이를 약자로 줄여서 GCD라고 합니다.

gcd 함수의 이름도 이 영어의 약자를 따와서 만든 것 같습니다.

 

밑의 링크는 약수, 최대공약수에 대한 위키백과 링크입니다.

약수 - 위키백과, 우리 모두의 백과사전

최대공약수 - 위키백과, 우리 모두의 백과사전

 

 

 

2. gcd 함수

2-1. 사용법과 결과

gcd 함수의 사용법은 다음과 같습니다.

 

gcd 함수를 호출하기 전, 맨 상단에 import math나 from math import gcd를 선언해

math 모듈을 먼저 호출해야 gcd 함수를 사용할 수 있습니다.

import 구문을 어떻게 사용하는가에 따라 gcd 함수 앞에 math.를 붙이거나 안 붙여서 사용합니다.

 

• math.gcd('정수1', '정수2', '정수3', ... '정수n')

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
import math

print("math.gcd 함수 사용:", math.gcd(10, 100))

import math 사용

 

• gcd('정수1', '정수2', '정수3', ... '정수n')

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("gcd 함수 사용:", gcd(10, 100))

from math import gcd 사용

 

코드를 실행시키면 매개변수에 넣은 숫자들의 최대공약수를 반환합니다.

 

참고로 인자가 1개이거나 3개 이상인 경우, 밑의 사진과 같이

인자의 개수가 맞지 않다는 TypeError 오류가 뜬다면 3.9 이상 버전의 파이썬이 아니기 때문입니다.

저도 사용하던 파이썬 버전이 3.8이었는데 gcd 함수를 사용하기 위해 3.9 버전으로 업그레이드했습니다.

012

파이썬 3.9 버전이 미만일 때, gcd 함수에 인자가 2개 아난 경우 발생하는 오류

 

 

 

2-2. 주의점

매개변수가 2개인 gcd 함수는 3.5 버전에서 추가되었지만,

매개변수가 1개 혹은 3개 이상인 gcd 함수는 3.9 버전에서 업데이트되었습니다.

이 글을 포스팅하는 2021.06.17에는 코딩 테스트 같은 시험에서

매개변수 2개가 아닌 경우의 gcd 함수가 제대로 반영되어 있는지 모르겠습니다.

백준에서는 gcd 함수를 사용해도 괜찮았습니다.

 

gcd 함수를 사용할 수 있다면 최대공약수를 구하는 문제는 매우 쉽게 풀 수 있겠지만,

gcd 함수를 사용 못하는 환경인 경우도 생각해

유클리드 호제법을 직접 구현하여 최대공약수를 구하는 방법도 까먹으면 안 될 것입니다.

 

파이썬에서 유클리드 호제법을 직접 구현해서 최대공약수와 최소공배수를 구하는 방법은 따로 포스팅하겠습니다.

 

 

 

 

 

 

 

 

2-3. 공식 문서

밑의 링크는 파이썬 math 모듈에 대한 파이썬 공식 문서 페이지입니다.

여기서 gcd 함수에 대한 공식 문서 내용을 찾을 수 있습니다.

math — 수학 함수 — Python 3.9.5 문서

 

파이썬 공식 문서의 내용을 보면 위에서 한 번 말했듯이, gcd 함수는 3.5 버전에 추가되었다고 합니다.

다만, 3.9 미만 버전에서는 위의 오류가 발생하는 예제와 같이 gcd 함수의 인자에 정수 딱 2개만 넣을 수 있었습니다.

3.9 버전부터 인수의 개수를 2개 외의 형태로도 사용 가능해졌다고 공식 문서에도 나와있습니다.

 

 

 

2-4. 실행 결과

2-4-1. 매개변수의 개수가 다른 경우

2-4-1-1. 매개변수에 아무것도 넣지 않은 경우

gcd 함수의 매개변수에 아무것도 넣지 않으면 0을 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 아무것도 넣지 않은 경우:", gcd())

gcd 함수의 매개변수에 아무것도 넣지 않은 경우

 

2-4-1-2. 매개변수가 1개일 때

gcd 함수의 매개변수가 1개라면, 그 숫자 그대로 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 1 하나만 넣은 경우:", gcd(1))
print("매개변수에 2 하나만 넣은 경우:", gcd(2))
print("매개변수에 100 하나만 넣은 경우:", gcd(100))
print("매개변수에 98765 하나만 넣은 경우:", gcd(98765))

gcd 함수에 매개변수를 1개 넣은 경우

 

2-4-1-3. 매개변수가 2개일 때

gcd 함수의 매개변수가 2개라면, 매개변수에 넣은 두 숫자의 최대공약수를 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 1, 2로 2개를 넣은 경우:", gcd(1, 2))
print("매개변수에 8, 4로 2개를 넣은 경우:", gcd(8, 4))
print("매개변수에 9, 6으로 2개를 넣은 경우:", gcd(9, 6))
print("매개변수에 13, 7로 2개를 넣은 경우:", gcd(13, 7))
print("매개변수에 98765, 432로 2개를 넣은 경우:", gcd(98765, 432))

gcd 함수에 매개변수를 2개 넣은 경우

 

2-4-1-4. 매개변수가 3개 이상일 때

gcd 함수의 매개변수가 3개 이상일 때, 매개변수를 2개 넣은 것처럼

매개변수에 넣은 숫자들의 최대공약수를 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 1, 2, 3으로 3개를 넣은 경우:", gcd(1, 2, 3))
print("매개변수에 8, 4, 16으로 3개를 넣은 경우:", gcd(8, 4, 16))
print("매개변수에 9, 6, 54, 108로 4개를 넣은 경우:", gcd(9, 6, 54, 108))
print("매개변수에 13, 7, 9, 5, 17로 5개를 넣은 경우:", gcd(13, 7, 9, 5, 17))

gcd 함수에 매개변수를 3, 4, 5개 넣은 경우

 

 

 

 

 

 

 

 

2-4-2. 매개변수에 여러 형태의 숫자, 자료형을 넣은 경우

2-4-2-1. 매개변수에 0을 넣은 경우

gcd 함수의 매개변수에 0 하나만 넣으면 0을 그대로 반환합니다.

gcd 함수의 매개변수에 0과 다른 숫자들을 넣으면 0 외의 다른 숫자들의 최대공약수를 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 0으로 1개를 넣은 경우:", gcd(0))
print("매개변수에 0, 1로 2개를 넣은 경우:", gcd(0, 1))
print("매개변수에 0, 2, 4로 3개를 넣은 경우:", gcd(0, 2, 4))
print("매개변수에 0, 4, 8, 16으로 4개를 넣은 경우:", gcd(0, 4, 8, 16))

gcd 함수의 매개변수에 0을 넣은 경우

 

2-4-2-2. 매개변수에 음수인 정수를 넣은 경우

gcd 함수의 매개변수에 음수인 정수를 넣으면 그 음수인 정수들을 모두 양수로 판단하고 

매개변수에 넣은 숫자들의 최대공약수를 반환합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 -1로 1개를 넣은 경우:", gcd(-1))
print("매개변수에 -2, -4로 2개를 넣은 경우:", gcd(-2, -4))
print("매개변수에 2, -4, 8로 3개를 넣은 경우:", gcd(2, -4, 8))
print("매개변수에 -4, 8, -16, 32로 4개를 넣은 경우:", gcd(-4, 8, -16, 32))

gcd 함수의 매개변수에 음수인 정수를 넣은 경우

 

2-4-2-3. 매개변수에 실수를 넣은 경우

gcd 함수의 매개변수에 실수를 넣으면 실수는 정수로 해석될 수 없다는 TypeError 오류가 발생합니다.

밑의 예제처럼 3, 6과 실제로는 같은 값 3.0, 6.0인 float 자료형을 넣는다고 하더라도 TypeError 오류가 발생합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 3.0, 6.0으로 2개를 넣은 경우:", gcd(3.0, 6.0))

gcd 함수의 매개변수에 실수를 넣은 경우

 

2-4-2-4. 매개변수에 숫자 외의 자료형을 넣은 경우

혹시나 정수들의 리스트를 gcd 함수의 매개변수에 넣으면 최대공약수가 반환될까 생각할 수도 있습니다.

하지만, 역시나 gcd 함수의 매개변수에는 int형인 숫자만 들어올 수 있습니다.

밑의 예제와 같이 리스트를 매개변수에 넣으면 리스트는 정수로 해석될 수 없다는 TypeError 오류가 발생합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 [3, 9]로 리스트를 넣은 경우:", gcd([3, 9]))

gcd 함수의 매개변수에 리스트를 넣은 경우

 

튜플도 마찬가지로 튜플은 정수로 해석될 수 없다는 TypeError 오류가 발생합니다.

# gcd 함수를 사용하기 위해 math 모듈을 import합니다.
from math import gcd

print("매개변수에 (3, 9)로 튜플을 넣은 경우:", gcd((3, 9)))

gcd 함수의 매개변수에 튜플을 넣은 경우

 

 

 

※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.