GCD & LCM

GCD(Greatest Common Divisor)는 최대공약수를 의미하며 LCM(Least Common Multiple)은 최소공배수를 의미한다.

일반적으로 GCD를 구하는 알고리즘은 유클리드의 호제법을 쓰며 다음과 같다.

1. 만약 72와 64라는 수가 있을 때 두 수 사이의 나머지를 구한다.(72 % 64 = 8)
2. 나머지와 두 수 중에 작은 수 사이의 나머지를 구하는 과정을 반복한다.(64 % 8 = 0)
3. 나누어 떨어질 경우 두 수 중에서 가장 작은 쪽이 GCD가 된다.

위의 알고리즘은 나머지 연산을 통해 구할 수 있지만, 나머지 연산보다 더욱 간단한 연산을 통해서도 위의 알고리즘을 구현할 수 있다.

//나머지 연산을 통한 구현
int gcd(int a, int b){
	while(b != 0){
		int temp = a % b;
		if(a > b)   a = temp;
		else        b = temp;
    
		if(a < b)  swap(a, b);
	}
	return a;
}

//뺄셈을 통한 구현
int gcd(int a, int b){
    while(b) (a > b) ? a -= b : b -= a;    //b가 0이 될 때까지 나머지를 구함(최소공배수)
    return a;
}

문제 설명

code review

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

using namespace std;

int gcd(int a, int b){
    while(b) (a > b) ? a -= b : b -= a;    //b가 0이 될 때까지 나머지를 구함(최소공배수)
    return a;
}

int lcm(int a, int b){ return a * b / gcd(a, b); };  //두 수의 곱에서 최소공배수를 나누어 최대공약수를 구함

int solution(vector<int> arr) {
    int answer = 1;
    for_each(arr.begin(), arr.end(), [&](int i){ answer = lcm(answer, i); }); //2개씩 순차적으로 최소공배수를 구해감
    return answer;
}