반응형
[문제]
[결과]
[해설]
유클리드 호제법(유클리드 알고리즘)은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.
호제법이란 두 수가 서로 상대방의 수를 나누어서 결과적으로 원하는 수를 얻는 알고리즘을 의미한다.
원리는 이렇다.
큰 수를 작은 수로 나눈다 -> 나누는 수를 나머지로 계속 나눈다 -> 나머지가 0이 나올 때까지 반복한다.
-> 나머지가 0이 나온다면, 그때 나누는 수가 최대공약수이다.
반응형
'알고리즘 PS > C++' 카테고리의 다른 글
| 백준 5565번 c++ 문제 풀이 (0) | 2022.02.16 |
|---|---|
| 백준 2748번 c++ 문제 풀이 (0) | 2022.02.15 |
| 백준 2441번 c++ 문제 풀이 (0) | 2022.02.15 |
| 백준 2440번 c++ 문제 풀이 (0) | 2022.02.15 |
| 백준 1408번 c++ 문제 풀이 (0) | 2022.02.15 |