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 int로 설정할 것이다.
2.2. 연산
섹시 소수는 차이가 6인 두 소수를 집합으로 한 집합이다. 그러므로 주어진 수 n보다 작은 1~n-1의 범위 중에서 섹시 소수들을 찾아 출력해야 한다. 그러므로 입력값을 받은 후 에라토스테네스의 체를 이용해 소수인지 판정하고, 범위 안에 있는 섹시 소수들을 찾아 출력한다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include <iostream>
#include <vector>
void set_prime(unsigned int n, std::vector<bool>& is_prime) {
is_prime[0] = is_prime[1] = false;
for(unsigned int i = 2; i * i < n; ++i) {
if(is_prime[i]) {
for(unsigned int j = i * i; j < n; j+= i) {
is_prime[j] = false;
}
}
}
}
void get_sexy_primes(unsigned int n, std::vector<bool>& is_prime) {
for(unsigned int i = 2; i < n; ++i) {
if(is_prime[i] && is_prime[i + 6]) {
if(i + 6 >= n) break;
std::cout << i << " " << i + 6 << '\n';
}
}
}
int main() {
unsigned int n;
std::cin >> n;
std::vector<bool> is_prime(n, true);
set_prime(n, is_prime);
get_sexy_primes(n, is_prime);
return 0;
}해당 범위까지 소수인 쌍을 찾은 후 전체탐색을 하는 것이 효율적이라고 판단해서 범위 내 소수 판정을 위해 에라토스테네스의 체를 이용했다.
시간복잡도는 O(nlog(logn))이다.
3. 코드 수정
코드 작성 후 2.2. 단계에서 고민이 생겼다.
나는 일일히 하나씩 계산하는 방법을 사용했지만, 에라토스테네스의 체와 6k ± 1 방법을 사용해보기로 하였다.
3.1. I/O
연산 타입은 일반적인 양의 정수 범위를 표현할 수 있는 unsigned int를 그대로 사용한다.
3.2. 연산 방법
범위 내 소수 식별에는 에라토스테네스의 체가 적합하기 때문에 그대로 사용한다.
3.3. 구현
get_sexy_primes함수의 조건문을 수정했다. 원래 조건문을 사용할 경우, i + 6을 식별하는데 오버플로우가 발생할 수 있기 때문에 반복문의 범위를 수정하고 내부 if문을 제외했다.
void get_sexy_primes(unsigned int n, std::vector<bool>& is_prime) {
for(unsigned int i = 2; i + 6 < n; ++i) {
if(is_prime[i] && is_prime[i + 6]) {
std::cout << i << " " << i + 6 << '\n';
}
}
}
입력값이 너무 크면 메모리 할당이 실패할 수 있으므로 메모리 할당에 제한을 걸어두었다.
int main() {
unsigned int n;
std::cin >> n;
if(n > 20000000) {
std::cout << "The input value is too large. Please enter a small number";
return 1;
}
std::vector<bool> is_prime(n, true);
set_prime(n, is_prime);
get_sexy_primes(n, is_prime);
return 0;
}
3.4. 결론
수정한 전체 코드는 아래와 같다.
#include <iostream>
#include <vector>
void set_prime(unsigned int n, std::vector<bool>& is_prime) {
is_prime[0] = is_prime[1] = false;
for(unsigned int i = 2; i * i < n; ++i) {
if(is_prime[i]) {
for(unsigned int j = i * i; j < n; j += i) {
is_prime[j] = false;
}
}
}
}
void get_sexy_primes(unsigned int n, std::vector<bool>& is_prime) {
for(unsigned int i = 2; i + 6 < n; ++i) {
if(is_prime[i] && is_prime[i + 6]) {
std::cout << i << " " << i + 6 << '\n';
}
}
}
int main() {
unsigned int n;
std::cin >> n;
if(n > 20000000) {
std::cout << "The input value is too large. Please enter a small number";
return 1;
}
std::vector<bool> is_prime(n, true);
set_prime(n, is_prime);
get_sexy_primes(n, is_prime);
return 0;
}
그 외 세 쌍, 네 쌍, 다섯 쌍 등 섹시 소수를 구한다면 get_sexy_primes에서 조건문을 수정하면 된다.
4. 후기
전 문제에서 구현한 소수 식별 함수를 이용한 문제였다. 알고리즘을 잘 판별하는 것 뿐만 아니라 오버플로우, 메모리 할당 같은 다른 상황에서의 디테일도 잘 잡아서 문제를 풀어야 한다는 것을 상기한 문제였다.