유클리드 알고리즘 정의

유클리드 알고리즘은 내가 백준 알고리즘을 공부하면서 알게 되었다. 코드 구현을 할때 수학적 명제 알고리즘을 알고있다는 것은 엄청난 도움이 된다고 생각해 공부를 해보고 포스팅 하게 되었다.

밑에는 유클리드 알고리즘을 만난 문제이다.

백준 알고리즘 2609번(유클리드 알고리즘)

---

유클리드 알고리즘(유클리드 호제법)

유클리드 알고리즘은 두 정수 사이의 최대 공약수(GCD)를 찾는 방법입니다.
유클리드 알고리즘은 a를 b로 나눈 나머지가 r이면 a와 b의 GCD는 b와 r의 GCD가 같다는 사실을 이용한 반복 과정입니다. 이 과정은 r이 0이 될 때까지 반복되며, 이 시점에서 a와 b의 GCD를 찾을 수있습니다.

우리는 이미 초등학교때 최대공약수를 구하는 방법을 배웠습니다. 예를들어 18과 24의 최대공약수는 6이라는 것을 알수있죠.

그렇다면 왜 GCD라는 알고리즘을 배워야 할까요? 그건바로 엄청나게 큰 두 수의 최대공약수를 구하기 위해서입니다. 

123456789과 987654321의 최대공약수를 구하라고하면 쉽지 않을것입니다 하지만 GCD를 사용한다면 아주 쉽게 구할 수있죠

글로쓰면 이해하기 어려워서 그림판을 사용하여 설명을 하겠습니다.

GCD는 최대공약수의 영어표현을 줄인 말이고 a=qb+r에서 q는 몫,r은 나머지를 뜻합니다.

---

유클리드 알고리즘을 사용하는 방법

1.GCD를 찾고자 하는 두 정수를 적는다.

2.큰 수를 작은 수로 나누고 나머지를 적는다.

3.나머지가 0이면 GCD는 더 작은 숫자이다. (예를들어 a가 6이고 b가 3이면 a와 b의 GCD는 3이된다)

4.나머지가 0이 아니면 더 작은 수를 나머지로 나누고 새 나머지를 기록한다.

5.나머지가 0이 될 때까지 3단계와 4단계를 반복한다.

6.GCD는 0이 아닌 마지막 나머지이다.

 

---

유클리드 알고리즘의 예

예제 문제: 18과 30의 GCD를 찾아보아라.


18과 30의 두 정수를 적는다.

큰 수(30)를 작은 수(18)로 나누고 나머지(12)를 적는다.

더 작은 숫자(18)를 나머지(12)로 나누고 새 나머지(6)를 기록한다.

더 작은 숫자(12)를 나머지(6)로 나누고 새 나머지(0)를 기록한다.

GCD는 0이 아닌 마지막 나머지인 6이된다. 따라서 18과 30의 GCD는 6이 나옵니다. 

따라서 유클리드 알고리즘을 사용하면 123456789과 987654321의 GCD를 충분히 구할 수있는 것이죠?

이떄 GCD(6 0)은 무엇인가에 대한 물음이 있을 수있는데 그건 제가 유클리드 알고리즘을 공부하기 위해 참고한 유튜브 영상에 잘 나와있으니 궁금하다면 보는걸 추천드려요

결론

결론적으로 유클리드 알고리즘은 두 정수 사이의 최대 공약수를 찾는 강력한 도구입니다. 사용이 간편하고 다양한 문제에 적용할 수 있는 반복 프로세스입니다. 유클리드 알고리즘을 이해하는 것은 암호화, 컴퓨터 과학 또는 일반적으로 수학에 관심이 있는 모든 사람에게 필수적입니다. 이 안내서에 설명된 단계를 따르면 Euclid 알고리즘을 쉽게 사용하여 문제를 해결하고 많은 응용 프로그램을 발견할 수 있습니다.