유클리드 호재법(Euclidean-algorithm)이란?

백준 2609 최대공약수와 최소공배수

최대공약수와 최소공배수를 구하는 법은 중학교 때 배운 바있다. 하지만 코드로 풀어내는 건 또 다른 문제였다.

한참 고민하다가 검색해 보았더니 유클리드 호재법으로 풀라는 조언이 있어, 그 방식대로 코드를 작성하기 시작했다.

유클리드 호재법이란?

유클리드 호재법은 두 수의 최대공약수를 구하는 알고리즘이다. 유클리드 호재법을 이해하기 위해서는 MOD(나머지) 연산을 이해해야 한다.

첫 번째, 큰 수를 작은 수로 나눈 나머지를 구한다.

1112 % 695 = 417

두 번째, 나눴던 수와 나머지로 다시 나머지를 구한다.

695 % 417 = 278

이 과정을 나머지가 0이 될 때까지 반복할 때, 마지막 계산에서 나누는 수로 사용된 수가 최대공약수이다.

즉, 유클리드 호재법은 MOD 연산을 반복하는 알고리즘이다.

코드로 유클리드 호재법 이해하기

자주 사용되는 재귀법으로 유클리드 호재법을 표현해 보자.

import java.util.Scanner;

public class Q4 {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int a = in.nextInt();
        int b = in.nextInt();

        int d = gcd(a, b);

        System.out.println(d); //최대공약수
        System.out.println(a * b / d); //최소공배수

    }
	
    //유클리드 호재법
    public static int gcd(int a, int b) {
    
    	//나머지가 0이면 나누는 수(a)를 반환한다.
        if (b == 0) {
            return a;
        } else {
        
        	//재귀로 MOD 연산을 반복한다.
            // 나머지가 0이 아닐 때는 나누는 수(b)와 나머지(a%b)로 MOD 연산을 반복한다.
            return gcd(b, a % b);
        }
    }
}

코드를 따라 치다보니 한 가지 궁금증이 생겼다. 나누는 수가 최대공약수라면 return a;가 아니라 return b; 여야 하는 것 아닌가?

이 해답은 간단하다.

48과 18의 GCD를 계산한다고 가정해 보자.

- 첫 번째 호출: gcd(48, 18)
48 % 18는 12이므로 gcd(18, 12)를 호출한다.

- 두 번째 호출: gcd(18, 12)
18 % 12는 6이므로 gcd(12, 6)을 호출한다.

- 세 번째 호출: gcd(12, 6)
12 % 6은 0이므로 gcd(6, 0)을 호출한다.

- gcd(6, 0)은 6을 반환한다.

MOD 함수를 진행하며 b를 a로 바꾸다보면, 결국 a가 이전 나누는 수(b)가 되고 b는 0이 되기 때문에 return는 a로 받아야 한다.