[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

유클리드 호제법을 이용하면 두 수의 최대공약수를 구할 수 있습니다. 최대공약수는 두 수의 공통인 최대 약수를 말합니다. [ Contents ] 1. 유클리드 호제법 (Euclidean Algorithm) 두 자연수 X, Y가 있을 때 (단, X > Y) 1) X와 Y의 최대공약수는 'X를 Y로 나눈 나머지'와 'Y'의 최대공약수와 같다. - 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복 2) X와 Y의 최대공약수는 'X를 Y로 뺀 값'과 'Y'의 최대공약수와 같다. - X와 Y가 같아질 때까지 큰 수를 작은 수로 빼며 반복 두 수의 최대공약수는 작은 수로 빼거나, 나눈 나머지로 구한 최대공약수와 같습니다. 유클리드 호제법을 이용하면, 1부터 Y까지 공약수 유무를 판별하지 않고도 최대공약수를 구할..

원문링크 : [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

 등록된 다른 글

[구현/수학] 백준 8871 Zadanie próbne 2 - 파이썬(Python)

[구현/수학] 백준 8871 Zadanie próbne 2 - 파이썬(Python)

[구현/수학] 백준 14264 정육각형과 삼각형 - Python

[구현/수학] 백준 14264 정육각형과 삼각형 - Python

[보안] 대칭키 방식과 비대칭키(공개키) 방식: 개념과 장단점, 차이점

[보안] 대칭키 방식과 비대칭키(공개키) 방식: 개념과 장단점, 차이점

[Brute Force] 백준 15656 N과 M (7) - 파이썬(Python)

[Brute Force] 백준 15656 N과 M (7) - 파이썬(Python)

[구현/수학] 백준 21866 추첨을 통해 커피를 받자 - 파이썬(Python)

[구현/수학] 백준 21866 추첨을 통해 커피를 받자 - 파이썬(Python)

[구현/수학] 백준 13240 Chessboard - 파이썬(Python)

[구현/수학] 백준 13240 Chessboard - 파이썬(Python)

[SW공학] 모듈화(Modulariation): 결집도와 응집도의 종류와 강도

[SW공학] 모듈화(Modulariation): 결집도와 응집도의 종류와 강도

[구현/수학] 백준 5691 평균 중앙값 문제 - 파이썬(Python)

[구현/수학] 백준 5691 평균 중앙값 문제 - 파이썬(Python)