[프로그래머스] - N개의 최소공배수(C++)

N개의 최소공배수

 

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

 

제한사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

입출력 예

arr	result
[2, 6, 8, 14]	168
[1, 2, 3]	6

 

시작 코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> arr) {
    int answer = 0;
    return answer;
}

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int GCD(int a, int b)
{
    int Max = max(a,b);
    int Min = min(a,b);
    
    int r = Max % Min;
    
    if(r == 0)
        return Min;
    else 
        return GCD(Min, r);
}
 
int solution(vector<int> arr) {
    int answer = arr[0];
    
    for(int i = 1; i < arr.size(); i++)
    {
        int gcd = GCD(answer, arr[i]);
        int lcm = answer * arr[i] / gcd;
        answer = lcm;
    }
    return answer;
}

 

코드 분석

GCD 함수를 만들어줍니다. 매개변수로는 int형 a와 b를 받고, int형 Max와 Min 변수에 a,b를 max, min 함수를 사용해 최댓값과 최솟값을 만들어 줍니다. int형 r변수에 max를 min으로 나눈 나머지를 저장하고, 만약 r이 0이라면 최솟값을 리턴, 그게 아니라면 GCD함수를 min값과 r값을 가지고 다시 실행시켜줍니다.

 

솔루션 함수로 돌아와서 answer에 주어진 arr의 첫번째 값을 넣고, for문으로 arr를 돌립니다. for문 안에서 int형 변수 gcd에 GCD함수를 answer 값과 arr[i]값으로 실행한 값을 넣어주고, lcm에 answer에 arr[i]를 곱한 값을 gcd변수로 나눈 값을 넣어줍니다. 이후 answer에 lcm값을 넣어주고 반복문을 빠져나가면 answer값을 리턴하며 종료합니다.

 

풀이 설명

문제에서 원하는 것은 n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수를 만드는 것입니다. 이 문제를 접근하기 위해서는 최대공약수, 최소공배수에 대한 지식이 필요합니다. 문제에서 최소공배수에 대한 설명은 주어졌지만, 우리는 위 소스코드에서 만든 GCD함수에 대해서 알아야 합니다.

 

우선 최소공배수와 최대공약수를 구하는 식으로 인해 두 수에서는 "최소공배수 = 두 수의 곱 / 최대공약수" 라는 공식이 도출됩니다. 최소공배수는 lcm으로 표현하며, 최대공약수는 gcd(Greatest Common Divisor)로 표현합니다. 즉, 우리가 구해야 하는 값은 배열 arr에 담긴 수들의 최소공배수를 구하는 것이기 때문에 "최소공배수 = n 수의 곱 / 최대공약수"의 식으로 볼 수 있습니다.

 

그렇다면 우리는 최대공약수를 구하면 최소공배수를 구할 수 있습니다. 이때 최대공약수를 구하기 위해 사용하는 것이 gcd함수이고, 이는 유클리드 호제법이라 불리는 유명한 알고리즘 중 하나입니다. 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로 더 자세한 내용은 따로 찾아보시는 것을 권장드립니다.

 

이제 입출력 예를 통해 살펴보겠습니다. [2, 6, 8, 14]가 arr로 주어졌을 때 실행하면 answer에는 2가 들어가고, 6부터 반복문을 돕니다. gcd변수에는 GCD함수를 2와 6으로 실행시킨 값을 넣어줍니다. GCD로 가서 실행하면 Max는 6 Min은 2가 들어가며 r은 0이 나오므로 Min값인 2를 리턴합니다. gcd는 2가 되고, lcm은 2 * 6 / 2가 됩니다. 계산하면 6이 나오고 이를 answer에 넣습니다. 이 과정을 arr의 끝까지 돌립니다. 중간과정을 스킵하며 살펴보면 [6, 8] 끼리 GCD를 실행하여 r이 2가 나와 else로 가기 때문에 재귀적으로 실행하여 [6, 2]로 다시 실행됩니다. 여기서 lcm은 6 * 8 / 2로 24가 나오고 다시 answer로 넣고 마지막 회차를 돌립니다. [24, 14]로 GCD를 돌리면 [14, 10]으로 재귀, [10, 4]로 재귀, [4, 2]로 재귀하여 Min으로 2가 나오고 24 * 14 / 2를 실행하여 168이라는 결과가 나오게 됩니다.

 

<NEXT>

이번에는 gcd와 lcm의 개념, 그리고 유클리드 호제법에 대해서 이야기를 하며 내용이 좀 길어졌습니다. 하지만 언젠가는꼭 짚고 넘어가야 하는 부분이기 때문에 이정도면 나름 잘 끊었다고 생각합니다. 오늘 다룬 문제는 정답률 70%의 연습문제 "N개의 최소공배수" 입니다. 다음에는 Summer/Winter Coding(~2018) 문제인 "점프와 순간이동" 문제를 다뤄보도록 하겠습니다. 감사합니다.