728x90
유클리드 호제법
: 두 자연수 A,B에 대하여 A를 B로 나눈 나머지를 R
이때 A,B의 최대공약수는 B와 R의 최대공약수와 같다.
대표적인 예제 : 두개의 자연수에 대한 최대공약수를 구하는 문제
(유클리드 호제법과 재귀함수* 이용)
def gcd(a,b):
if a%b == 0:
return b
else :
return gcd(b, a%b)
print(gcd(192,162))
* 재귀함수 -> 자기자신을 다시 호출하는 함수
종료조건을 반드시 명시하여 무한히 호출되지 않도록 해야함.
>> DFS 알고리즘에서 자주 사용된다.
'알고리즘 (JAVA)' 카테고리의 다른 글
| [python] 코딩테스트를 위한 파이썬 문법 정리 - 개발자 배찌 (0) | 2022.11.27 |
|---|---|
| [코테준비 python] - 이진탐색 알고리즘 - 개발자 배찌 (0) | 2022.11.10 |
| [코테준비 python] 스택, 큐 자료구조 - 개발자 배찌 (0) | 2022.11.03 |
| [코테준비 python] 그리디알고리즘, 구현 알고리즘 - 개발자 배찌 (0) | 2022.11.02 |
| [프로그래머스] level1.완주하지 못한 선수 - 개발자 배찌 (0) | 2022.06.08 |