서론

알고리즘 공부를 하다가 또 새로운 지식을 습득하게 되었으니 정리를 해야겠지?

재귀함수를 공부하고 있던 중
재귀함수를 통해 최대공약수 구하는 문제를 발견하고 풀이를 보았다

나한테 큰 도움이 될 수도 있으니 바로 정리하려고 한다.

---

본론

유클리드 호제법을 이용해 최대공약수를 찾아볼 것 이다.

유클리드 호제법

설명은 위키에도 자세히 나와 있지만,

짧게 설명하자면 2개 이상의 숫자를 가지고 최대공약수를 구할 경우 두 수의 나머지가 0이 될때까지
계속해서 반복하며 나머지를 구하는 방식이라고 생각하면 된다.
코드를 통한 예제를 보면서 이해해보자

x = 22, y = 8이라는 가정하에 코드를 돌려보자

코드

public class Main {
	public static int GCD(int x, int y) {

		if(y == 0) {
			return x;
		}
		else {
			return GCD(y, x % y);
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int x = Integer.parseInt(br.readLine());
		int y = Integer.parseInt(br.readLine());

		int result = GCD(x, y);
		System.out.println(result);

	}
}

x = 22, y = 8이 되어서

처음에 GCD(22, 8)의 함수가 실행된다.

일단 처음에 y가 0이 아니기 때문에 if(y==0)은 당연히 걸리지 않고 else로 넘어갈 것이다.

여기서 부터 재귀함수가 시작된다.
else에서 GCD를 다시 호출했다.
여기서 살펴볼 점이 x % y 이 부분이 유클리드 호제법의 핵심이다.

GCD함수가 실행되는 시점에서 y의 매개변수가 0으로 실행되면 if문에 걸리면서 종료되는 것이다.

실행되는 과정을 천천히 살펴보자.

1. GCD(22, 8)로 실행
else문 실행 y값이 x자리로 이동
GCD(8, 22 % 8) -> GCD(8, 6)

2. GCD(8, 6)로 실행
또 다시 y가 0이 아니기 때문에 else 문 실행 y값이 x자리로 이동
GCD(6, 8 % 6) -> GCD(6, 2)

3. GCD(6, 2)로 실행
또 다시 y가 0이 아니기 때문에 else 문 실행 y값이 x자리로 이동
GCD(2, 6 % 2) -> GCD(2, 0)

4. GCD(2, 0)로 실행
여기서 y값이 0이된다고 곧바로 종료 되지 않는다는 것을 명심하자!
매개변수 y의 자리에 0이 들어간 후 if문에 걸려서 종료된다!!

이제 y의 값이 0이므로 if(y==0)의 조건에 걸리게 된다.
이제 return x;를 해주는데 x의 값이 바로 최소공약수가 된다.

답은 2이다.

---

결론

문제 자체가 2개의 숫자로 최대공약수를 구하는 문제여서 비교적 쉬웠지만
조금만 더 깊게 공부한다면 다른 문제에서도 유용하게 쓸 수 있을것 같은(?)
생각이든다.