유클리드호제법

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

안녕하세요. 이번 포스팅은 재귀 알고리즘에 대해서 다뤄보았습니다. 재귀는 다양한 알고리즘에서 활용이 되는데요. 특히, 재귀를 모르고 지나친다면 다른 재귀에 기반하여 풀 수 있는 고등 알고리즘에 대해 알 수 없게 된다는 점이 있습니다.  재귀로 쉽게 풀 수 있는 대표적인 알고리즘 중 하나인 최대공약수 찾는 알고리즘에 대해서 다뤄보겠습니다. 예를 들어 9 x 24 인 직사각형이 있다고 가정하겠습니다. 쉽게 범용적으로 풀 수 있는 방법 중 하나는 다음처럼 정사각형으로 분할이 될 때까지 쪼개는 방법이 있는데요. 로직 자체는 간다합니다.위 첫번째 그림처럼 9 x 24 크기의 직사각형에서 짧은 변의 길이인 9를 한 변으로 하는 정사각형으로 나눠줍니다. 그러면 2개의 9x9 정사각형이 만들어지고 하나의 9 x 6 크..