728x90
1. 유클리드 호제법
- 두 수의 최대 공약수를 구하는 알고리즘이다.
- % 연산을 사용하여 구현한다.
2. 유클리드 호제법 구현
- '큰 수 % 작은 수' 연산을 수행
- '작은 수 % 과정 1의 결과값' 연산을 수행
- 나머지가 0이 되는 순간의 작은 수가 최대 공약수이다.
3. 예제 문제
[1934] 최소공배수 (JAVA)
# 문제 설명 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 6
spicyrisotto.tistory.com
[1850] 최대공약수 (JAVA)
# 문제 설명 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약
spicyrisotto.tistory.com
[2609] 최대공약수와 최소공배수 (JAVA)
# 문제 설명 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-12 오일러 피 (0) | 2024.04.07 |
|---|---|
| Day-13 확장 유클리드 호제법 (0) | 2024.04.06 |
| Day-12 소수 구하기 (0) | 2024.04.04 |
| Day-10,11 그리디 알고리즘 (0) | 2024.04.03 |
| Day-9 이진 탐색 (0) | 2024.03.29 |
