최대공약수 재귀(recursion)함수 feat. 유클리드 호제법

<!-- TOC -->autoauto- 들어가기auto- 마무리autoauto<!-- /TOC -->

들어가기

인프런에서 무료 알고리즘 강좌를 듣고있다. 아 코딩테스트 넘나 어려운것...

여튼 순환 혹은 재귀함수를 이용하여 최대공약수를 구하는 예제인데, 참으로 신박해서 정리해본다. 기원전 300년 전 유클리드라는 아저씨가 유클리드 호제법이라고 최대공약수를 구하는 공식을 만들어 놓으셨다. 아래 코드는 그 유클리드 호제법을 이용한 최대공약수를 구하는 예제이다.

Java 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class test {

public static void main(String [] args) {

System.out.println(gcd(10, 12));

}

public static int gcd(int p, int q) {
if( q == 0) {
return p;
}else {
return gcd(q, p % q);
}
}

}

Python 코드

1
2
3
4
5
6
7
8
def gcd(p, q):
if q == 0:
return p
else:
return gcd(q, p % q)

result = gcd(10, 12)
print('최대공약수:',result)

마무리

이거 알고리즘 보다, 중등수학부터 다시 봐야 할것 같다.