유클리드 호제법...

프로그래머스 Lv.1문제중 최대공약수와 최소공배수 문제를 풀어보았다.

다음과 같은 조건에 맞는 함수를 작성하는 문제이다.

우선 최대공약수를 구하는 방법을 찾아보다가 유클리드 호제법이라는 방법이 있다는 것을 알고 그것에 대해 공부했다.

유클리드 호제법이란...

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[1] 일본의 수학 교육과정에서는 수학A로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다. - 나무위키.

나무위키에는 위와같이 정의해 놓았다. 유클리드 호제법을 수식으로 나타내면

즉 a > b보다 클 때 a를 b로 나눈 나머지를 r이라고 한다. 이것에 대해서 다시 b를 r로 나누는 작업을 반복하면서 나머지가 0이되는 b값이 두 수 a, b의 최대공약수이다.

이 공식을 적용해서 위의 문제를 풀어보았다.

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int a = n;
        int b = m;
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;          
        }
        answer[0] = a;
        answer[1] = n * m / answer[0];
        return answer;
    }
}

문제에서 주어진 입력값이 n = 3이고 m = 12일 때 [3, 12]를 반환해야 한다.
1. 2개의 배열형태로 값을 반환하라고 했기 때문에 정수형 배열 answer를 2의 크기로 지정해 준다. 그리고 int a 에 n을 넣고 in b 에 m값을 대입한다.

2. while 반복문을 이용해 b값이 0이 될때까지 아래 과정을 반복한다.

3. a를 b로 나눈 나머지를 r 이라고 하면 a = 3, b = 12이기 때문에 정수형으로 반환했을 때 r값은 3이 된다. a = b; 해서 a값을 12로 만들어주고 b = r 이기 때문에 b값을 3으로 만들어준다. 즉 a > b라는 조건이 없어도 위의 연산에 의해 b가 더 클 경우 a와 b의 위치가 바뀐다.

4. 아직 b값이 0보다 크기 때문에 반복한다. 12를 3으로 나누면 나머지 r은 0이된다. 유클리드 호제법에 의하면 a % b = r 이고 이때 r =0 이면 최대공약수는 b라고 되어있다. 즉 3과 12의 최대공약수는 3이다. 그리고 a = 3이되고 b = 0이된다.

5. b값이 0이기 때문에 while문은 더이상 실행되지 않고 아래로 내려간다. answer라는 정수형 배열에 0번 인덱스는 a기 때문에 3이 들어간다.

6. answer의 1번 인덱스에는 최소공배수의 값이 들어가야 하는데 최소공배수를 구하는 공식을 보면 구하고자 하는 두 수 n, m에 대해 n,m의 최소공배수는 n x m / (최대공약수) 라고 한다.
   즉 n x m / answer[0] (여기서 우리는 최대공약수를 이미 구해서 answer[0]에 넣어주었다.) 해주면 된다.

7. asnwer 를 return 해주면 문제가 끝난다.

최대공약수 구하는 방법을 알면 쉽게 풀 수 있는 문제지만 모른다면 많은 생각이 필요할 것 같다.