GCD 검색 결과

해당 글 2건
왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까?

질문이 왔습니다. 왜 확장 유클리드는 최악의 경우에, 대략 log(min(a,b))개의 gcd 함수를 호출하나요? 생각보다 빨리 끝나는 것 같은데. 이 질문에 대한 답을 하기 위해서는 재귀 함수의 기저 조건에서부터 위로 쭉 올라가 보아야 합니다. 그러면 기저 조건을 먼저 볼 건데요. gcd(2,1)의 값은 1입니다. 2는 1로 나누어 떨어지기 때문입니다. 이 때, gcd는 재귀적으로 1번 호출합니다. 유클리드 알고리즘은, a = bQ+r꼴로 표현이 될 때 (단 0b이면서 3으로 나눴을 때 나머지가 2인 가장 작은 자연수는 얼마인가요? 5입니다. 우리는 b 다음에 a 이렇게 커지는 수열을 생각할 때, a를 최대한 작은 친구를 선택하는 겁니다. 최대한 천천히 증가하게끔. 그러면 gcd(5,3)을 호출하였을 ..
자료알고/알고리즘 2019. 8. 21. 15:50
최대공약수 최소공배수 알고리즘 : 짧은 코드 이해해 봅시다.

오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다. 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다. 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 ..
자료알고/알고리즘 2019. 8. 7. 17:50