오늘의 키워드

오늘 푼 알고리즘 문제 중에 최대공약수를 이용하는 문제가 있었다. 그냥 막연하게 최대공약수는 유클리드 호제법으로 구한다. 정도만 알고 있었는데, 이번 기회에 정리해봐야겠다.

프로그래머스 - 숫자 카드 나누기 Lv.2

문제 설명

철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.

1. 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
2. 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a

예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.

철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.

제한사항

• 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
• 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
• arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.

입출력 예

해결방안

arrayA에 있는 모든 원소들의 공통의 최대공약수로 arrayB에 있는 모든 원소를 하나도 나누어떨어지지 않는다면 문제에서 요구하는 1번 조건을 만족하는 가장 큰 양의 정수를 찾을 수 있다.
반대로 , arrayB에 있는 모든 원소들의 공통의 최대공약수로 arrayA에 있는 모든 원소를 하나도 나누어떨어지지 않는다면 문제에서 요구하는 2번 조건을 만족하는 가장 큰 양의 정수를 찾을 수 있다.
이렇게 찾은 두 개의 양의 정수 중에 더 큰 쪽을 return하면 된다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int canDivide(int gcd, vector<int>& arr)
{
    for (auto e : arr)
        if (e % gcd == 0)
            return 0;
    return gcd;
}

int solution(vector<int> arrayA, vector<int> arrayB) 
{
    int answer = 0;
    int gcd1 = 0;
    int gcd2 = 0;
    for (auto e : arrayA)
        gcd1 = gcd(gcd1, e);
    for (auto e : arrayB)
        gcd2 = gcd(gcd2, e);
    answer = max(canDivide(gcd1, arrayB), canDivide(gcd2, arrayA));
    return answer;
}

최대공약수를 구하는 gcd() 함수는 유클리드 호제법을 이용했다.
배열의 모든 원소의 최대공약수는 배열의 원소들을 방문하면서 최대공약수를 구하고, 방금 구한 최대공약수와 다음 원소의 최대공약수를 구하는 식으로 반복하면 된다.

유클리드 호제법

유클리드 호제법의 동작 원리는 다음과 같다.

두 정수 a, b의 최대공약수를 구할 때 (단, a > b),

1. a가 b로 나누어떨어지지 않으면 a를 b로 나눈 나머지 a'을 구한다.
2. b가 a'으로 나누어떨어지지 않으면 b를 a'으로 나눈 나머지 b'을 구한다.
3. 나머지가 0이 될 때까지 위의 과정을 반복한다.

예를 들어.. 1071과 1029의 최대공약수를 구한다고 쳐보자.

1. 1071은 1029로 나누어떨어지지 않으니 그 나머지를 구해보면 42이다.
2. 1029는 42로 나누어떨어지지 않으니 그 나머지를 구해보면 21이다.
3. 42는 21로 나누어떨어지므로 최대공약수는 21이다.

이런식으로 서로를 나눈다고 해서 호제법이라는 이름이 붙었다고 한다.
나머지가 0이 될 때까지 반복하므로 재귀로 간단하게 구현할 수 있고, 컴퓨터에서는 소인수분해를 하는 것보다 빠르게 동작한다.

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

최대공약수를 쉽게 찾을 수 있는 방법을 알았으니, 최소공배수를 쉽게 찾을 수 있는 방법도 알아두자.

int lcm(int a, b)
{
    return a * b / gcd(a, b);
}

최대공약수를 알면 최소공배수를 간단하게 알아낼 수 있다! 그냥 두 수를 곱한 값을 최대공약수로 나눠주기만 하면 된다.

예를 들어.. 12와 30의 최소공배수를 구한다고 쳐보자.

1. 12를 소인수분해하면 2x2x3이다.
2. 30을 소인수 분해하면 2x3x5이다.
3. 최소공배수는 2가 2개, 3은 공통으로 1개씩 가지고 있고, 5가 1개 필요하므로 2x2x3x5 = 60이 되어야한다.

그럼 위의 방법으로 최소공배수가 구해질까 ?

1. 둘을 곱하면 360 = 2x2x2x3x3x5이다.
2. 여기서 최대공약수인 6 = 2x3을 나눠주면..
3. 60 = 2x2x3x5 최소공배수가 구해진다 !

마치며

최소공배수와 최대공약수(유클리드 호제법)은 알고리즘 문제에서 자주 나오는데, 나올 때마다 구글링을 했던 것 같다. 구현하기도 쉽고 개념도 간단한데 말이다. 완벽하게 외우진 못하더라도 개념을 알아두면 다음에 필요할 때 금방 떠올릴 수 있을 정도로는 외워두면 좋을 것 같다.