규도자 개발 블로그

최대공약수 구하기 알고리즘을 풀다가 비슷한 로직이 필요했는데 잘 생각이 안나서 이번기회에 정리해두려고 한다. 보통 컴퓨터로 최대공약수를 구할 땐 유클리드 호제법이라는 방법을 많이 쓴다. 이미 기원전 300년에 검증된 로직이므로 그런게 아닐까 싶다. 유클리드 호제법은 다음과 같다. 입력으로 두 수 m, n이 들어온다. (m>n) n이 0이라면 m을 반환한다. m이 n으로 나누어 떨어지면 n을 반환한다. 위 2, 3번의 경우에 해당되지 않을 경우 n을 m으로, m을 n으로 나눈 나머지를 n에 대입하고 1번으로 돌아간다. 코드로 표현하면 다음과 같다. def gcd(m, n): if m < n: m, n = n, m if n == 0: return m if m % n == 0: return n else: re..