유클리드 호제법

백준 https://www.acmicpc.net/problem/1934

를 유클리드 호제법으로 풀던 와중 코드를 잘 썼다고 생각했는데 정상작동하지 않았습니다.

그래서 유클리드 호제법에 대해 다시 정리하며 제가 실수한 부분을 다시 살펴보려 합니다.

 

두 정수 a, b의 최소공배수(LCM)를 구하려면 보통 최대공약수(GCD)를 먼저 구한 뒤
LCM(a, b) = a × b / GCD(a, b) 공식을 씁니다.
이때 핵심이 되는 게 유클리드 호제법이고, 재귀식은 다음 한 줄로 요약됩니다.

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

 

유클리드 호제법의 이론

1.큰 수를 작은 수로 나누는 MOD 연산을 수행한다.

2.앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다.

3.2를 반복하며 MOD연산의 결과가 0이 됐을때의 작은수가 최대 공약수다.

 

예를 들어 gcd(1071, 462)라면

 

1. 1071 % 462 = 147 → gcd(1071,462) = gcd(462,147)
2. 462 % 147 = 21 → gcd(462,147) = gcd(147,21)
3. 147 % 21 = 0 → gcd(147,21) = gcd(21,0)
   따라서 gcd = 21

아 큰 수를 작은 수로 나누는 mod연산이니까 큰 수 작은 수의 순서를 맞출 필요가 있겠구나! 라고 생각해서 다음과 같이 문제를 풀었습니다.

 

#include <iostream>

using namespace std;

int gcd(int a, int b)

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;

		int result = a * b / gcd(a, b);
		cout << result << "\n";
	}


	return 0;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	else {
		return gcd(a, b % a);
	}
}

 

문제의 예제 입력을 보면 큰수가 항상 뒤에 고정되어 있어 나중에 입력받는 b를 앞에두고 %연산을 하고 더 작은 a를 두어
gcd(a, b % a); 라고 써놨는데 이게 문제가 되었습니다.

 

왜 문제가 되었나

• 내가 쓴 재귀식은 gcd(a, b%a)였다. 유클리드 호제법의 정의식은 a = q·b + r     (r = a%b, q=a/b) 이고, 여기서 gcd(a, b) = gcd(b, r) = gcd(b, a%b)가 된다. 즉 나머지는 항상 “앞의 수를 뒤의 수로 나눈 값”이어야 한다.
• gcd(a, b%a)는 이 정의를 어겨서 두 가지 문제가 생긴다.
  1. a > b일 때 무한 반복에 빠질 수 있다. 예: a=6, b=4
     gcd(6, 4%6=4) = gcd(6,4)로 자기 자신을 다시 호출 → 종료 조건에 도달하지 못함.
  2. a < b일 때는 우연히 맞는 경우가 있지만 일반적으로 올바른 수렴 보장이 없다.

핵심 오해 바로잡기

• “항상 큰 수를 작은 수로 나눠야 한다”가 아니라, “항상 첫 번째 인자를 두 번째 인자로 나눈 나머지”를 써야 한다.
• 코드에서 굳이 큰수/작은수를 미리 맞출 필요가 없다. 유클리드 호제법은 한 번의 호출로 자연스럽게 자리 정리가 된다.
  • a ≥ b면 a%b < b이므로 값이 바로 줄어든다.
  • a < b면 a%b = a가 되어 다음 호출이 gcd(b, a)로 “자리 바꿈”이 일어나고, 그다음부터 정상적으로 감소한다.

간단 반례로 보는 잘못된 변형들

• 잘못된 식 1: gcd(a, b) → gcd(a, b%a)
  a=6, b=4 → gcd(6,4%6=4) = gcd(6,4) 반복 → 무한 루프 위험
• 잘못된 식 2: gcd(a, b) → gcd(b, b%a)
  a=1, b=2 → gcd(1,2) → gcd(2, 2%1=0) = 2 (오답, 실제 gcd는 1)

바른 재귀식과 직관

• 바른 식: gcd(a, b) → gcd(b, a%b)
• 직관: a와 b의 공약수 집합은 b와 r(a%b)의 공약수 집합과 동일하다. a에서 b의 배수를 뺀 나머지 r은, 공약수 구조를 그대로 유지한다.

정답 코드

#include <iostream>

using namespace std;

int gcd(int a, int b);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;

		int result = a * b / gcd(a, b);
		cout << result << "\n";
	}


	return 0;
}

int gcd(int a, int b) {
	if (b == 0) return a;
	else {
		return gcd(b, a%b);
	}
}

 

gcd에 들어가는 인자를 바꾸니 정상작동한다.