[cppchallenge] 7. 친화수 짝 출력 프로그램 구현하기
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. 문제
친화수 짝 출력 프로그램 구현하기
1000000보다 작은 모든 친화수 짝을 출력하라.
2. 풀이(1)
필요한 코드 구조는 아래와 같다.
친화수 짝 구하는 부분+ 답 출력하는 부분
출력 부분과 소수 연산 부분을 각각 따로 함수로 처리하기로 했다.
2.1. I/O
친화수는 두 수의 쌍이 있을 때, 한 수의 진약수의 합이 다른 수와 같은 두 수를 의미한다. 예시로 220의 진약수의 합은 284이고, 284의 진약수의 합은 220이므로 두 수는 친화수이다.
그러므로 양의 정수로 값이 정해져 있고, 1.0 * 10^6이 범위로 설정되어 때문에 입력값, 출력값을 int로 설정할 것이다.
2.2. 연산
해당 수를 구하기 위해 입력값까지 수의 진약수의 합을 담은 배열을 만든 뒤, 해당 배열을 돌며 같은 값이 있는지 확인하는 것이다. 이 때 진약수의 합을 구하는 건 과잉수를 구하는 과정과 동일한 부분이 있으므로 과잉수를 계산할 때처럼 각 수의 약수 합을 저장하는 배열을 만든 후, 각 수의 배수에 자신을 더한다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include <iostream>
#include <vector>
void set_divorsor_sum(int limit, std::vector<int>& divisor_sum) {
for(int i = 2; i <= limit; ++i) {
for(int j = i * 2; j <= limit; j += i) {
divisor_sum[j] += i;
}
}
}
void get_amicable_numbers(int limit, std::vector<int>& divisor_sum) {
set_divorsor_sum(limit, divisor_sum);
for(int i = 2; i < limit; ++i) {
int j = divisor_sum[i];
if(j > i && j <= limit && divisor_sum[j] == i) {
std::cout << i << " " << j << '\n';
}
}
}
int main() {
int limit = 1000000;
std::vector<int> divisor_sum(limit + 1, 1);
get_amicable_numbers(limit, divisor_sum);
return 0;
}진약수의 값을 미리 계산했으므로, 친화수를 찾는 부분을 이중 반복문을 돌리지 않고 값을 찾아 비교하는 것만으로 해결할 수 있었다.
i < j로 중복 방지를 설정하고, 다른 조건문으로 범위 설정 및 검증 과정도 거쳤다.
시간복잡도는 O(nlogn)이다.
3. 코드 수정
핵심 로직의 시간복잡도가 아닌 디테일을 수정하려고 한다.
3.1. I/O
int로도 범위가 안정적이지만, 양수 처리를 안정적으로 하기 위해 unsigned int로 하는 게 오히려 나을 수 있겠다라는 생각이 들었다.
3.2. 연산 방법
핵심 로직은 크게 수정하지 않았다.
3.3. 구현
배열을 설정할 때 divisor_sum[0] = 0으로 명시적으로 설정해 의미를 명확하게 한다.
3.4. 결론
수정한 전체 코드는 아래와 같다.
#include <iostream>
#include <vector>
void set_divorsor_sum(unsigned int limit, std::vector<unsigned int>& divisor_sum) {
for(unsigned int i = 2; i <= limit; ++i) {
for(unsigned int j = i * 2; j <= limit; j += i) {
divisor_sum[j] += i;
}
}
}
void get_amicable_numbers(unsigned int limit, std::vector<unsigned int>& divisor_sum) {
set_divorsor_sum(limit, divisor_sum);
for(unsigned int i = 2; i < limit; ++i) {
unsigned int j = divisor_sum[i];
if(j > i && j <= limit && divisor_sum[j] == i) {
std::cout << i << " " << j << '\n';
}
}
}
int main() {
const unsigned int limit = 1000000;
std::vector<unsigned int> divisor_sum(limit + 1, 1);
divisor_sum[0] = 0;
get_amicable_numbers(limit, divisor_sum);
return 0;
}자료구조를 unsigned int로 변경해 오버플로우를 방지하고 양수임을 명시했다.
limit 변수를 상수로 변경했다.
divisor_sum[0]을 설정함으로써 0번 인덱스의 의미를 명확히 했다.
4. 후기
약수임을 탐색하면서 동시에 약수 합을 구하는 방법도 중요하지만 로직을 사용하여 친화수를 찾는 반복문의 시간복잡도를 줄이는 게 핵심인 문제라고 생각한다. 그리고 단순히 범위 안에 들어간다고 안전하게 int로 사용해도 되지만, 해당 값이 양수라는 것을 명시하는 의미로도 unsigned를 붙이는 것이 코드 가독성에 좋으므로 해당 값의 범위 뿐만 아니라 안전성과 가독성도 고려하여 데이터 타입을 설정해야겠다는 생각이다.