[Java] 29. 최대 공약수(GCD)

Feb 07, 2025

[Java] 29. 최대 공약수(GCD)

❗

유클리드 호제법이란?

유클리드 호제법은 나머지를 이용해 최대공약수를 구하는 방법입니다.

아래의 과정을 반복하면 됩니다.

1️⃣ 큰 수를 작은 수로 나눈다.

2️⃣ 나머지를 구한다.

3️⃣ 나머지가 0이면 작은 수가 최대공약수!

4️⃣ 나머지가 0이 아니면, 작은 수를 큰 수로, 나머지를 작은 수로 변경 후 반복

5️⃣ 나머지 연산은 나누는 수가 더 크거나 동일할 때, 나머지가 원래 숫자(피제수)와 같다는 기본 원칙이 있습니다.

❗

정리

✔ 큰 수를 작은 수로 나누고 나머지를 구한다.

✔ 나머지가 0이 될 때까지 반복한다.

✔ 나머지가 0이 되는 순간 작은 수가 최대공약수!

notion image

1. 최대 공약수 알고리즘

2. 과일 공평하게 나누기

Share article

harimmon

RSS·Powered by Inblog