2025.7.25: 유클리드 호제법

jiyongg·2025년 7월 25일

Euclidean algorithm TIL algorithm

TIL: Today I Learned

목록 보기

8/30

오늘은 해커톤 아이디어 회의 준비 때문에 자료 조사 및 문서 정리에 많은 시간을 썼다.

그래서 복잡한 실습을 하기보다는, 유클리드 호제법에 대해 알아 보았다.

🖼️ 배경

때는 올해 초, 멋사에 지원했을 때였다. 우리 학교 멋사에서는 서류 심사 합격자들에게 과제를 내주고 해당 과제를 얼마나 성실히 푸는지를 테스트하는 과정이 있었다.

거기에서 풀이 과정에서 최대공약수를 구해야 하는 문제가 나왔다.

백준 2485번 가로수 문제가 변형된 문제로, 백준 문제의 내용을 기준으로 했을 때 내가 짠 풀이 전략은 아래와 같았다.

가로수의 위치가 모두 정수이므로, 모두 같은 간격에서 그 간격은 첫 가로수와 마지막 가로수 사이의 거리의 약수일 것이다. 또한, 거리 3을 2로 나누어 1.5로 만드는 등의 사례는 불가능하므로 정수인 간격들의 최대공약수일 것이다.
따라서, 첫 가로수와 마지막 가로수 사이의 거리 last_minus_first를 구하고,
각 가로수 사이의 거리 distances를 저장하고, 각 가로수 사이의 거리들의 최대공약수 gcd를 구한다.
그 gcd로 last_minus_first를 나눈다. -> 거리의 개수를 의미한다.
3개의 거리는 4그루의 가로수에서 발생하므로, 결과에 1을 더해야 한다.

당시에 나는 과제를 풀 때, 최대한 계산에 필요한 함수들을 직접 구현하고자 했다. math 모듈의 gcd 함수의 존재는 알고 있었지만, 뭔가 이 함수를 이용해 푸는 것은 뭔가 출제자의 의도에 벗어날 것 같은 느낌이었다.

과제 당시 작성했던 나의 최대공약수 계산 함수는 아래와 같았다.

def gcd(arg):
    start = min(arg)
    
    for i in range(start, 0, -1):
        if all(map(lambda x: not x % i, arg)):
            return i

arg는 최대공약수를 구해야 하는 대상들이다.
그 중에 가장 작은 숫자를 뽑아서, i가 그 숫자에서 시작해서 1까지 내려가며, arg에 있는 숫자들에 대한 나머지 연산의 결과가 모두 0이 나올 때, 그 i를 반환한다.
시간 복잡도를 계산해보자.
- arg의 길이를 n이라고 하자.
- 먼저, 첫번째 줄에서 arg의 최솟값을 구하려면 O(n)이 걸린다.
- for문 내부에서 n번의 나머지 연산이 발생한다. 즉, O(n)이다.
- 이 나머지들을 순회하면서 모두 True인지 확인해야 한다. 이 작업의 시간 복잡도는 O(n)이다.
- for문의 시간 복잡도는 O(min(arg))이다.
- 이 gcd 함수의 시간 복잡도는 O(n) + (O(n) + O(n)) $\times$ O(min(arg)) = O(min(arg) $\times$ n)이다.
- 최악의 경우는 min(arg)가 10억(10 $^9$ )에 가까우면서, n이 10만(10 $^5$ )에 가깝고, arg의 요소들이 모두 서로소, 즉 최대공약수가 1인 경우이다. 이 경우, O(10 $^9$ ) $\times$ O(10 $^5$ ) =O(10 $^{14}$ )가 된다.
- 시간 제한이 1초일 때 O(10 $^8$ )이 넘으면, 그 알고리즘은 통과하지 못한다고 보면 된다. (10 $^8$ = 1억)
  - 참고: A Time Complexity Guide (Codeforces), How many operations per second can my solution be? (Codeforces), [알고리즘] 시간 제한과 시간 복잡도 (Velog)
- 결론적으로 이 알고리즘은 통과하지 못하는 알고리즘이다.

당시 과제를 풀면서도, 이게 맞나? 시간 복잡도 면에서 괜찮은가?라는 생각은 들었지만, 정답을 맞히는 것보다는 성실하게 푸는 것을 중점으로 본다고 하여서 일단 넘어갔다.

그리고 과제 제출 마감 이후에 GPT군에게 물어보니, 최대공약수를 구할 때에는 유클리드 호제법을 쓰면 된다고 하던 것이다!

그래서 한번 알아봐야지 해놓고는 미루고 있었다. 그러던 중, 오늘 유클리드 호제법을 정리하면 괜찮지 않을까 싶어서 유클리드 호제법에 대해 알아보게 되었다.

🔢 유클리드 호제법

알고리즘

유클리드 호제법으로 최대 공약수를 구하는 방법은 다음과 같다.

두 수 a와 b가 있다. (이때, a > b)
a를 b로 나눈 나머지를 r이라고 하자. (r = a $\bmod$ b)
이때, 다음 두가지 경우가 있다.
- r이 0이라면, b는 a와 b의 최대 공약수이다.
- r이 0이 아니라면, a에 b를 대입하고 다시 위의 과정을 진행한다.

굉장히 간단하면서도 시간이 오래 걸리지 않는 알고리즘이다.

파이썬 코드

