📒유클리드 호제법

최대공약수를 구하는 방법으로는 유클리드 호제법이라는 간단한 방법이 있다.
간단한 수라면 눈으로 풀거나 암산이 빠르겠지만, 그 수가 커지면 암산은 힘들고 우리에게는 간단한 알고리즘이 필요하다.

📌정의

두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 알고리즘

즉 a>b에 대하여 a%b는 r이고 a와 b의 최대공약수는 b와 r의 최대공약수다.

정의만으로 이해가 되지 않는 유클리드 호제법(gcb)! 이해를 도와주는 예시가 있다.

a=18 b=12
18 % 12 = 6
12 % 6 =0
➡18과 12의 최대공약수는 6이다.

📌증명

a와 b는 a>b인 자연수이다. m은 몫 r은 0이 아닌 나머지다.
a는 아래의 식으로 표현할 수 있다.
a = b*m + r 여기서 b는 새로운 a가 되고 r은 새로운 b가 된다.
b = r*m2 + r2
r = r2*m3 + r3
	  .
	  .
	  .
r(n-1) = rn*m(n+1) + 0
위의 식을 아래의 식으로 대체한다면 아래와 같이 된다.
a = b*m + r 	= m * (r*m2 + r2) + r = r(m*m2 + 1) + m*r2
b = r*m2 + r2	= m2 * (r2*m3 + r3) + r2 = r2 * (m2*m3 + 1) + m2*r3
r = r2*m3 + r3
	  .
	  .
	  .			= mn * rn*m(n+1) + rn = rn(mn * m(n+1) + n)
r(n-1) = rn*m(n+1) + 0
따라서 rn이 최대공약수다.

📌구현

위의 유클리드 호제법을 사용해 최대공약수를 구하는 코드를 c++을 통해 구현했다.

int gcd (int a, int b)
{
	int c;
    while(b!=0)
    {
    	c = a % b;
        a = b;
        b = c;
  	}
    return a;
}

✍최대공약수를 활용한 최소공배수

최대공약수를 구했다면 최소공배수를 구하는 것은 정말 쉽다.
두 수를 곱하고 그 값을 최대공약수로 나누 값 == 최소공배수다

📌구현

int lcm (int a, int b)
{
	return (a * b) / gcd(a, b);
}

유클리드 호제법과 간단한 수학적 공식을 통해 프로그래머스 LV2 최소공약수 문제를 쉽게 풀 수 있었다.
그저 간단한 코딩 문제라고 생각할 수 있지만, 깊게 생각한다면
여러가지 공식이나 알고리즘을 알 수 있는 좋은 문제다 :)