🔗 최대공약수(GCD) & 유클리드 호제법

최대공약수(GCD)는 두 수 이상의 공통 약수 중 가장 큰 값입니다.

• 여러 수를 모두 나눌 수 있는 가장 큰 수

🧐 예시

24, 18, 12의 공통으로 나눌 수 있는 수는?
공약수: 1, 2, 3, 6
최대공약수: 6

👉 이런 “공통으로 나누는 최대 값”을 찾는 것이 GCD

1️⃣ 사용하는 경우

• 모든 값을 나눌 수 있는 수를 찾을 때

  • 배열 전체를 나누는 값
  • 공통 약수 문제

• 수를 단순화할 때

  • 분수 약분
  • 비율 계산

• 최적화 문제

  • 완전탐색 대신 수학적으로 해결 가능할 때

2️⃣ 핵심 아이디어

🔹 유클리드 호제법

두 수 a, b에 대해:

gcd(a, b) = gcd(b, a % b)

🔹 반복 규칙

(a, b) → (b, a % b)

👉 나머지가 0이 될 때까지 반복 👉 그때의 값이 GCD

3️⃣ 동작 예시

🧐 gcd(24, 17)

24 % 18 = 6 → gcd(18, 6) 
18 % 6 = 0 → gcd(6, 0)

// 결과: 6

여러 수의 GCD는 이렇게 구할 수 있습니다.

gcd(a, b, c) = gcd(gcd(a, b), c)

👉 하나씩 누적 계산

4️⃣ 기본 구현

🔹 gcd

function gcd(a, b) { 
	while (b !== 0) { 
		let temp = b; 
		b = a % b; 
		a = temp; 
	} 
	return a; 
}

🔹 배열 GCD

function getGDC(arr) {
	let result = arr[0];

	for (let i = 1; i < arr.length; i++) {
		let b = arr[i];

		while(b !== 0) {
			let temp = b;
			b = result % b;
			result = temp;
		}
	}
	return result;
}

5️⃣ 전체 흐름 예제

const arr = [24, 18, 12]; 
getGCD(arr);

🔄 계산 과정

• gcd(24, 18) → 6
• gcd(6, 12) → 6

👉 최종 결과: 6

✍️ 한 줄 정리

GCD는 여러 수를 모두 나누는 가장 큰 값이며, 유클리드 호제법을 통해 나머지 연산으로 빠르게 구할 수 있습니다.