이 글에서는 C++을 사용해 배열에 존재하는 소수 쌍(prime pair)의 개수를 구하는 방법을 자세히 알아봅니다. 정수 배열 arr[]가 주어졌을 때, 배열 안에서 만들어질 수 있는 모든 소수 쌍을 찾아야 합니다. 먼저 문제의 예시부터 살펴보겠습니다.
입력 : arr[ ] = { 1, 2, 3, 5, 7, 9 }
출력 : 6
주어진 배열에서 만들 수 있는 소수 쌍은 다음과 같습니다.
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
입력 : arr[] = {1, 4, 5, 9, 11}
출력 : 1문제 해결 접근 방법
브루트 포스(Brute Force) 방식
가장 기본적인 방법인 브루트 포스 방식부터 살펴보겠습니다. 이 방법은 효율성이 떨어지기 때문에, 이후에는 이를 개선한 더 빠른 방법도 함께 다룹니다.
예시
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
int answer = 0; // 소수 쌍의 개수를 세는 카운터 변수
int MAX = INT_MIN; // 최대 원소
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // 각 원소가 소수인지 여부를 나타내는 불리언 배열
memset(prime, false, sizeof(prime)); // 모든 원소를 false로 초기화
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(prime[i] == true && prime[j] == true)
answer++;
}
}
cout << answer << "\n";
return 0;
}출력
6
이 방식에서는 각 원소가 소수인지 여부를 알려주는 bool 배열을 만든 뒤, 가능한 모든 쌍을 하나씩 확인하면서 두 수가 모두 소수인지 검사합니다. 두 수가 모두 소수라면 정답 카운트를 1 증가시키고 다음 쌍으로 넘어갑니다.
하지만 이 방법은 시간 복잡도가 O(N*N)(N은 배열의 크기)이라서 그다지 효율적이지 못합니다. 따라서 지금부터 이 방법을 더 빠르게 개선해 보겠습니다.
효율적인 접근 방법
이 방법에서는 대부분의 코드가 앞선 방식과 동일하지만, 핵심적인 변화는 가능한 모든 쌍을 일일이 확인하는 대신 공식을 사용해 한 번에 계산한다는 점입니다.
예시
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // 배열의 크기
int answer = 0; // 소수 쌍의 개수를 세는 카운터 변수
int MAX = INT_MIN; // 최대 원소
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // 각 원소가 소수인지 여부를 나타내는 불리언 배열
memset(prime, false, sizeof(prime)); // 모든 원소를 false로 초기화
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n; i++){
if(prime[i] == true)
answer++;
}
answer = (answer * (answer - 1)) / 2;
cout << answer << "\n";
return 0;
}출력
6
앞선 방법과 코드가 거의 동일하다는 것을 확인할 수 있습니다. 하지만 복잡도를 크게 줄여준 결정적인 변화는 바로 사용한 공식, 즉 n(n-1)/2입니다. 이 공식을 통해 소수 쌍의 개수를 곧바로 계산할 수 있습니다.
코드 상세 설명
이 코드에서는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용해 배열의 최댓값까지 범위 내의 모든 소수를 미리 표시합니다. 그리고 별도의 bool 배열에 인덱스별로 해당 원소가 소수인지 여부를 기록합니다.
마지막으로 배열 전체를 순회하며 소수의 총 개수를 구한 뒤, n*(n-1)/2 공식을 이용해 가능한 모든 소수 쌍의 개수를 계산합니다. 이 공식 덕분에 시간 복잡도가 O(N)(N은 배열의 크기)까지 크게 줄어듭니다.
결론
이 글에서는 O(n) 시간 복잡도로 배열에 존재하는 소수 쌍의 개수를 구하는 문제를 해결했습니다. 또한 이 문제를 위한 C++ 프로그램과 함께 일반 방식 및 효율적인 방식 등 전체적인 접근 방법도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다.