[C++로 풀이] 소수 만들기(DFS, 조합, next_permutation)⭐⭐

Date: 2021.02.05 Updated: 2021.02.05

카테고리: Programmers

📌 소수 만들기

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

✈ DFS (nC3 조합)

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool Prime[3001];

bool isPrime(vector<int> three){
    int sum = three[0] + three[1] + three[2];

    if (Prime[sum]) return true;
    else return false;
}

void DFS(vector<int>& nums, vector<int> three, int& answer, int start, int depth){
    if (depth == 3){
        if (isPrime(three))
            answer++;
        return;
    }

    // 👇 조합의 특징
    // a가 등장했다면 그 다음엔 b,c,d 에서만 등장할 수 있다.
    // a는 다시는 한번 등장했다면 다시는 등장할 수 없다.
    for (int i = start; i < nums.size(); i++){
        three[depth] = nums[i];
        DFS(nums, three, answer, i + 1, depth + 1);
    }
}

int solution(vector<int> nums){
    int answer = 0;

    for (int i = 2; i < 3001; i++)
        Prime[i] = true;
    for (int i = 2; i < 3001; i++){
        if (Prime[i]){
            for (int j = i * i; j < 3001; j += i)
                Prime[j] = false;
        }
    }

    vector<int> three(3);
    DFS(nums, three, answer, 0, 0);

    return answer;
}

nums.size()를 n이라고 했을 때 위 문제는 nums 에서 nC3 개의 모든 조합을 구한 후 이 조합의 합이 소수인지를 확인 하면 되는 문제다.

모든 조합의 경우를 다 구하면 시간초과가 나지 않을까 싶었는데 다행히 나진 않았다. nums의 최대길이인 1000으로 1000C3 구하는 정도는 시간초과가 나지 않는다.

(C++) 조합(Combination)을 구현하는 여러가지 방법

nums의 최대 길이를 대충 3000 으로 잡고 이를 바탕으로 1 에서 3000 까지의 인덱스 중에서 소수인 것만 True를 표시하는 배열 Prime을 만든다.
- 에라토스테네스의 체를 이용함
DFS 를 통하여 nums의 모든 nC3 개의 조합을 전부 검사한다.
- 완성된 이 3개의 조합의 합이 소수라면 answer를 1만큼 더한다.

조합의 DFS 과정 eX) [1, 2, 7, 6, 4]
- 1 👉 12 👉 127
- 1 👉 12 👉 126
- 1 👉 12 👉 124
- 1 👉 17 👉 176
- 1 👉 17 👉 174
- 1 👉 16 👉 164
- 2 👉 76 👉 276
- 2 👉 74 👉 274
- 2 👉 64 👉 264
- 7 👉 76 👉 764

최종적으로 answer는 서로 다른 3개를 골라 더했을 때 소수가 되는 모든 경우의 개수가 된다.

✈ (에라토스테네스의 체)로 효율적으로 소수 체크

bool Prime[3001];
//...

    // ✨에라토스테네스의 체✨
    for (int i = 2; i < 3001; i++)
        Prime[i] = true;
    for (int i = 2; i < 3001; i++){
        if (Prime[i]){
            for (int j = i * i; j < 3001; j += i)
                Prime[j] = false;
        }
    }

에라토스테네스의 체 👉 초기화를 싹 true로 시작한 후, 모든 배수들을 전부 false 처리해 나간다. 최종적으로 소수인 것만 true가 되게끔!

모든 수에 일단 true를 체크한다.
2 부터 차례 차례 검사한다.
- true 체크되어 있는 수라면 소수다.
  - 그 소수의 제곱들을 전부 false로 체크한다. (약수에 그 소수가 포함된다는 것이므로.)
    - ex) 5는 소수니까 25부터 시작하여 25, 125, 625, …. 전부 소수 아닌 것으로 체크함.
    - ex) 2는 소수니까 2를 제외한 모든 짝수는 소수 아닌 것으로 체크됨.

🚀 다른 풀이

✈ 반복문 풀이

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

using namespace std;

