최대공약수 구하기

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

최대공약수를 구하는 문제를 푸는데 O(n)의 시간 복잡도로 해결을 했다. 좀 더 효율적인 알고리즘이 있는데 활용을 하지 못하는 것 같아서 구글링을 해서 더 직관적이고 효율적인 알고리즘을 공부해서 소개하고자 한다.

A = B * c + r 일 때, A, B의 최대 공약수는 B, r의 최대 공약수와 같다. 라는 것이다.

전제

1. A와 B의 최대 공약수는 G이다.

2. A = aG, B = bG 일 때 a mod b != 0 이다. (서로소이다.)

증명 순서

1. r = nG 형태로 치환한다.

r = Bc - A = bGc - aG = (bc - a)G

2. r = (bc - a)G, B = bG 일 때 (bc - a) mod b !=0 이면 유클리드 호제법을 증명이 완료된다.

2-1 (bc - a) mod b = 0 이 거짓임을 증명한다.

bc - a = kg, b = hg ( g는 bc - a 와 b의 최대공약수 )

hgc - a = kg

a = kg - hgc = (k - hc)g

a, b는 서로수이기 때문에 g = 1 이다.

따라서 (bc - a) mod b != 0 이다.

유클리드 호제법을 이용하면서 브루드 포트 방식인 O(n)에서 O(log N)으로 개선할 수 있다.

//a > b
    public int gcd(int a, int b){
        if(b == 0) return a;
        return gcd(b, a % b);
    }

정리 노트