유클리드 알고리즘

유클리드 알고리즘 ?

: 입력한 두수의 최대공약수(gcd)를 구하는 알고리즘

 

유클리드 알고리즘 풀이법?

(a=15 , b=10 - 큰수가 a에 입력될 때)

 

1. 큰수에서 작은수 나누기

2. 다음 나눠줄 큰수 자리에 작은 수 넣어주기 (a가10이 됨)

3. 다음 나눠줄 작은수 자리에 (1)에서의 나머지값 넣어주기 (b가 5가됨)

4. b가 0이 될때까지 계속 반복

 

코드 작성하기

*순서 기억하기*