유클리드 알고리즘

종종 백준 문제를 풀다가, 수학문제를 만나면 골머리를 앓곤 한다. 특히, 이산수학의 경우 너무 대충공부한 나머지(ㅠㅠ)
나를 당황하게 하는데 이런 문제를 방지하고자 앞으로 종종 이산수학 관련 내용들도 포스팅할 예정이다.

어떤 두 수의 최대 공약수를 알 수 있는 방법은 무엇일까?

인류 최초의 알고리즘인 "유클리드 알고리즘(Eucleadian Algorithm)"이 존재한다.
내가 직접 증명을 할라면 할 수 있겠지만,, 그것까지 적기엔 너무 귀찮으므로 위키피디아를 인용한다.

수학과 안친한 나 포함 많은 사람들이 살짝(?) 어지러울 수도 있겠지만, 말로 풀어쓰면 별 거 아니다.

정수 a,b의 최대 공약수는 b와 a%b와의 최대 공약수와 같다. 

꽤나 단순한지 않은가? 그리고 척 보면 오는 느낌이 있다... 바로 재귀적으로 연산할 수 있어보인다는 것.

int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}

실제로 코드로 나타내어도 상당히 간단한 것을 볼 수 있다.