약수 알고리즘

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
    https://github.com/AeroCodeX/

성능은 중요해

아무런 고려없이 약수 알고리즘을 만든다면 아래와 같지 않을까.

아무리 심플한게 좋다지만, 이건 좀 과한 듯 싶다.

이 심플한 알고리즘은 v = 1,000,000,000 기준으로 평균 4208 ms가 걸렸으며,

전체 연산량이 입력값에 대해 선형으로 증가하므로, 시간복잡도는 O(n)이다.

입력값이 작은 상황에서는 괜찮겠지만, 입력값이 크거나 타임 크리티컬한 상황에서는 절대 사용하면 안된다.

상당한 개선이 필요해보인다.

음.. 전체 연산량을 줄일 수 있는 방법은 없을까?

있다. 약수의 정의를 생각하면 좀 더 빠르게 동작하는 약수 알고리즘을 구현할 수 있다.

정수 V, A, B에 대하여 위의 등식이 성립하면 A, B는 V의 약수라고 한다.

여기서 좀 더 생각해보자.

A가 증가하면 등식을 맞추기 위해 B는 감소할 것이고,

A와 B가 같은 값을 가질 때 교차할것이며, 

교차점을 기준으로 y축 대칭이다.

정리하자면, V의 제곱근을 넘어서 얻은 해답은 중복이라는 것이다.

예를 들면 아래와 같은 상황이다.

(A, B) -------- (V, V) -------- (B, A)    // 입력값이 V^2 일 때,

(2, 8) -------- (4,  4) -------- (8, 2)    // 입력값이 16일 때,

자, 제곱근 이후의 해답은 중복임을 알았기 때문에 검사해야 할 범위가 루트 수준으로 줄었다.

위의 키 포인트를 이용해서 더욱 빠른 약수 알고리즘을 구현해보자.

C++에서 기본적으로 제공하는 sqrt 함수가 있지만, 

입력을 정수로 한정지으면 9행처럼 구현하는 것이 훨씬 빠르다.

위 함수는 v = 1,000,000,000 기준으로 평균 0.328 ms가 걸린다.

제곱근 까지만 조사하므로, 시간 복잡도 또한 O(log n) 이다!