유클리드 호제법(최대공약수 구하기)

2024. 7. 18. 16:08·Java & Spring/알고리즘

◇ 유클리드 호제법 : 최대공약수를 구하는 알고리즘

최대공약수(GCD) : 유클리드 호제법을 통해 구한다.

최소공배수(LCM) : 두 수의 곱을 최대공약수(GCD)로 나눈다.

  1. 두 수 A, B(A > B)에 대해 A / B의 나머지 C를 계산
  2. B를 C로 나눈 나머지 D를 계산
  3. C를 D로 나눈 나머지 E를 계산
  4. 위 과정을 반복하여 나머지가 0이될 때 마지막 나누는 수가 최대 공약수가 된다.

ex)
1071과 1029의 최대공약수를 구하면 마지막 나머지가 0이되는 수 21이된다.

  • 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
  • 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
  • 42는 21로 나누어 떨어진다.

◇ 구현

1. 재귀함수 사용

public class test {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int GCD = gcd(n, m);
		int LCM = (n * m) / GCD;

		
		br.close();
        bw.write(Integer.toString(GCD));
        bw.newLine();
        bw.write(Integer.toString(LCM));
        bw.flush();
	}
	
	public static int gcd(int p, int q) {
		if (q == 0) return p;
		return gcd(q, p % q);
	}
}


※ 재귀함수에서 대소관계 구분이 필요없는 이유
ex) n = 12, m =18을 입력 할 경우

  •  처음 gcd(12, 18)를 호출
  •  gcd 함수는 두 인자 p와 q를 받음, 여기서 p = 12, q = 18
  •  gcd 함수의 구현에서 q가 0이 될 때까지 재귀적으로 호출하며 최대공약수를 계산
  •  현재의 호출에서는 q가 0이 아니므로, 재귀 호출로 gcd(q, p % q)를 수행
  •  따라서 gcd(12, 18)은 gcd(18, 12 % 18)로 변화
  •  여기서 12 % 18은 12
  •  따라서 새로운 호출은 gcd(18, 12)

2. 일반적인 구현

public class test {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int B = n > m ? n : m;
		int S = n > m ? m : n;
		int tmp = 0;
		
		while(S != 0) {
			tmp = S;
			S = B % S;
			B = tmp;
		}
		
		int GCD = tmp;
		int LCM = (n * m) / GCD;

		
		br.close();
        bw.write(Integer.toString(GCD));
        bw.newLine();
        bw.write(Integer.toString(LCM));
        bw.flush();
	}
}



 

 

 

'Java & Spring > 알고리즘' 카테고리의 다른 글

다익스트라(Dijkstra) - 최단경로 찾기  (0) 2025.03.24
그래프탐색 - DFS와 BFS  (0) 2024.12.23
에라토스테네스의 체(소수, 약수 구하기)  (0) 2024.07.26
투 포인터(Two Pointer) 알고리즘(세 수의 합 구하기)  (0) 2024.07.25
'Java & Spring/알고리즘' 카테고리의 다른 글
  • 다익스트라(Dijkstra) - 최단경로 찾기
  • 그래프탐색 - DFS와 BFS
  • 에라토스테네스의 체(소수, 약수 구하기)
  • 투 포인터(Two Pointer) 알고리즘(세 수의 합 구하기)
DJ.Kang
DJ.Kang
백엔드 개발 기록 블로그
  • DJ.Kang
    DJ Hello World
    DJ.Kang
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 이론공부
      • 시스템설계
      • Java & Spring
        • TIL
        • 트러블슈팅
        • 고도화
        • 알고리즘
        • 코딩테스트
        • Java
        • Spring
        • Thymeleaf
      • 프로젝트
        • coin-trading
        • 트러블슈팅
      • Docker
      • DB
      • AWS
      • CI-CD
      • 웹
      • git & github
      • 구인공고분석
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    java기초
    java 에라토스테네스의 체
    개발로드맵
    java two-pointer
    java arrays.copyofrnage()
    java enhance switch
    Java this
    데이터 타입
    Java 생성자
    java
    데이터 크기
    java 제어자
    자료구조
    java 메서드
    java super
    프로그래머스 java 기초 트레이닝
    java 세수의합
    프로그래머스 java 기초트레이닝
    java 멤버
    java 유클리드 호제법
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
DJ.Kang
유클리드 호제법(최대공약수 구하기)
상단으로

티스토리툴바