프로그래머스 알고리즘 고득점 Kit - 완전탐색

최소직사각형

- 명함들의 가로 세로 길이가 주어지고, 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 구하는 것

- 명함을 가로로/세로로 눕힐 수 있음!

int solution(vector<vector<int>> sizes) {
    int max_w = 0, max_h = 0, min_area = 0;
    for(vector<int> size : sizes) {
        // 가로로 넣었을 때
        int tmp_w1 = max(max_w, size[0]);
        int tmp_h1 = max(max_h, size[1]);
        // 세로로 넣었을 때
        int tmp_w2 = max(max_w, size[1]);
        int tmp_h2 = max(max_h, size[0]);
        
        if(tmp_w1*tmp_h1 < tmp_w2*tmp_h2) {
            min_area = tmp_w1*tmp_h1;
            max_w = tmp_w1;
            max_h = tmp_h1;
        } else {
            min_area = tmp_w2*tmp_h2;
            max_w = tmp_w2;
            max_h = tmp_h2;
        }
    }
    
    return min_area;
}

// 처음엔 이렇게 비효율적으로 했는데

int solution(vector<vector<int>> sizes) {
    int max_w = 0, max_h = 0;
    for(vector<int> size : sizes) {
        max_w = max(max_w, max(size[0], size[1])); // 긴 변만 오도록
        max_h = max(max_h, min(size[0], size[1])); // 짧은 변만 오도록
    }
    
    return max_w*max_h;
}

// 애초에 이렇게 긴 변끼리 / 짧은 변끼리 묶어서 해버리면 되더라

 

모의고사

- 각 학생의 정답 찍는 방식이 존재할 때, 가장 많이 답을 맞춘 학생을 구하는 문제

- 미리 벡터를 정의해두고, 인덱스로 접근하는 방식으로 ㄱㄱ (나머지 연산 활용)

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> stud1 = {1,2,3,4,5};
    vector<int> stud2 = {2,1,2,3,2,4,2,5};
    vector<int> stud3 = {3,3,1,1,2,2,4,4,5,5};
    vector<int> scores(3);
    
    for(int i=0; i<answers.size(); i++) {
        if(answers[i] == stud1[i%stud1.size()]) scores[0]++;
        if(answers[i] == stud2[i%stud2.size()]) scores[1]++;
        if(answers[i] == stud3[i%stud3.size()]) scores[2]++;
    }

    int max_cnt = max(scores[0], max(scores[1], scores[2]));
    for(int i=0; i<3; i++) {
        if(max_cnt == scores[i]) answer.push_back(i+1);
    }
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

소수 찾기

- 문자열 numbers가 주어졌을 때 문자 재조합해서 만들 수 있는 소수의 개수

- 소수인지 check하는 방법

bool not_sosu[10000000] = { false, };

void checkSosu() {
    not_sosu[0] = not_sosu[1] = true;
    for(int i=2; i<5000000; i++) {
        if(not_sosu[i]) continue;
        for(int j=i*2; j<10000000; j+=i) not_sosu[j] = true;
    }
}

// 에라토스테네스의 체 방식을 사용하려 했는데, 불필요하게 반복문을 돌림

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

// 엄청 크지 않은 테스트케이스들에 대해서는 이렇게 매번 isPrime check 해주는게 더 좋음 (실제로 속도 개선 큼)

 

- next_permutation 사용하지 않은 풀이

vector<string> makeNum(string s) {
    // 기본으로 빈 문자열 리턴
    if(s.length()==0) return vector<string>(1, "");
    
    // s[1:]로 만들 수 있는 부분 문자열 전부 받아옴
    vector<string> answer;
    vector<string> tmp = makeNum(s.substr(1));
    // 각 경우에서 s[0]을 고려함
    for(string t : tmp) {
        answer.push_back(t); // s[0] 삽입 x
        for(int i=0; i<=t.length(); i++) {
            answer.push_back(t.substr(0,i)+s[0]+t.substr(i));
        }
    }
    
    return answer;
}

int solution(string numbers) {  
    vector<string> num_str = makeNum(numbers);
    set<int> num;
    for(string s : num_str) if(s.length()>0) num.insert(stoi(s));
    
    int answer = 0;
    for(int i : num) if(isPrime(i)) answer++;
    
    return answer;
}

// 재귀문을 이용해 가능한 모든 문자열을 만든 다음, stoi() 씌워가지고 계산

 

- c++ algorithm 헤더에는 n개의 원소의 순열 구할 수 있는 next_permutation 함수 존재, 시작과 끝 iterator 건네주면 됨

https://mjmjmj98.tistory.com/38

[C++ / Algorithm] 순열(next_permutation) 사용 방법과 조합(Combination) 구하기

- 오름차순으로 정렬된 값을 가진 컨테이너만 사용 가능

- 기본적으로 오름차순으로 순열을 생성함

- string도 iterator를 가짐

int solution(string numbers) {  
    set<int> num;
    int answer = 0;
    sort(numbers.begin(), numbers.end());
    
    do {
        for(int i=0; i<numbers.size(); i++) {
            num.insert(stoi(numbers.substr(i)));
        }
    } while(next_permutation(numbers.begin(), numbers.end()));
    
    for(int n : num) if(isPrime(n)) answer++;
    
    return answer;
}

// 5개의 permutation 조합은 4개 permutation 조합을 모두 포함할 것

// 따라서 전체의 permutation을 구한 뒤 substring 구하면 substring의 permutation 전부 포함될 듯

 

피로도

- [최소 필요 피로도, 소모 피로도] 쌍이 주어질 때, 유저가 탐험 가능한 최대 던전 수를 구하는 문제

- 최소 필요 피로도>=소모 피로도 조건 만족

 

