hye0.log hye0.log

최대공약수 구하는 알고리즘

• [Python] 유클리드 호제법(Euclidean Algorithm)

  Algorithm/Basic 2021. 3. 19. 18:46

  1. 정의 - 두 수의 최대공약수를 구하는 알고리즘 2. 방법 - 2개의 자연수 a, b(a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대공약수와 같음 -> 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. 3. 비교 유클리드 호제법이 아닌 다른 방법으로 코드를 작성한 후, 시간을 비교해보았습니다. 2초 가량 차이가 난다. 결론: 최대공약수를 구할 땐 유클리드 호제법을 이용하자

  Read More