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

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

  • 최근 글

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

티스토리툴바