[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 문제 해석/코드 설명
[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 코딩테스트 타파하기 1주차 - 1번 주요 키 포인트 유클리드 호제법 (최대공약수) 2개의 자연수(또는 정수) a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (이때, a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 아래의 코드를 살펴보면 int gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b, a%b); } 연쇄적으로 최대공약수를 찾아가는 것을 볼 수 있다. 성질에 따라서 b를 r로 나눈 나머지를 구하고 다시 이것들을 연쇄적으로 진행해서 나머지가 0이 되었을 때 나누는 수 ((a%b)에서 b)가 a와 b..
알고리즘/C++
2024. 3. 12. 15:43
