[python] 재귀 알고리즘 - 최대공약수 GCD - 유클리드 호제법

안녕하세요.

 

이번 포스팅은 재귀 알고리즘에 대해서 다뤄보았습니다.

 

재귀는 다양한 알고리즘에서 활용이 되는데요. 특히, 재귀를 모르고 지나친다면 다른 재귀에 기반하여 풀 수 있는 고등 알고리즘에 대해 알 수 없게 된다는 점이 있습니다. 

 

재귀로 쉽게 풀 수 있는 대표적인 알고리즘 중 하나인 최대공약수 찾는 알고리즘에 대해서 다뤄보겠습니다.

 

예를 들어 9 x 24 인 직사각형이 있다고 가정하겠습니다.

 

쉽게 범용적으로 풀 수 있는 방법 중 하나는 다음처럼 정사각형으로 분할이 될 때까지 쪼개는 방법이 있는데요.

 

로직 자체는 간다합니다.

• 위 첫번째 그림처럼 9 x 24 크기의 직사각형에서 짧은 변의 길이인 9를 한 변으로 하는 정사각형으로 나눠줍니다. 그러면 2개의 9x9 정사각형이 만들어지고 하나의 9 x 6 크기의 직사각형이 남습니다.
• 마찬가지로 9 x 6 크기의 직사각형에 대해서 다시 짧은 변으로 나눠주어 정사각형을 만들면 3 x 6 크기의 직사각형이 남습니다.
• 이 때 3 x 6 크기의 직사각형은 3 x 3 정사각형 두개로 나뉘어집니다.
• 이렇게 얻은 정사각형 변의 길이 3이 9와 24의 최대 공약수입니다.

위 연산은 python에서 mod 연산자를 활용하면 쉽게 로직을 만들 수 있습니다.

def gcd(x: int, y: int) -> int:
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

 

여기서 재귀라는 속성 때문에 헷갈릴 수 있는 부분 중 하나는 "x와 y 중 어디에 더 짧은 변의 길이 값을 넣어줘야하는가?" 일 수도 있는데요.

위 코드와 동일하게 modulo 연산을 사용하면 그럴 걱정이 없습니다. 

gcd(y, x % y) 의 연산 방식이 결국에는 짧은 변을 기초로 하게 되어 있기 때문입니다.

 

간단하게 호출 순서를 살펴보면서 알아보겠습니다.

 

위에 명시한 코드 내 로직 흐름대로 따라가면 위 순서에 대한 이해가 되실겁니다.