[알고리즘] 효율적으로 약수를 찾는 알고리즘

코딩테스트 문제 중, 가끔 수학적인 기초를 묻는 문제에 약수, 배수 등의 문제가 출제된다.

이러한 유형의 문제를 접해본 경험이 없는 사람들은

최악의 시간복잡도를 갖는, 모든 경우를 찾는 순차적인 알고리즘으로 문제를 풀게 된다.

그러므로 PS를 준비하는 사람이라면 '모든 약수를 찾는 효율적인 알고리즘' 정도는 익혀두는 것이 좋다.

 

 

가장 단순하게 약수를 찾는 알고리즘

가장 단순한, 누구나 쉽게 생각할 수 있는 방법을 고안해보자.

만약 10의 약수를 찾는다고 했을 때, 1~10까지의 수 중에서,

10을 0으로 나누어 떨어지게 하는 수를 찾는 알고리즘을 생각할 수 있을 것이다.

 

10 % 1 = 0

10 % 2 = 0

10 % 3 = 1

10 % 4 = 2

10 % 5 = 0

10 % 6 = 4

10 % 7 = 3

10 % 8 = 2

10 % 9 = 1

10 % 10 = 0

 

이렇게 순차적으로 접근했을 때, 10이 0으로 나누어 떨어지게 하는 수는 1, 2, 5, 10 이 된다.

그러므로 10의 약수는 1, 2, 5, 10 이다.

이 경우에는, 모든 경우를 탐색하게 되므로 O(N)의 시간 복잡도를 가지게 된다.

그러므로, N이 약 10억 정도만 되어도 PS 문제에서는 시간 초과로 풀 수 없게 되는 문제가 생긴다.

구현 코드는 다음과 같다.

 

#include <iostream>

int main(void)
{
	int N;
	std::cin >> N;

	for (int i = 1; i <= N; i++)
		if (N % i == 0)
			std::cout << i << '\n';

	return 0;
}

 

 

 

효율적으로 약수를 찾는 알고리즘

위에서 비효율적으로 약수를 찾는 알고리즘을 보았으니,

이번에는 효율적으로 약수를 찾는 알고리즘을 알아보겠다.

어떤 아이디어를 적용해야 할까?

 

우리는 약수를 찾을 때, 다음과 같은 사실을 통해 어마무시한 시간 단축을 할 수 있다.

 

"N의 약수를 구할 때는, 1부터 N의 제곱근 까지의 수만 0으로 나누어 떨어지는지 확인하면 된다!"

 

왜 그렇게 되는 것일까?

아래에서 100의 약수를 구하는 사례를 살펴보자.

우리는 제곱근까지만 구하기로 했으니, 1 ~ 10 사이의 수에 대해서, 100이 0으로 나누어 떨어지는지 보면 된다.

 

100 % 1 = 0

100 % 2 = 0

100 % 3 = 1

100 % 4 = 0

100 % 5 = 0

100 % 6 = 4

100 % 7 = 2

100 % 8 = 4

100 % 9 = 1

100 % 10 = 0

 

이를 통해서, 100의 약수는 일단 1, 2, 4, 5, 10 을 갖는다는 것을 알게 되었다.

이제 이 수를 가지고, 놀라운 일을 할 것이다.

바로 100에 이미 구해진 1, 2, 4, 5, 10을 나누는 것이다.

 

100 / 1 = 100

100 / 2 = 50

100 / 4 = 25

100 / 5 = 20

100 / 10 = 10

 

그렇게 되면, 이미 구했던 1, 2, 4, 5, 10 외에 100, 50, 25, 20, 10이 추가로 구해진 약수가 된다는 것을 알 수 있다.

이제, 중복을 제거하고 오름차순으로 순서를 정렬하자.

그럼 다음과 같이, 100의 약수를 모두 구할 수 있다.

 

1, 2, 4, 5, 10, 20, 25, 50, 100

 

이 경우에는 시간 복잡도가 O(√N)이 되므로, 10억의 입력이 들어온다해도, 약 3만번의 연산으로 약수를 구할 수 있다.

그러므로 왠만한 PS 문제에서 시간 초과가 발생하는 일은 없을 것이다.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

int main(void)
{
	std::vector<int> solution;

	int N;
	std::cin >> N;

	for (int i = 1; i <= sqrt(N); i++)
		if (N % i == 0)
		{
			solution.push_back(i);
			if (i != N / i) solution.push_back(N / i);
		}
	std::sort(solution.begin(), solution.end());

	for (auto a = solution.begin(); a != solution.end(); a++)
		std::cout << *a << '\n';

	return 0;
}