자료구조
유클리드 호제법(Euclidean algorithm)
굽이굽이
2022. 2. 24. 10:19
Summary
- 유클리드 호제법은 최대공약수(Greatest Common Divisor)를 구하는 알고리즘이다.
- '호제'의 뜻은 '서로 호'(互)와 '덜 제'(除)의 조합으로 서로 빼는 과정을 반복해서 최대공약수를 구하겠다는 뜻이다.
- 이때, 큰 수에서 작은 수를 빼야 한다.(최대공약수는 양수여야만 하니까)
HOW 1.
※ 12와 8의 최대공약수를 유클리드 호제법으로 구하는 순서 :
1️⃣ 12와 8 두 가지 숫자가 있음
2️⃣ 12에서 8을 빼면 4가 나옴
3️⃣ 12에서 8을 뺀 결과인 4가 12를 대체함
4️⃣ 그러면, 이제 8과 4 두 가지 숫자가 있음
5️⃣ 8에서 4를 빼면 4가 나옴
6️⃣ 그러면, 이제 8에서 4를 뺀 4가 8을 대체함
7️⃣ 같은 숫자 4 가 두개 남았음, 이때는 4에서 다른 4빼서 0으로 만듦
8️⃣ 한 쪽이 0이 됐을 때 남은 수가 최대공약수가 됨
HOW 2.
※파이썬 코드로 구현 :
1️⃣ 12를 8로 나누었을 때, 나머지가 0이면 8을 반환한다
2️⃣ 그런데 나머지가 0아니니까 네번째줄이 실행되어 8, 4를 파라미터로 전달한다.
3️⃣ 그러면, 두번째줄에서 다시 8을 4로 나눈 나머지가 0이니까 4를 반환하면서 종료된다.
