[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
Python/이코테
2022. 6. 11. 20:30