def calc_gcd(a: int, b: int) -> int:
    """
    두 수의 최대공약수를 유클리드 호제법을 이용해 계산한다.
    """
    # a가 b보다 커야 하므로 a < b라면 a와 b를 교환
    if a < b:
        a, b = b, a
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    
    return b

유클리드 호제법은 a > b라는 조건이 있으므로, a < b라면 a > b가 되도록 a와 b를 교환한다.
그 외에는 알고리즘의 내용을 그대로 코드로 옮긴 것뿐이다.

검증

저번에 Django 앱 테스트에 대해 공부하면서 잠깐 언급한 unittest 모듈을 이용해 테스트를 진행해 보고자 한다. calc_gcd와 math 모듈의 gcd 함수의 실행 결과가 같은지를 테스트해 볼 것이다.

테스트 케이스

from math import gcd
from random import sample
import unittest

class GCDTestCase(unittest.TestCase):
    # 파이썬의 math 모듈의 gcd 함수와 계산값이 일치하는지 100회 테스트한다.
    def test_100_times(self):
        # 가로수 위치 조건: 10억 이하의 양수
        condition_range = range(1, 1_000_000_001)
        for _ in range(100):
            # 문제에서 가로수 위치는 중복되지 않는다. sample 함수로 반환된 각 값은 unique함
            a, b = sample(condition_range, k=2)
            self.assertEqual(calc_gcd(a, b), gcd(a, b), msg="값이 다름")

테스트 케이스는 unittest의 TestCase 클래스를 상속한다.
테스트 메소드의 이름은 test로 시작해야 한다.
condition_range에 위 문제의 가로수 위치 조건과 같은 범위를 지정한다.
radnom 모듈의 sample 함수는 주어진 시퀀스에서 중복되지 않는 값 k개를 뽑아서 그 값들이 담긴 리스트를 반환한다.
TestCase의 assertEqual 메소드는 두 인자의 값이 같은지 검사하여, 값이 다르면 AssertionError를 일으킨다. 이때 출력할 메시지를 msg 인자를 통해 정할 수 있다.

테스트 실행

테스트를 실행하는 법은 간단하다. unittest.main을 호출하면 된다.

if __name__ == '__main__':
    unittest.main()

테스트 결과

테스트를 통과하였다. 혹시 100회 시행이라서 믿음이 가지 않는다면, 100을 다른 수로 바꿔서 테스트해 볼 수도 있다.

여러 수의 최대공약수

그런데, 위의 방법은 두 수의 최대공약수를 구하는 방법이다. 하지만, 가로수 문제에서는 여러 수의 최대공약수를 구해야 한다.

그렇다면 어떻게 해야 할까?

답은 간단하다. 최대공약수가 모든 수들의 공약수 중 가장 큰 수라는 점을 생각해보면, a, b, c의 최대공약수 (gcd(a, b, c))는 a와 b의 최대공약수와 c의 최대공약수 (gcd(gcd(a, b), c))와 같다는 것이 성립됨을 알 수 있다.

그렇다면 이 원리를 적용해서 가로수 문제를 풀어보자.

가로수 문제 풀이

import sys
input = sys.stdin.readline

from copy import copy

def calc_gcd(a, b):
    if a < b:
        a, b = b ,a
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b

    return b

def gcd_multiple_numbers(arg):
    numbers = copy(arg)
    while len(numbers) > 1:
        a, b = [numbers.pop() for _ in range(2)]
        numbers.append(calc_gcd(a, b))
    return numbers[0]

n = int(input())

street_trees = [0] * n
distances = list()

for i in range(n):
    pos = int(input())
    street_trees[i] = pos

    if i > 0:
        tmp = street_trees[i] - street_trees[i-1]
        if tmp not in distances:
            distances.append(tmp)

last_minus_first = street_trees[-1] - street_trees[0]
distance = (gcd_multiple_numbers(distances))

print(last_minus_first // distance - n + 1)

혹시 모를 상황에 대비해서 원본 리스트를 복사했는데, 지금 보니 복사하지 않아도 괜찮았을 것 같다.
여러 수의 최대공약수 계산의 경우, 먼저 맨 뒤의 두 수를 뽑고, 그 수의 최대공약수를 다시 넣고, 맨 뒤의 두 수를 뽑는 과정을 numbers의 길이가 1이 되는 (모든 수의 최대공약수만이 남는) 때까지 반복했다.

이 코드를 제출해보니, 통과와 함께 452ms의 시간이 나왔다.

🔚 결론

오늘은 유클리드 호제법에 대해 알아보았다. 사실 위의 코드에는 개선할 수 있는 부분들이 있다. 다음 번에는 유클리드 호제법에 대해 더 알아보면서, 위의 코드를 개선해 보고자 한다.

맨 처음에 적었듯이 해커톤 아이디어 준비로 인해 오늘은 짧은 내용을 준비했기에 금방 쓸 줄 알았는데, 이것저것 찾고, 검증해보다 보니 생각보다 시간이 길어져서 또 새벽 3시가 다 되어서 글을 마무리하게 되었다.

이렇게 이번 주의 TIL 활동이 끝났다. 팀원들의 TIL 그리고 나의 TIL을 보니 확실히 하루하루 지식들을 채워나가고 있음이 느껴진다. 그럼에도 채워야 하는 그릇이 너무 큰 것 같다. 다음 주에는 또 무엇을 쓰게 되고, 팀원들은 어떤 것들을 공부하게 될까? 다음 주의 TIL 활동이 기대된다.