- 정의
- 두 수의 최대 공약수를 구하는 알고리즘
- 재귀를 활용할 수도 있다
- 핵심이론
- MOD연산은 최대 공약수를 구할 때 이용할 키이다
- MOD연산은 두 값을 나눈 나머지를 구하는 연산이다
- 먼저 큰 수를 작은 수로 나누는 MOD연산을 수행한다
- 앞 단계에서 작은 수와 MOD 연산 결과값으로 MOD 연산을 수행한다
- 두번째 단계를 반복하여 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택한다
- MOD연산은 최대 공약수를 구할 때 이용할 키이다
- 이해하기
'자료구조 > Do It' 카테고리의 다른 글
| 그래프의 표현 (0) | 2023.12.13 |
|---|---|
| 그래프 (0) | 2023.12.12 |
| 오일러 피 (1) | 2023.12.11 |
| 그리디 알고리즘(탐욕법, Greedy Algorithm) (1) | 2023.11.13 |
| 이진탐색 (0) | 2023.11.09 |