# GCD
# GCD : Greatest common divisor : 최대공약수
# 유클리드 호제법
# : a,b에 대해 a를 로 나눈 나머지를 r이라 하면
# a,b의 최대 공약수는 b와 r의 최대 공약수와 같다.
# a b
# 192 162
# 162 30
# 30 12
# 12 6 >> 최대 공약수 6
def gcd(a, b):
print("---" + str(a) + ", " + str(b))
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
'Algorithm' 카테고리의 다른 글
[1028알고리즘 FROM 동빈나 21]그래프 탐색 : DFS vs BFS (0) | 2021.04.13 |
---|---|
[1028알고리즘 20]Dynamic Programming (0) | 2021.04.10 |
[1028알고리즘 19]해쉬 (0) | 2021.04.10 |
[1028알고리즘 18]정렬 (0) | 2021.04.10 |
[1028알고리즘 17]재귀함수(Recursive function) (0) | 2021.04.10 |