유클리드 호제법 정리
Membership/알고리즘 2015. 4. 15. 22:06 |유클리드 호제법을 한번 알아보았다.
LCM(least common multiple) - 최소 공배수
GCD(Greatest common divisor) - 최대 공약수
주로 LCM과 GCD 문제에서 자주 사용되는데, 그 원리를 알아본다면,
정수의 최대 공약수는 두 수의 공약수 중 가장 큰 수이다.
예를 들어 20과 8 의 최대 공약수는
20의 약수 : 1,2,4,5,10,20
8의 공약 : 1,2,4,8
20과 8의 공약수 : 1,2,4
이중 최대 공약수는 4 이다.
유클리드 호제법에 의하면
20 = 8 * 2 + 4 로 표현 가능하고 20과 8의 공약수는 8과 4의 공약수와 같다고 할 수 있다.
그렇다면 8과 4의 최대 공약수를 구한다면
8 = 4 * 1 + 4
8과 4의 공약수는 4와 4의 공약수와 같다.
결국 20과 8의 최대공약수는 4가 되는 것이다.
그렇다면 최소공배수를 알아보자.
두 수의 최소공배수는 각각의 수의 곱에 대하여 처음으로 공통된 숫자를 찾는것이다.
20과 8을 다시 예로 든다면
20의 배수 = 20,40,60,80...
8의 배수 = 8,16,24,32,40..
20과 8의 최소 공배수 = 40이 된다.
이 또한 잘 생각해보면 처음 수인 20 * 8 의 값에 서로 공통된 약수의 최대값인 최대공약수를 나눠보면 최소공배수가 나온다는 것을 알 수 있다.
20 * 8 = 160 -> 160 / 4 = 40
그럼 이를 코딩에 적용 해본다면...
문제: 두 수의 최대공약수와 최소 공배수를 출력하시오 입력: 두개의 정수 출력: 최대공약수 최소공배수 (주석을 많이 달아놓지 않아서 이해가 힘들지도 모르지만 gcd 재귀함수를 잘 생각해보면 이해가 될것이다.)'Membership > 알고리즘' 카테고리의 다른 글
(10 ^ 7)! 의 자리수를 어떻게 구할 수 있을까? (0) | 2015.03.29 |
---|---|
기본적인 LinkedList 구현 (0) | 2015.01.20 |
루트값 까지 배수를 제외해서 소수값 구하는방법 (0) | 2015.01.16 |
백트래킹 기초 주사위 굴리기 (0) | 2015.01.15 |
재귀로 글래스파이어 활용 (0) | 2015.01.12 |