유클리드 알고리즘

안녕하세요 .woo0429 입니다.

백준 문제를 풀다가 '유클리드 알고리즘'에 대해 알게 되었습니다.

1. '유클리드 알고리즘'

• 유클리드 알고리즘은 두 수의 최대공약수(GCD)를 구하는 알고리즘 입니다.

2. '유클리즈 알고리즘' 원리

• 두 자연수 a,b가 주어졌다고 가정(a>b)
• a=a%b(a를 b로 나눈 나머지를 다시 b에 대입 )
• b=0 될 때 까지, a에 b를 , b에 a를 대입한 후 a=a%b를 반복합니다.
• b=0 일 때, a가 최대 공약수 입니다.

3. 접근방법

임의의 변수 a,b를 입력 받고 최대공약수를 출력하는 방식입니다

변수에 5와 30을 넣었을 때 최대공약수 5가 나오게 됩니다.