- algorithm 헤더의 max_element는 시작/끝 iterator를 건네주면 가장 큰 값을 가리키는 iterator를 반환

int sol(int k, vector<vector<int>> dungeons) {
    if(dungeons.empty()) return 0;
    
    vector<int> nums;
    for(int i=0; i<dungeons.size(); i++) {
        vector<int> dungeon = dungeons[i];
        if(k >= dungeon[0]) {
            // 추가 탐험 가능한 던전 있으면 ㄱㄱ
            vector<vector<int>> tmp = dungeons;
            tmp.erase(tmp.begin()+i);
            nums.push_back(1+sol(k-dungeon[1], tmp));
        }
    }
    if(nums.empty()) return 0;
    return *max_element(nums.begin(), nums.end());
}

int solution(int k, vector<vector<int>> dungeons) {
    return sol(k, dungeons);
}

// recursion으로 구해보았다 (dungeons 수가 8개이므로 나름 효율적)

// 현재 상황에서 선택 가능한 던전들을 각각 골랐을 때의 시나리오를 고려하여 최적의 선택을 함

 

- 마찬가지. 완전탐색 제목에 걸맞게 모든 순열을 구해놓고서 최대 던전 수를 구하면 되겠네

int solution(int k, vector<vector<int>> dungeons) {
    vector<int> nums;
    sort(dungeons.begin(), dungeons.end());
    
    do {
        int hp = k;
        int num = 0;
        for(vector<int> dungeon : dungeons) {
            if(hp >= dungeon[0]) {
                hp -= dungeon[1];
                num++;
            }
        }
        nums.push_back(num);
    } while(next_permutation(dungeons.begin(), dungeons.end()));
    
    return *max_element(nums.begin(), nums.end());
}

 

전력망을 둘로 나누기

- n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있을 때, 어떤 전선을 끊어야 두 서브트리의 송전탑 개수 차이가 최소가 되는지 구하는 문제

- 서브트리의 노드 개수는 dfs/bfs로 구할 수 있고, 각 전선을 끊는 모든 경우를 완전탐색한다

vector<int> graph[100];
bool visited[100] = { false };
int nodes = 0;

void dfs(int x) {
    nodes++;
    visited[x] = true;
    
    for(int neighbor : graph[x]) {
        if(!visited[neighbor]) dfs(neighbor);
    }
}

int solution(int n, vector<vector<int>> wires) {
    int min_diff = n;
    
    for(vector<int> wire : wires) {
        for(vector<int> w : wires) {
            if(w == wire) continue;
            // 인접 노드 저장
            graph[w[0]-1].push_back(w[1]-1);
            graph[w[1]-1].push_back(w[0]-1);
        }
        dfs(0);
        int diff = nodes>n-nodes ? 2*nodes-n : n-2*nodes;
        if(min_diff>diff) min_diff = diff;   
        
        // 초기화
        for(int i=0; i<100; i++) {
            graph[i].clear();
            visited[i] = false;
        }
        nodes = 0;
    }
    
    return min_diff;
}

 

- 트리: 사이클이 없는 연결 그래프, 어떤 두 노드를 연결하는 간선이 정확히 하나 존재하며, 이 간선을 제거하면 트리는 두 개의 독립적인 서브트리로 분리됨

- 이걸 활용해 dfs 한 번만으로 야무지게 푸는 풀이를 발견

vector<int> graph[101];
int siz[101]; // 현재 노드를 루트로 하는 서브트리 크기

void dfs(int cur, int prev) {
    siz[cur] = 1;
    for(int nxt : graph[cur]) {
        if(nxt == prev) continue; // 원래 노드 돌아가지 않게
        dfs(nxt, cur);
        siz[cur] += siz[nxt];
    }
}

int solution(int n, vector<vector<int>> wires) { 
    for(vector<int> wire : wires) {
        graph[wire[0]].push_back(wire[1]);
        graph[wire[1]].push_back(wire[0]);
    }
    
    dfs(1,-1);
    
    int min_diff = n;
    for(int i=1; i<=n; i++) {
        for(int j : graph[i]) {
            int diff = 2*siz[j] - n;
            if(diff<0) diff = diff*-1;
            min_diff = min(min_diff, diff);
        }
    }
    return min_diff;
}

 

모음 사전

- A, E, I, O, U만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어 수록

- A, AA, AAA, AAAA, AAAAA, AAAAE, ... , UUUUU 순서

- 로직은 간단, 각 자릿수마다 1씩 더하고 / A가 아닌 문자열 만날 경우 서브 케이스들을 전부 더해나가는 식으로 ㄱㄱ

int solution(string word) {
    // A4 = 1+5*A3 = 781 , A _ _ _ _
    // A3 = 1+5*A2 = 156 , A _ _ _
    // A2 = 1+5*A1 = 31 , A _ _
    // A1 = 1+5*A0 = 6 , A _
    // A0 = 1
    // I = A4 + A4 + 1(I인 경우)
    // EIO = A4 + 1(E인 경우) + A3 + A3 + 1(EI인 경우) + A2 + A2 + A2 + 1(EIO인 경우)
    // AAAE = 1(A인 경우) + 1(AA인 경우) + 1(AAA인 경우) + A1 + 1(AAAE인 경우)
    // AAAAE = 1(A) + 1(AA) + 1(AAA) + 1(AAAA) + A0 + 1(AAAAE)
    
    int n = 0;
    int A[5] = {781, 156, 31, 6, 1};
    char alpha[5] = {'A', 'E', 'I', 'O', 'U'};
    
    for(int i=0; i<word.length(); i++) {
        n++; // 각 자릿수
        int j;
        for(j=0; j<5; j++) if(alpha[j] == word[i]) break;
        n += A[i]*j;
    }
    
    return n;
}

// 거진 수학 문제?