유클리드 호제법 (Euclidean Algorithm) 이란? 두 개의 자연수의 최대공약수(GCD) 를 빠르게 찾는 알고리즘이다. 유클리드 호제법이 유명한 또 다른 이유는, 이 방법이 인류 최초의 알고리즘이라고 소개되고 있기 때문이다. 최대공약수를 찾는 알고리즘은 여러가지가 있겠지만, 시간복잡도 면에서 가장 훌륭한 알고리즘이기 때문에 PS 과정에서 필요하다면 적극 활용하는 것을 추천한다. 계산 과정 유클리드 호제법은 매우 단순하다. 자연수 A, B가 있다고 가정하고, 다음과 같은 과정을 반복하기만 하면 된다. (1) A를 B로 모듈러 연산한다. (A % B) (2) 만약 나머지가 0이라면, B가 최대 공약수이다. (3) 만약 나머지가 0이 아니라면, A를 B로 바꾸고, B를 나머지로 바꾼다. 만약 A =..

1. 문제 2. 접근 방법 '어떤 수가 가지고 있는 약수를 빠르게 찾는 알고리즘' 을 모르면 해결이 쉽지 않은 문제이다. 나도 이 알고리즘을 몰랐기 때문에, 처음에는 시간 초과를 겪어 당황스러울 수밖에 없었다. 이 문제를 접근하는 방법은 다음과 같다. (1) N개의 숫자를 대상으로, N - 1 만큼 숫자 간의 차이들을 구한다. (2) 이 N - 1개의 '차이'들 중, 가장 작은 값을 찾는다. (3) 위에서 구한 가장 작은 값을 대상으로, 1을 제외한 모든 약수를 구한다. (4) 위에서 구한 모든 약수 중, 전체 숫자를 나눠봤을 때 0으로 나누어 떨어지는 약수들만 출력한다. 예시를 들어보자. 다음과 같이 9, 23, 58 의 3개의 숫자가 있다고 가정해보겠다. 그렇다면 위와 같이, 3개의 숫자들의 차이는 ..