[C++] 완전 탐색 모음

42839 소수 찾기 [문제 바로가기]

 

solution

1. numbers로 만들 수 있는 모든 경우의 수에 대한 숫자를 구한다.

2. 중복을 제거한다.

3. 숫자에 대해서 소수인지 판별한다.

 

이때 중복을 제거하기 위해 unique() 함수를 사용한다. 주의할 점은 정렬이 되어 있어야 한다는 것이다.

unique 함수는 중복되지 않은 수를 앞에서부터 정렬하고 중복이 시작되는 배열 주소를 반환한다.

따라서 반환된 주소부터 끝까지 삭제하여 중복을 제거한 배열을 생성할 수 있다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool is_prime(int n) {
    if (n < 2)
        return false;
    
    for(int i = 2;i <= sqrt(n);i++) {
        if (n % i == 0)
            return false;
    }
    
    return true;
}

int solution(string numbers) {
    int answer = 0;
    
    vector<char> num;
    vector<int> valid;
    
    for(int i = 0;i < numbers.size();i++) {
        num.push_back(numbers[i]);
    }
    sort(num.begin(), num.end());
    
    do {
        string temp = "";
        for(int i = 0;i < num.size();i++) {
            temp += num[i];
            valid.push_back(stoi(temp));
        }
    } while(next_permutation(num.begin(), num.end()));
    
    sort(valid.begin(), valid.end());
    valid.erase(unique(valid.begin(), valid.end()), valid.end());
    
    for(int i = 0;i < valid.size();i++) {
        if (is_prime(valid[i])) {
            answer++;
        }
    }
    
    return answer;
}

 

---

42842 카펫 [문제 바로가기]

 

solution

1. yellow 카펫의 약수를 구한다. (ex. 24 = 4 * 6)

2. brown 카펫은 테두리 1줄이기 때문에 yellow 카펫의 약수에 +2를 해준 값이 가로 세로가 된다. (ex. (4+2), (6+8))

3. 이렇게 구한 가로, 세로 값으로 넓이를 구한 후, yellow 카펫을 뺀 값이 brown 카펫의 개수와 맞다면 정답이다.

이때 가로가 세로보다 길거나 같기 때문에 정렬을 해준다.

 

사실 정렬하지 않고 for 문을 1에서 시작하는 것이 아니라 sqrt(yellow) 에서 시작하는 것으로 대체 가능할듯

 

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> solution(int brown, int yellow) {
    vector<int> answer;
    
    for(int i = 1;i <= sqrt(yellow);i++) {
        if (yellow % i != 0)
            continue;
        
        int w = i;
        int h = yellow / i;
        
        int total = (w + 2) * (h + 2);
        if (total - yellow == brown) {
            answer.push_back(w + 2);
            answer.push_back(h + 2);
            break;
        }
    }
    
    sort(answer.begin(), answer.end(), greater<>());
    return answer;
}

---

87946 피로도 [문제 바로가기]

 

solution

1. 던전을 순서대로 탐험하는 가능한 조합을 구한다.

2. 조합에 대해 피로도를 소진하며 탐험을 한다.

3. 최대로 탐험 가능한 던전 수를 구한다.

 

이때 가능한 던전 조합을 구하기 위해 던전의 인덱스를 배열에 넣고 이를 next_permutation 을 통해서 순열을 구했다.

 

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

int solution(int k, vector<vector<int>> dungeons) {
    vector<int> arr;
    vector<vector<int>> valid;
    
    for(int i = 0;i < dungeons.size();i++)
        arr.push_back(i);
    
    do {
        vector<int> temp;
        for(int i = 0;i < arr.size();i++) {
            temp.push_back(arr[i]);
        }
        valid.push_back(temp);
        
    } while(next_permutation(arr.begin(), arr.end()));
    
    int result = 0;
    int tempK = k;
    
    for(int i = 0;i < valid.size();i++) {
        int tmp = 0;
        tempK = k;
        
        for(int len = 0;len < valid[i].size();len++) {
            if (tempK >= dungeons[valid[i][len]][0]) {
                tempK -= dungeons[valid[i][len]][1];
                tmp++;
            }
        }
        
        result = max(result, tmp);
    }
    
    return result;
}

---

86971 전력망을 둘로 나누기 [문제 바로가기]

 

solution

