책/Do it! 알고리즘 코딩 테스트 자바 편

Day-13 유클리드 호제법

댈팽이 2024. 4. 4. 20:53
728x90

1. 유클리드 호제법

  • 두 수의 최대 공약수를 구하는 알고리즘이다.
  • % 연산을 사용하여 구현한다.

2. 유클리드 호제법 구현

  1. '큰 수 % 작은 수' 연산을 수행
  2. '작은 수 % 과정 1의 결과값' 연산을 수행
  3. 나머지가 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