[Baekjoon] 1934번: 최소공배수

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

1934번: 최소공배수

 

관련 개념을 고등학교 1학년 과정에서 아마 배웠던 것으로 기억하는데, 요새 수학 교육과정은 어떻게 되는지 잘 모르겠다. 본인은 이 개념을 처음 배웠을 때 도대체 왜 이렇게 최대공약수를 구해야하는가에 대한 의문이 풀리지 않았었는데 대학교를 입학해서 수치해석 과목 시간에 이를 revisiting 하면서 이 알고리즘이 왜 필요한지를 깨달았던 기억이 있다.

 

나는 여태 살아오면서 수학을 전공한 것이 평소에도 논리적으로 사고하려는 습관(뭐든 논리적으로 설명하지 않으면 입 안에 가시가 돋는 병, '이과 망했으면'의 주범)을 가지게 되었다는 것을 제외하면 솔직하게 인생에 있어서는 하등 도움이 안 된다고 생각하고 있었는데 프로그래머를 지망하고 있는 지금, 특히나 게임 엔진 프로그래머를 지망하면서 공부하는 동안 내가 운 좋게도 수학을 전공했었다는 사실이 큰 도움이 되고 있다는 것을 많이 느낀다. 프로그래밍에 있어서 수리논리적 사고를 펼칠 수 있다는 것은 프로그래머의 인생에 있어서 정말 많은 도움이 된다고 느끼고 있는데 교육과정이 발전해서 학생들이 좀 더 이런 수학을 재미있게 배우고, 활용할 수 있는 계기를 많이 느껴 재미를 붙이도록 가르쳐줄 수 있다면 전국의 수포자들의 수가 크게 줄어들 수도 있지 않을까 하는 생각을 해본다(남녀노소 요새는 다들 게임 좋아하니까...).

 

---

 

문제 해결 과정

 

착안

두 수 \(A, B\)의 최소공배수(least common multiplier, LCM)는 $$LCM(A, B) = A × B / GCD(A, B)$$이다(\(GCD(A, B)\)는 \(A\)와 \(B\)의 최대공약수(greatest common divisor, GCD)). 따라서, 주어진 두 수의 최대공약수를 빠르게 구할 수 있는 알고리즘이 있다면 두 수를 굳이 소인수분해(prime factorization)하지 않고도 최소공배수를 간단하게 구할 수 있다.

 

구현

주어진 두 수 \(A, B\)의 최대공약수를 구하기 위해 유클리드 호제법(Euclidean algorithm)을 사용하였다.

* 참고) 유클리드 호제법의 증명은 귀류법을 통해 간단하게(사실 증명은 간단한 편인데, 가끔가다 심심해서 증명하려 해보면 은근 좀 헷갈리기는 한다. 일상 프로그래밍에서 그렇게까지 최대공약수를 자주 구해볼 일이 없어서 더 기억에서 빨리 사라지는 것 같기도) 증명할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
	return b ? GCD(b, a % b) : a;
}

int main()
{
	int T, A, B;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%d %d", &A, &B);
		printf("%d\n", A * B / GCD(A, B));
	}

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

위에서 유클리드 호제법을 통해 최대공약수를 구하는 함수 (함수 원형: int GCD(int a, int b);)를 재귀 호출을 이용한 숏코딩으로 구현하였으나, 사실은 재귀를 하지 않고 그냥 한 번의 함수 호출 안에서 반복문을 통해 구현하는 것이 더 바람직하다(아래 코드 참고). 재귀 호출의 경우 함수 호출 시마다 계속해서 스택이 쌓이기 때문이다. 숏코딩은 그냥 유흥으로만 즐겨야지 별로 좋은 습관은 아닌 것 같다(남들이 알아보기에도 힘들다, 이는 협업을 하는 프로그래머에게는 생각보다 아주 중요한 덕목이 될 수도 있다).

 

재귀 호출을 하지 않고 유클리드 호제법을 사용하는 예시 코드:

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

int GCD(int a, int b)
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}