알고리즘 Java

[JAVA] 8. 필수 알고리즘 Ⅲ. 최대공약수(GCD)

Feb 08, 2025

[JAVA] 8. 필수 알고리즘 Ⅲ. 최대공약수(GCD)

Contents

1. 최대공약수 알고리즘 절차적 노가다 코드 반복문과 유클리드 호제법 재귀함수와 유클리드 호제법 배열을 이용하여, 비교하여 처리하시오 2. 과일을 공평하게 나누기 1. 기본문제 2. 심화문제

💡

유클리드 호제법

두 수를 서로 나누는 것, 나머지가 0이 되는 몫이 최대공약수다.

큰 수에서 작은 수를 나눈다.

10과 8이 있다.

10 % 8 = 2

8 % 2 = 0

최대공약수는 2

notion image

시간복잡도

O(logN)

1. 최대공약수 알고리즘

❗

12와 18의 최대공약수를 구하시오!.


12의 약수: 1, 2, 3, 4, 6, 12
18의 약수: 1, 2, 3, 6, 9, 18
공통 약수: 1, 2, 3, 6
최대 공약수 : 6

절차적 노가다 코드

반복문과 유클리드 호제법

재귀함수와 유클리드 호제법

배열을 이용하여, 비교하여 처리하시오

2. 과일을 공평하게 나누기

1. 기본문제


사과 12개를 3명이서 공평하게 나누려면 몇 개씩 나누면 될까?

2. 심화문제


사과 12개 🍎, 바나나 18개 🍌, 귤 24개 🍊을 같은 개수로 최대한 공평하게 나눌 때, 
한 사람당 받을 개수는?

Share article

Contents

1. 최대공약수 알고리즘 절차적 노가다 코드 반복문과 유클리드 호제법 재귀함수와 유클리드 호제법 배열을 이용하여, 비교하여 처리하시오 2. 과일을 공평하게 나누기 1. 기본문제 2. 심화문제