알고리즘/이론 (1) 썸네일형 리스트형 [수학] 유클리드 호제법이란?(gcd, lcm) 유클리드 호제법 알고리즘 문제에서 두 수의 최대 공약수(gcd)를 찾는데 활용되는 알고리즘 이론이다. 어려운 내용도 아니고 구현도 간단하지만, 그만큼 최대공약수 문제의 기본이 되는 이론이니 익혀두는 것을 추천한다! 원리 두 수 a,b가 있을 때, a를 b로 나눈 나머지를 r이라고 할 때(a%b = r (a>b) ), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 따라서, 이 성질에 따라 a를 b로 나눈 나머지 r을 구한 뒤, b를 r로 나눈 r'를 구하고 r%r' == 0 이 된다면 r'이 a와 b의 최대 공약수가 된다. (위 같은 식이 성립하는 이유는 나머지 연산(%)이 분배법칙이 성립하기 때문인데, 나머지 연산의 분배법칙 또한 수학 카테고리의 문제의 기본이 되는 경우가 많으니 찾아보길 권장.. 이전 1 다음
