프로그래머스 : N개의 최소공배수(lv2) C++

프로그래머스 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

문제 설명

두 수의 최소공배수(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

코드 보기 전 알고 가야 할 알고리즘

유클리드 호제법
유클리드 알고리즘 : 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘이다
호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

 

자세한 내용 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법을 이용한 최대 공약수 구하는 함수

int Gcd(int a, int b)
{
    int A = max(a, b);
    int B = min(a, b);

    while (A % B != 0)
    {
        int R = A % B;
        A = B;
        B = R;
    }
    return B;
}

코드

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

using namespace std;

// 유클리드 호제법
// 유클리드 알고리즘 : 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘이다
// 호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘
// 최대 공약수
int Gcd(int a, int b)
{
    // 최대값 % 최소값을 해야하는데 매개변수로 들어온 값이
    // 어떤게 크고 작은지 모르기때문에 max, min함수를 이용하여 구해준다.
    int A = max(a, b);
    int B = min(a, b);

    while (A % B != 0)
    {
        int R = A % B;	// 나머지를 구해줌
        A = B;		// 큰값을 작은값으로 대입
        B = R;		// 작은값을 나머지로 대입
    }
    
    return B;
}

// 최소 공배수 구하는 함수
int Lcm(int a, int b)
{
    return a * b / Gcd(a, b);
}

// 최소공배수 = 두 수의 곱 / 최대공약수
int solution(vector<int> arr)
{
    // 처음 0번인덱스의 값과 1번인덱스의 값을 계산하고
    // 그이후 계속해서 구해진 최소공배수와 다음 인덱스의 값끼리 계산해야하기 때문에
    // 미리 0번인덱스 값을 넣어줌
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++)
    {
        // 최소 공배소값은 계속해서 갱신된다.
        answer = Lcm(answer, arr[i]);
    }
    return answer;
}

---

최소 공배수 구하는 알고리즘을 찾아보다가 유클리드 호제법이라는 알고리즘이 바로 나와서

해당 알고리즘을 참고해 구현하였다.

덕분에 좋은 알고리즘을 알게 되었고 다음에 할 때는 바로 생각나길...