목록유클리드 호제법 (1)
Hippo's data
유클리드 호제법 - 최대공약수GCD, 최소공배수LCM 구하기
백준 문제를 풀다보면 공약수, 공배수를 활용하는 문제들을 찾아볼 수 있다. 그중 최대 공약수GCD(Greatest Common Divisor), 최소 공배수LCM(Least Common Multiple)를 구하는 문제들이 있는데 이 경우 유용하게 이용할 수 있는 정의가 있는데 바로 '유클리드 호제법'이다.유클리드 호제법은 유클리드의 원론에 적혀있는 정의로 한국 수학교육과정에서는 자세하게 다루지 않는 내용이다.유클리드 호제법을 통해 최대 공약수를 간단하게 구할 수 있다. # 최대 공약수 GCD(Greatest Common Divisor)자연수 a,b가 주어졌을때 a 를 b로 나눈 나머지가 r인 경우 a,b의 최대 공약수와 b와 r의 최대 공약수가 동일하다이를 응용하면 a를 b로 나눈 나머지 r을 구하고..
Algorithm
2023. 8. 8. 00:48