알고리즘 (401) 썸네일형 리스트형 최대공약수, 최소공배수 두 수의 최대공약수를 구하는 알고리즘은 유클리드 호제법을 베이스로 한다. 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 + 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 gcd = 36 출처 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 큰 수(a)에서 작은 수(b)로 나누어 그 나머지(r)가 존재하면 작은 수에서 그 나머지로 나누는 과정을 나머지가 없을 때 까지 재귀적으로 반복하는 것이다. int gcd(int a, int b) // always a > b { // int remainde.. 이전 1 ··· 38 39 40 41 다음