[cppchallenge] 6. 과잉수 출력 프로그램 구현하기
modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. 코드 수정
3.1. I/O 타입
3.2. 연산 방법
3.3. 구현
3.4. 결론
4. 결론
1. 문제
과잉수 출력 프로그램 구현하기
사용자가 입력한 상한까지의 모든 과잉수와 그 과잉을 출력하라.
2. 풀이(1)
필요한 코드 구조는 아래와 같다.
양의 정수 입력값 받는 부분 + 과잉수 구하는 부분 + 답 출력하는 부분
이전 문제와 마찬가지로 main함수에서 I/O를 해결하고 소수 연산 부분은 따로 함수로 처리하기로 했다.
2.1. I/O
과잉수는 자기 자신을 제외한 모든 양의 약수의 합이 자기 자신보다 큰 양의 정수이다. 또한 과잉은 진약수(자기 자신을 제외한 양의 약수) - 주어진 정수의 값이다.
그러므로 양의 정수로 값이 정해져 있기 때문에 입력값, 출력값을 unsigned int로 설정할 것이다.
unsigned long long이 아닌 unsigned int로 정의하는 이유는 이전 섹시 소수 출력 문제와 동일하게 메모리 이슈이다.
2.2. 연산
과잉수와 과잉을 구하기 위해 우선 해당 수의 약수를 구해야 하고, 진약수들의 합을 구해야 한다. 그러므로 1~n까지의 반복하면서 해당 수가 과잉수인지 판단하고, 과잉수일 경우 진약수들의 합을 구해야 한다.
과잉수인지 판단하기 위해 2~int(sqrt(n))까지 나눠떨어지는 약수들을 구하고, 해당 약수들의 합도 같이 구한다. 이 때 제곱수일 경우 약수는 하나만 더한다. 그리고 구한 합에 +1을 해준 후 해당 수와 대소를 비교한 다음, 과잉수가 맞으면 과잉수를 출력하고 과잉을 구한다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include <iostream>
void find_abundant_numbers(unsigned int n) {
unsigned int sum = 0;
for(unsigned int i = 2; i * i <= n; ++i) {
if(n % i == 0) {
sum += i;
if((n / i) == i) continue;
sum += (n / i);
}
}
sum += 1;
if(sum > n)
std::cout << n << " " << sum - n << '\n';
}
int main() {
unsigned int n;
std::cin >> n;
for(unsigned int i = 1; i < n; i++){
find_abundant_numbers(i);
}
return 0;
}일단 전체탐색을 사용하되 범위를 줄여서 약수를 찾는 방식을 사용했고, 마지막 약수 1은 나중에 더해서 과잉수인지 판단했다.
시간복잡도는 O(n * sqrt(n))이다. 하지만 풀고 나서 생각해보니 n이 커질수록 매우 느려지게 된다.
3. 코드 수정
나는 약수의 합을 구할 때 모든 수의 약수를 다 구했지만, 8 같은 경우는 4의 약수의 합에 추가로 값을 더하면 되는 경우이므로 이와 같이 각 숫자에 대해 그 숫자의 배수들의 약수 합에 기여하는 방식을 적용해보도록 하겠다.
3.1. I/O
연산 타입은 일반적인 양의 정수 범위를 표현할 수 있는 unsigned int를 그대로 사용한다. 다만 unsigned int의 최대값보다 약수들의 합이 커질 수 있으므로 해당 조건에 맞게 범위를 2 * 10^9로 설정했다.
3.2. 연산 방법
각 수의 약수 합을 저장하는 배열을 만든 후, 각 수의 배수에 자신을 더하는 방식으로 작성했다.
#include <iostream>
void set_divorsor_sum(unsigned int n, std::vector<unsigned int>& divorsor_sum) {
std::vector<unsigned int> divorsor_sum(n + 1, 1);
set_divorsor_sum(n, divorsor_sum);
for(unsigned int i = 2; i <= n / 2; ++i) {
for(unsigned int j = i * 2; j <= n; j += i) {
divorsor_sum[j] += i;
}
}
for(unsigned int i = 1; i <= n; ++i) {
if(divorsor_sum[i] > i)
std::cout << i << " " << divorsor_sum[i] - i << '\n';
}
}1~n까지 각 수의 약수 합을 저장하는 배열을 만든 뒤, 1부터 n까지 각 배수에 자신을 더한다.
이 때, 1은 모든 수의 약수이므로 1을 초기값으로 설정했다.
어떤 수의 진약수는 항상 n의 절반 이하이기 때문에 약수를 찾는 i는 n / 2 이하로 설정했다.
자신을 제외하고 i의 배수들에만 i를 더해주어 i가 j의 약수임을 기록한다.
시간복잡도는 O(nlogn)이다.
3.4. 결론
수정한 전체 코드는 아래와 같다.
#include <iostream>
void set_divorsor_sum(unsigned int n, std::vector<unsigned int>& divorsor_sum) {
for(unsigned int i = 2; i <= n / 2; ++i) {
for(unsigned int j = i * 2; j <= n; j += i) {
divorsor_sum[j] += i;
}
}
for(unsigned int i = 1; i <= n; ++i) {
if(divorsor_sum[i] > i)
std::cout << i << " " << divorsor_sum[i] - i << '\n';
}
}
int main() {
unsigned int n;
std::cin >> n;
if(n >= 2000000000) {
std::cout << "The input value is too large. Please enter a small number" << '\n';
return 1;
}
std::vector<unsigned int> divorsor_sum(n + 1, 1);
set_divorsor_sum(n, divorsor_sum);
return 0;
}
4. 후기
약수임을 탐색하면서 동시에 약수 합을 구하는 방법으로 시간복잡도를 줄인 문제였다. 시간이 없다면 일단 무조건 풀어야 하지만 조금이라도 더 나은 방법을 생각해보는 게 좋은 것 같다. 그래도 각 수가 약수로써 몇 개의 수에 영향을 주는지를 생각하고, 해당 수를 더하는 사고방식을 배웠다는 데에 의의를 둔다.