유클리드 호제법

LeetCode 문제를 풀다가 Greatest Common Divisor of Strings라는 문제를 만났다. 처음에는 별생각 없이 두 문자열을 포인터로 하나씩 비교하는 방식으로 풀었는데, 곧 그 접근이 틀렸다는 것을 알았다. 역시 문제를 풀기 전에는 요구사항을 제대로 읽고 구조를 먼저 분석해야 한다.

핵심은 두 문자열이 공통으로 가질 수 있는 가장 긴 반복 단위를 찾는 것이다. 이 문제를 문자열 자체가 아니라 문자열의 길이 관점으로 바꾸어 보면, 결국 두 길이의 최대공약수를 찾는 문제로 볼 수 있다.

최대공약수를 직접 구현해 본 적이 없어서 혼자 여러 방법을 생각해 보다가, 결국 다른 풀이를 참고했다. 그리고 정말 간결한 코드를 발견했다.

public int gcd(int a, int b) {
    return (b == 0)? a : gcd(b, a % b);
}

그리고 이 방식이 그 유명한 유클리드 호제법이라는 것을 알게 되었다.

내가 원래 알고 있던 최대공약수 구하는 방법은 두 수를 공통 약수로 계속 나누어 가는 방식이었다. 예를 들어 252와 105의 최대공약수를 구한다면 먼저 둘 다 3으로 나누어 252 / 3 = 84, 105 / 3 = 35를 얻고, 다시 둘 다 7로 나누어 84 / 7 = 12, 35 / 7 = 5를 얻는다. 12와 5는 더 이상 공통 약수가 없으므로 공통으로 나누었던 3 * 7 = 21이 최대공약수다.

유클리드 호제법은 같은 결과를 훨씬 간단하게 구한다. 두 수 a, b에 대해 gcd(a, b) = gcd(b, a % b)라는 관계를 반복하고, 나머지가 0이 되는 순간의 값이 최대공약수가 된다. 위 코드가 바로 이 규칙을 재귀로 표현한 것이다.

참고: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm https://seunghyum.github.io/algorithm/Euclidean-algorithm