우당탕탕 게임개발 여행기

프로그래머스 문제에서 분수를 계산하는 문제가 나왔다.

분수를 계산할려고 하면 먼저 분모를 똑같이 만들기 위한 수를 곱해주고

곱한 수를 각각 분자에서 곱해서 서로 더해준다.

계산된 분자와 분모의 최대공약수를 구해서 나눠주면 끝난다.

분수끼리 계산은 구현했으나 최대공약수를 구하는 방법은 유클리드 호제법을 사용하면 된다.

약수를 구하는데에는 어려운 경우가 발생한다.

1. 두 수가 크면 약수를 구하기 복잡해진다. (ex. 26552와 46552의 최대 공약수는?)

2. 약수 찾기가 어려운 경우 (ex. 403과 155의 최대 공약수는?)

인간의 대선배님들은 쉽게 구하는 방법을 후세를 위해서 남겨주신 것이다. 

- 유클리드 호제법을 이용해서 최대공약수 구하기

일단 두 수(a > b)가 주어지면

  1. 더 큰 수(a)에서 작은 수(b)를 나눈다. : a / b

  2. 작은 수(b) 에서 나눈 값에서 나온 나머지(a % b)를 나눈다. : b / (a % b)

  3. 나머지가 0이 될 때까지 반복한다.

이를 코드로 표현해보자면 이런식으로 표현할 수 있다.

        // 최대 공약수(Greatest Common Divisor) 구하기
        public static int GCD(int a, int b) {
            int temp = 0;
            while (b != 0) { 
                temp = b;
                b = a % b;
                a = temp;
            }
            return temp;
        }

- 프로그래머스에서 풀었던 전체 코드 (분수 계산하기)

internal class Program
{
    // 최대 공약수(Greatest Common Divisor) 구하기
    public static int GCD(int a, int b) {
        int temp = 0;
        while (b != 0) { 
            temp = b;
            b = a % b;
            a = temp;
        }
        return temp;
    }

    public static int[] solution(int numer1, int denom1, int numer2, int denom2)
    {
        numer1 *= denom2;
        numer2 *= denom1;

        int temp = numer1 + numer2;
        int tempdenom = denom1 * denom2;

        // 최대공약수 구하고 약분하기
        int gcd = GCD(temp, tempdenom);
        return new int[] { temp / gcd, tempdenom / gcd };
    }

    static void Main(string[] args)
    {
        // Program program = new Program();
        Console.WriteLine(string.Join(" ", solution(1, 2, 3, 4))); // 5 4 
        Console.WriteLine(string.Join(" ", solution(9, 2, 1, 3))); // 29 6 
    }
}