재귀 :: 유클리드 호제법 - 최대공약수 구하기

드디어, 재귀 알고리즘 중 유클리드 호제법을 이해하였다.

다른 사람들에겐 우습고 유치한 '최대공약수 구하기' 일지 모르지만 나에겐 큰 성장이고, 드디어 알아냈다는 것이 기뻐서 기록하려고 한다.

 

static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

 

위 코드는 재귀적으로 자기 자신을 호출하며 최대 공약수를 구하는 방법이다.

 

 

이것을 반복문을 사용하여 구현해보았다.

	int gcd = 0;
        int bigger = x;
        int smaller = y;

        // 더 큰 값이 앞으로 오도록,
        if (bigger < y) {
            bigger = y;
            smaller = x;
        }

        // 반복하며 최대공약수 찾기
        while (true) {
            int a = bigger % smaller;
            if (a != 0) {
                bigger = smaller;
                smaller = a;
            } else {
                gcd = smaller;
                break;
            }
        }

정수 x, y 중에 더 큰 값이 x에 위치하게 설정하고, 반복문을 수행하며 최대공약수를 구하도록 구현했다.

 

정수 x, y를 입력받아 결과를 확인해보니 두 버전 모두 동일한 결과값을 얻을 수 있었다. 

 

 

그렇지만 아직 멀었죠?

static int gcd(int x, int y) {
		while (y != 0) {
			int temp = y;
			y = x % y;
			x = temp;
		}
		return x;
	}

너무... 멀었죠..?