bool Prime[3001];
int solution(vector<int> nums) {
    int answer = 0;

    for (int i = 2; i < 3001; i++)
        Prime[i] = true;
    for (int i = 2; i < 3001; i++){
        if (Prime[i]){
            for (int j = i * i; j < 3001; j += i)
                Prime[j] = false;
        }
    }

    for(int i = 0; i < nums.size(); i++)
        for(int j = i + 1; j < nums.size(); j++)
            for(int k = j + 1; k < nums.size(); k++){
                if(Prime[nums[i] + nums[j] + nums[k]])
                    answer++;
            }
    return answer;
}

어차피 딱 3개만 뽑는 것이므로 3중 for문을 사용하여 뽑을 수도 있다. “ABCDE”를 예시로 들자면 첫 번째에서 A 를 뽑았고 B 를 뽑지 않기로 했다면 그 다음은 CDE 에서 2개를 뽑아야 한다. C를 뽑고 D를 뽑지 않기로 했다면 E를 뽑는다. 즉, 뽑든 안뽑든 한번 결정하고 지나간 것은 다신 보지 않는다. 따라서 두번째 for문의 반복은 첫번째 for문에서 살핀 것의 다음 것(i + 1)부터, 세번째 for문의 반복은 두번재 for문에서 살핀 것의 다음 것(j + 1)부터 돌리면 된다.

✈ next_permutation 사용

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool Prime[3001];

int solution(vector<int> nums) {
    int answer = 0;

    for (int i = 2; i < 3001; i++)
        Prime[i] = true;
    for (int i = 2; i < 3001; i++){
        if (Prime[i]){
            for (int j = i * i; j < 3001; j += i)
                Prime[j] = false;
        }
    }
    
    int sum = 0;

    vector<bool> comb_bool(nums.size(), true);
    for(int i = 0; i < nums.size() - 3; i++)
        comb_bool[i] = false;
    
    do{
        sum = 0;
        for(int i = 0; i < comb_bool.size(); i++){
            if (comb_bool[i])
                sum += nums[i];
        }
        
        if (Prime[sum]) 
            answer++;
        
    }while(next_permutation(comb_bool.begin(), comb_bool.end()));

    return answer;
}

    // nC3 조합 구하기 
    int sum = 0;
    vector<bool> comb_bool(nums.size(), true); // 3개의 true를 뒤에 
    for(int i = 0; i < nums.size() - 3; i++)
        comb_bool[i] = false;
    
    do{
        sum = 0;
        for(int i = 0; i < comb_bool.size(); i++){
            if (comb_bool[i]) // true와 일치하는 것
                sum += nums[i];
        }
        
        if (Prime[sum]) 
            answer++;
        
    }while(next_permutation(comb_bool.begin(), comb_bool.end()));

순서 신경 안쓰고 next_permutation을 사용한 조합 구현. 어차피 3 개 조합의 합만 구하면 되니까 순서는 중요치 않아 true 3개를 뒤에다 배치.

next_permutation으로 조합을 구현하는 자세한 설명은 이 포스트 참고

✈ prev_permutation 사용

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool Prime[3001];

int solution(vector<int> nums) {
    int answer = 0;

    for (int i = 2; i < 3001; i++)
        Prime[i] = true;
    for (int i = 2; i < 3001; i++){
        if (Prime[i]){
            for (int j = i * i; j < 3001; j += i)
                Prime[j] = false;
        }
    }
    
    int sum = 0;
    vector<bool> comb_bool(nums.size(), false);
    for(int i = 0; i < 3; i++)
        comb_bool[i] = true;
    
    do{
        sum = 0;
        for(int i = 0; i < comb_bool.size(); i++){
            if (comb_bool[i])
                sum += nums[i];
        }
        
        if (Prime[sum]) 
            answer++;
        
    }while(prev_permutation(comb_bool.begin(), comb_bool.end()));

    return answer;
}

    int sum = 0;
    vector<bool> comb_bool(nums.size(), false);
    for(int i = 0; i < 3; i++) // 앞에 3개를 true로
        comb_bool[i] = true;
    
    do{
        sum = 0;
        for(int i = 0; i < comb_bool.size(); i++){
            if (comb_bool[i])
                sum += nums[i];
        }
        
        if (Prime[sum]) 
            answer++;
        
    }while(prev_permutation(comb_bool.begin(), comb_bool.end()));

prev_permutation으로 조합을 구현하는 자세한 설명은 이 포스트 참고

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️