유클리드 호제법
두개의 수로 최대공약수를 구하는 알고리즘
두 정수를 같은 수로 나누어 가며 최대 공약수를 셈하는 방법
호제 : 서로 나누다
int A , int B 가 존재할 때,
A를 B로 나눈 나머지를 r 이라 정의(단, A>B)
A와 B의 최대공약수(GCD)는 B와 r의 GCD와 같다는 논리를 이용해 계속 나눗셈을 연산하여 r == 0 일때, 나누는 수가 GCD가 된다.
A % B = r
42 % 24 = 18(나머지)
24 % 18 = 6
18 % 6 = 0
r == 0 일때, 나누는 수(B) == 6, 즉 6이 최대공약수(GCD)이다.
최소공배수(LCM) = (A / GCD) * (B / GCD) = A * B / GCD
유클리드 호제법을 이용한 최소공배수와 최대공약수 구하기 연습문제
이렇게 간단하게도 푸는 사람들을 보면 대단하다. 바로 생각이 날 정도로 문법에 익숙한 사람들이라 생각된다.
'Algorithm' 카테고리의 다른 글
| 정렬 알고리즘(선택정렬, 삽입정렬) (0) | 2022.05.19 |
|---|---|
| DFS(깊이 우선 탐색 - 그래프 탐색 알고리즘) (0) | 2022.05.18 |
| 구현(시뮬레이션과 완전탐색) (0) | 2022.05.17 |
| 탐욕법(Greedy Algorithm - 동전 교체, 체육복 대여 연습문제) (0) | 2022.05.17 |
| 배열(복제, 버블정렬) (0) | 2022.05.08 |