유클리드 호제법 - 최대 공약수 구하기

소스코드

#include <iostream>
using namespace std;
int gcd(int n, int m){
    int temp;
    while(m){
        temp = n%m;
        n = m;
        m = temp;
    }
    return n;
}

최대 공약수를 구하는 O(log(n+m)) 알고리즘

 기본 생각으로 알고리즘을 짜게 되면 nm의 시간 복잡도가 주어지게 됩니다. 1부터 계속해서 수를 검증해야 하기 때문에 테스트 케이스가 너무 많은 경우 시간이 너무 오래 걸려 문제를 풀 수 없게 됩니다.

 

조금 더 풀어쓰기

 

 위 예시를 봤을 때 나머지가 0이 되는 연산에서의 분모가 최대 공약수가 됩니다. 코딩을 하는게 목적이니 증명에 대해서는 다음에 이야기하겠습니다.

 

최소 공배수를 구하는 경우

유클리드 호제법으로 최대 공약수를 구한 다음 (val1 X val2) / 최소 공배수를 하면 최대 공약수를 구할 수 있습니다.

 

 

 

추천 문제

 

1934번: 최소공배수

2609번: 최대공약수와 최소공배수