최대 공약수 썸네일형 리스트형 최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm))(개선) 저번에 포스팅한 최대 공약수 찾는 알고리즘은 큰 문제점이 하나 있습니다. 만약 50000과 1의 최대공약수를 구하기 위해서는 무려 50000번의 연산을 해야하기 때문입니다. 그런데 저번 포스팅에 사용한 예시 get_gcd(110.33)에서 뺄셈을 모두 끝내면 (11,33) 이 되는건 다 알 고 계실겁니다. 여기서 자세히 살펴보면 110을 33으로 나누고 나머지가 11이 나온다는걸 발견할 수 있습니다. 즉 11=110%33으로 대체가능하며 이 방법으로 많은 뺄셈 연산을 나머지 연산으로 대체가능합니다. 그렇다면 이번에는 함수를 이렇게 짜봅시다. GCD(a,b)=(a%b,b) 이렇게 불필요한 연산을 삭제함으로써 프로그램을 좀더 능률적이게 만들수 있습니다. 아래 프로그램은 이를 이용한 프로그램입니다. 오타 & .. 더보기 최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm)) 최대 공약수는 A=G*aB=G*b 로 표현이 가능합니다. 그렇다면 두 수를 빼보면 A-B=(a-b)G 로 표현이 가능합니다. 그럼 만약 최대 공약수를 구하는 함수 X가 있다고 하면 X(a,b) 와 X(a-b,b) (a>b) 의 값은 같게 나오게 됩니다. 그리고 X(0,b)가 된다면 b가 최대 공약수가 되고 X(a-b,b) (a 더보기 이전 1 다음
