JArchive 프로그래밍 일기

문제

최대공약수와 최소공배수 프로그래머스 level1

리뷰

최대공약수는 유클리드 호제법으로 구할 수 있다.

유클리드 호제법은 나머지를 구하는 MOD 연산을 이용한다.

MOD 연산

// MOD 연산 : 나머지를 구하는 연산 
5 % 3 = 2 
// 5를 3으로 나눈 몫은 1 이다. 나머지는 2. 

유클리드 호제법 (Euclidean algorithm)

2개의 자연수에 대해서. a 를 b로 나눈 나머지를 r 이라고 한다면. ( 단, a > b )

a와 b의 최대 공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라 b를 r로 나눈 나머지를 구하는 과정을 반복하여.

나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대 공약수다.

예시를 읽으면 금방 이해된다. 위키백과 유클리드호제법

14와 24의 최대공약수(GCD, Greatest Common Divisor)

// 24와 14의 최대 공약수 구하기.  주의할 점은 a > b 

24 % 14 = 10 
14 % 10 = 4
10 % 4  = 2
4  % 2  = 0

// MOD 연산 결과가 0 이 되면 종료된다. -->  24와 14의 최대공약수는 2 

나머지가 0 일 때, 나누는 수 2가 최대공약수다.

재귀 코드

// 나머지가 0이 나올 때 종료.
int GCD(int a, int b)   // 단, a > b
{
    if (b == 0) return a;
    else return GCD(b, a%b);
}

반복문 코드

int GCD(int a, int b){  // 단, a > b
    int temp = 0;

    while(b){
        temp = a % b;
        a = b;
        b = temp;
    }

    return a;
}

최소공배수 (LCM, Least Common Multiple)

a 와 b의 최소공배수는 최대공약수를 구하면 계산할 수 있다.

LCM =  a * b * GCD(a, b);

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

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

}

vector<int> solution(int n, int m) {
    vector<int> answer;

    // 큰 값을 앞에, 작은 값을 뒤에.
    int gcd_num = gcd(max(n, m), min(n, m));

    answer.push_back(gcd_num);
    answer.push_back((n*m)/gcd_num);

    return answer;
}