algorithm

백준 2609번을 풀다가 최대공약수를 구하는 새로운 알고리즘에 대해 공부하게 되었다. 명시적으로 기술된 가장 오래된 최대공약수 구하기 알고리즘이라고 한다. 최대공약수 풀이 유클리드 호제법(알고리즘) 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이...