[C++] 최대공약수 구하기 (유클리드 호제법)
예를 보시면 바로 이해가 됩니다. 78696과 19332의 최대공약수를 구하면, 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 + 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 위와 같이 최대공약수
unagi44.wordpress.com
최대공약수 : 유클리드 호제법
최소공배수 : a*b / 최대공약수
'알고리즘' 카테고리의 다른 글
| [알고리즘] BFS,DFS,다익스트라,MST 사용하는 경우 (0) | 2025.05.28 |
|---|---|
| [알고리즘] 정렬 알고리즘 선택 (0) | 2024.02.26 |
| [알고리즘] 동적 계획법(DP) - TIC-TAE-TOE(3목) (0) | 2023.02.23 |
| [알고리즘] 동적 계획법(DP) - LIS(Longest Increasing Subsequence) (0) | 2023.02.22 |
| [알고리즘] 동적 계획법(DP) - 조합 (0) | 2023.02.22 |