[TIL] 7. 8월 알고리즘(유클리드 호제법)

알고리즘 수업때 배웠던 유클리드 호제법에 대해서 정리해보려고 한다.

 

🧐최대공약수 구하기

두 수의 최대공약수를 구하는 방법은 여러가지가 존재한다

 

가장 단순한 방법으로 이렇게 최대 공약수를 구할 수 있다.

brute force 방법으로 계산

하지만 이 코드에는 단점이 존재한다 숫자가 커지면 그 만큼 연산횟수도 커지기 때문에 성능측에도 문제가 발생한다.

✅좀 더 효율적으로( 유클리드 호제법 이용하기)

이때 유클리드 호제법을 사용하면 좀 더 효율적으로 계산을 처리할 수 있다.

유클리드 호제법은 코딩 테스트 문제를 풀 때도 유용하게 사용되므로 알아두면 좋다.

 

유클리드 호제법은 두 수를 서로 나누어 나머지가 0이 될 때까지 반복하며, 마지막으로 나눈 수가 최대공약수가 된다.

a 를 b로 나눈 나머지를 r 이라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다

 

그림으로 확인해보자

 

60과 24의 최대공약수를 구하는 과정을 60x24 크기의 직사각형을 가장 큰 정사각형 타일로 빈틈없이 채운다고 생각해보자

1. 가장 큰 정사각형 후보인 24x24로 채워보자, 60 % 24의 몫이 2므로 타일 두 개가 들어가고 12x24크기의 공간이 남는다.
2. 정답이 되려면 저 빈칸마저 완벽히 채워야한다.
3. 여기서 핵심은 60x24를 채울 수 있는 타일은 당연히 남아있는 24x12 공간을 모두 완벽하게 채울 수 있어야만 한다.
   따라서 gcd(60, 24)를 푸는 문제는 gcd(24, 12)를 푸는 문제와 본질적으로 같아진다. 이것이 유클리드 호제법의 핵심이다.
4. 크기를 줄여서 (24, 12) 크기를 채울 수 있는 정사각형을 찾는 방법으로 시도하자,
   이 공간은 12x12로 완벽히 채워진다(나머지 0)
5. 이렇게 나머지가 0이 되는 순간, 마지막에 사용된 타일의 길이 즉 12가 최대 공약수가 된다.

코드로 알아보자

1. 두 수 중 가장 큰 수를 작은 수로 나눈다.

2. 이 때 나머지가 0이라면 작은 수가 최대 공약수이다.

3. 아니라면 작은 수가 다음 단계의 큰 수가 되고 나머지는 다음 단계의 작은 수가 된다 그리고 1단계 부터 다시 반복한다

 

예를 들어 gcd(60, 48) 일 때를 확인해보자

 

1. 첫 번째 반복

int gcd(int a, int b) {
	while (b > 0) { // while(b > 0) : 48 > 0 이므로 true이다
		int temp = b; // temp에 b값인 48을 저장
		b = a % b; // b 는 60 % 48의 결과인 12 를 저장한다
        a = temp; // a는 temp 값을 저장한다.
	} // 첫 번째 반복이 끝나면 a = 48, b = 12가 된다.
	return a;
}

 

2. 두 번째 반복

int gcd(int a, int b) { 
	while (b > 0) { // while(b > 0) : b는 12이므로 계속 진행한다
		int temp = b; // temp에 b값인 12를 저장
		b = a % b; // b 는 48 % 12의 결과인 0을 저장한다
        a = temp; // a는 temp 값을 저장한다.
	} // 첫 번째 반복이 끝나면 a = 12, b = 0 이 된다.
	return a;
}

 

3. 반복 종료

int gcd(int a, int b) { 
	while (b > 0) { // b = 0이기 때문에 while문의 조건을 만족하지 않는다. (건너뜀)
		int temp = b;
		b = a % b;
        a = temp; 
	} 
	return a; // 최종적으로 a값인 12가 반환된다
}

 

그래서 60과 48의 최대공약수는 12임을 알 수 있다.

 

일반 연산과 유클리드 호제법의 성능은 어떠한 차이를 보일까?

출처: https://www.bigocheatsheet.com/

일반 연산의 경우 O(n)의 시간복잡도를 가진다 반면 유클리드 호제법은 O(log n)의 시간 복잡도를 가진다 둘의 간격이 점점 벌어지는 것을 확인할 수 있다.

 

😎 더 알아보기

유클리드 호제법은 최소공배수도 효율적으로 구할 수 있다.

최소공배수를 구하는 lcm(a, b)는 lcm(a, b) = (a * b) / gcd(a, b) 와 같다 라는 점을 기억하면 쉽게 최소공배수도 구할 수 있다.

 

🧐어떻게 성립하나?

최대공약수와 최소공배수의 관계

조합으로 표현해보자 서로 겹치는 부분을 G라고 할 때, 원 a는 2 x 3 x G 이고 원 b는 5 x G 라고 표현할 수 있다.

이때 겹치는 부분은 최대공약수, 전체영역을 최소공배수라고 할 수 있다.

그래서 lcm = (a x b) / gcd 가 성립하는 이유는,  a x b는 (a x g) x (b x g) 즉 a x b x g x g로 표현되고 gcd는 g 이므로

(a x b x g x g) / g 이다. 그래서 lcm = a x b x g가 성립된다.