[AlgorithmTheory] 알고리즘에서의 최대공약수와 최소공배수

1. 개요

코딩테스트의 기출 문제들을 풀다보면 기초적인 문제로 수학과 관련된 문제들이 많습니다. 특히 소수와 함께 최대공약수 및 최소공배수 문제가 많이 등장합니다. 요즘은 모르겠지만 저는 어린시절 수학을 배우면 수학의 이론 및 정의에 대해서 모두 알고 배운 것이 아니라 단순히 문제를 빨리 풀기 위한 것들만 외우는 주입식 교육을 받아서 수학적 이론이 굉장히 부족합니다. 특히나 이런 수학 문제들을 코드로 옮기기 위해선 수학적 이론의 개념이 필요합니다만 저는 이론이 부족하여 최대공약수나 최소공배수 문제를 처음 만났을 때 어떻게 코드로 옮겨야 하지 하며 가장 기초적인 문제임에도 막혔던 기억이 있습니다.

이번 알고리즘에서의 최대공약수 및 최소공배수 포스트 작성은 추후에도 취업을 위한 코딩테스트를 재학습 할 때 빠르게 학습할 수 있도록 하기 위함과 개인적으로 공부를 하고 이를 정리하면서 한 번더 학습을 하기 위한 차원으로 작성을 하게 되었습니다.

2. 최대공약수

공약수란? 두 개 이상의 자연수에서 공통으로 가지는 약수를 말하며, 최대공약수는 이 공약수들 중에서 가장 큰 수를 의미합니다. 예를 들어 4와 6의 공약수와 최대공약수를 구해보도록 하겠습니다.

두 수 4와 6의 약수는 4 = [1, 2, 4], 6 = [1, 2, 3, 6]와 같으며, 여기서 공약수는 [1, 2]입니다. 이 중 가장 큰 약수인 최대공약수는 2입니다.

2.1 최대공약수를 구하기 위한 유클리드 호제법

최대공약수를 구하기 위한 방법은 여러가지가 있습니다. 우리는 보통 초등과정에서 두 수의 소인수분해를 진행하면서 약수를 구하고 공약수들 중에서 가장 큰 수를 고르는 방식으로 배웁니다. 하지만 이런 방식으로 코드를 짜면 코딩테스트 문제에서는 시간초과로 인해 오답을 받을 수 있습니다. 따라서 이를 위해선 최대공약수를 빠르고 쉽게 구하는 방법을 알아야 합니다.

일반적으로 최대공약수를 구하는 방법은 유클리드 호제법을 주로 사용합니다. 유클리드 호제법(- 互除法, Euclidean Algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘의 하나입니다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타냅니다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다.

이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당합니다.

2.2 코드로 구현한 유클리드 호제법을 이용한 최대공약수 구하기

유클리드 호제법을 보면 재귀적 성질이 있음을 확인할 수 있습니다.

1. a에서 b를 나누어 준다
2. 나머지 값이 0이면 b는 a와 b의 최대공약수이다.
3. a에서 b를 나눈 나머지 값이 0이 아니면 a를 b로, b를 r로 바꾸어준다.
4. b에서 r값을 나누었을 때의 나머지가 0이 될 때까지 반복해 준다.

이를 재귀함수로 구현하면 다음과 같습니다.

def get_gcd(a, b):

    r = a % b

    if r == 0:
        return b

    return get_gcd(b, r)

a = 48
b = 56

print(get_gcd(a, b))

48과 56의 약수들을 구해보면 48 = [1, 2, 3, 4, 6, 8, 12, 16, 24, 48], 56 = [1, 2, 4, 7, 8, 14, 28, 56]가 되며 공약수는 [1, 2, 4, 8]이 됩니다. 이 중 가장 큰 값이 최대공약수는 8이고, 출력값을 보면 8이 출력되는 것을 확인할 수 있습니다.

Output:
8

여기서 재귀함수를 쓰지않고 좀 더 간단히 구현하는 방법이 있습니다. 코드는 다음과 같습니다.

def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

a = 48
b = 56

print(get_gcd(a, b))

2.3 최대공약수를 이용한 문제를 풀 때의 주의할점

유클리드 호제법을 보면 a>b여야만 작동하는지 의문이 들 수 있습니다. 하지만 a<b이더라도 두 함수 모두다 첫 루프에서 자동으로 두 수가 바뀌게 되므로 굳이 정렬을 할 필요가 없습니다. 간혹 기초적인 문제가 출제가 되지만 정렬을 진행해서 시간초과가 발생하도록 함정을 심어놓은 문제들이 출제가 될 수 있기 때문에 이러한 점을 기억해 두시면 될 것 같습니다.

2.4 N개 수에 대한 확장

두 수가 아니라 여러 개(3개 이상)의 수에 대한 GCD와 LCM을 구하라는 응용 패턴이 자주 출제됩니다. 핵심 아이디어는 앞선 두 수의 최대공약수를 구한 결과값과 다음 수의 최대공약수를 누적해서 구하면 됩니다. 코드는 다음과 같습니다.

def get_gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

num_list = [2, 8, 10]

gcd_value = num_list[0]

for i in range(1, len(num_list)):
    gcd_value = get_gcd(num_list[i], gcd_value)

print(gcd_value)

3. 최소공배수

공배수는 두 개 이상의 자연수에서 공통으로 가지는 배수를 말하며, 최소공배수는 이 공배수들 중에서 가장 작은 수를 의미합니다. 예를 들어 4와 6의 공배수와 최소공배수를 살펴보도록 하겠습니다.

4의 배수: 4, 8, 12, 16, 20, 24 … 6의 배수: 6, 12, 18, 24, … 공배수: 12, 24, 36, … 최소공배수: 12

3.1 최소공배수 구하는 방법

두 수의 최소공배수를 구하는 방법은 두 수의 곱셈에서 최대공약수를 나누어주면 최소공배수가 됩니다.

3.2 코드로 구현한 최소공배수 구하기

최소공배수를 구하기 위해선 최대공약수가 필수로 필요합니다. 코드는 다음과 같습니다.

def get_gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

def get_lcm(a, b):
    return (a*b)//get_gcd(a, b)

a = 4
b = 6

print(get_lcm(a, b))

3.3 최소공배수를 구할 때의 주의할 점

보통 최대공약수 및 최소공배수 문제는 입력값의 범위가 0보다 큰 자연수인 경우가 많습니다. 여기서 최소공배수를 구할 때에 두 수의 곱에서 최대공약수를 나눠주게 되는데 이 때 나눗셈으로 인한 부동소수점 문제로 오답을 받는 경우가 있습니다. 이 점만 주의를 한다면 최소공배수 문제에서는 큰 문제가 없을 것입니다.

3.4 N개 수에 대한 확장

최대공약수와 같이 누적된 최소공배수에 새로운 수를 곱해주고 이전에 누적된 최소공배수와 새로운 수의 최대공약수를 나누어주는 식으로 구해주면 됩니다. 코드는 다음과 같습니다.

def get_gcd(a, b):
    while b>0:
        a, b = b, a%b
    return a

num_list = [2, 8, 10]

lcm_value = num_list[0]

for i in range(1, len(num_list)):
    lcm_value = lcm_value * num_list[i] // get_gcd(lcm_value, num_list[i])

print(lcm_value)