[Python] 그래프 탐색 알고리즘: DFS/BFS_최대공약수(유클리드 호제법)

예제

• 두 개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있습니다.

유클리드 호제법

• 두 자연수  A,B에 대하여 (A, > B) A를 B로 나눈 나머지를 R이라고 합니다.
  • R = A % B
• 이 때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다.
  • GCD(A,B) = GCD(B,R)
• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있습니다.
  • 예시: GCD(192, 162)

계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

 

def GCD(a, b):
    if a % b == 0:
        return b
    return GCD(b, a % b)


print(GCD(192, 162)) # 6