1. 전선을 끊을 수 있는 모든 경우의 수를 구한다.

1-1. 즉 wires 배열을 돌면서 전선 연결을 하나씩 포함하지 않으면 된다.

 

2. 그래프를 연결한다.

2-1. vector 배열을 사용해서 연결되어 있는 전선의 정보를 해당 인덱스 vector 배열에 추가한다.

2-2. 이때 양쪽으로 연결되어 있기 때문에 입력에 대해서 값을 번갈아 가면서 추가해준다.

 

map[wires[i][0]].push_back(wires[i][1]);
map[wires[i][1]].push_back(wires[i][0]);

 

3. 기본 그래프 알고리즘을 사용하여 연결 되어 있는 전선의 개수를 각자 센다.

3-1. 구간이 포함되어 있는 여부를 계산하기 위해 visited 배열로 방문 여부를 체크한다.

 

#include <string>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

int solution(int n, vector<vector<int>> wires) {
    int result = 1e9;
    
    for(int len = 0;len < wires.size();len++) {
        vector<int> visited(n + 1, 0);
        vector<int> map[n + 1];
        
        for(int i = 0;i < wires.size();i++) {
            if (len == i)
                continue;

            map[wires[i][0]].push_back(wires[i][1]);
            map[wires[i][1]].push_back(wires[i][0]);
        }
        
        int firstCnt = 0, secondCnt = 0;
        
        
        // 첫번째 구간 계산
        queue<int> q;
        q.push(1);
        
        while(!q.empty()) {
            int front = q.front();
            q.pop();
                
            visited[front] = 1;
            firstCnt++;
                
            for (int j = 0;j < map[front].size();j++) {
                if (visited[map[front][j]] == 0)
                    q.push(map[front][j]);
            }
        }
        
        // 두번째 구간 계산
        // 이때 첫번째 구간에 포함되지 않는 구간만 계산하기 위해 for문을 돌린다.
        for(int i = 1;i <= n;i++) {
            if (visited[i] != 0) 
                continue;
            
            queue<int> q;
            q.push(i);
            
            while(!q.empty()) {
                int front = q.front();
                q.pop();
                
                visited[front] = 1;
                secondCnt++;
                
                for (int j = 0;j < map[front].size();j++) {
                    if (visited[map[front][j]] == 0)
                        q.push(map[front][j]);
                }
            }
        }

        result = min(result, abs(secondCnt - firstCnt));
    }

    return result;
}

---

 

84512 모음 사전 [문제 바로가기]

 

solution

1. 만들 수 있는 모든 모음 문자열을 구하고 배열에 넣는다.

2. word와 같은 문자열의 인덱스를 찾아 반환한다.

2-1. 이때 find 함수를 사용한다.

 

find(시작, 끝, 타겟) 으로 호출하며 return 값은 첫번째로 찾은 요소의 iterator이다. (주소)

answer = find(arr.begin(), arr.end(), word) - arr.begin();

 

완전 탐색 버전

이때 구현한 버전에서는 맨 처음에 빈 문자열 즉 ""를 배열에 넣는데 이는 길이가 0이라서 유효한 문자는 아니지만

인덱스를 반환할 때 어짜피 1을 더해줘야 하기 때문에 상관없다고 판단하여 예외 처리하지 않았다.

 

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

string temp = "AEIOU";
vector<string> arr;

void getWord(string str) {
    if (str.size() > 5)
        return;
    
    arr.push_back(str);
    for (int i = 0; i < 5;i++) {
        getWord(str + temp[i]);
    }
}

int solution(string word) {
    int answer = 0;
    getWord("");
    
    sort(arr.begin(), arr.end());
    answer = find(arr.begin(), arr.end(), word) - arr.begin();
    
    return answer;
}

 

 

그런데 생각해보면 getWord 함수를 돌리면서 index를 구할 수도 있다.

바로 DFS를 이용하는 것이다

 

DFS 버전

 

#include <string>
#include <vector>
using namespace std;

int len, answer;
string temp = "AEIOU";

void dfs(string str, string target) {
    if (str == target) {
        answer = len;
        return;
    }
    
    if (str.size() > 5)
        return;
    
    len++;
    for (int i = 0; i < 5;i++) {
        dfs(str + temp[i], target);
    }
}

int solution(string word) {
    dfs("", word);
    return answer;
}