[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 7회차 과제 에디토리얼

7회차 - graph, tree, map and set

 

---

</11723> 집합

https://www.acmicpc.net/problem/11723

다양한 방법으로 풀 수 있는 문제입니다. 

 

1. set을 사용한 풀이

단순히 문제에서 설명하는 대로 코드를 작성하면 됩니다.

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    string op;
    cin >> m;
    set<int> s;

    for (int i = 0; i < m; i++) {
        cin >> op;
        if (op == "add") {
            cin >> n;
            s.insert(n);
        } else if (op == "remove") {
            cin >> n;
            s.erase(n);
        } else if (op == "check") {
            cin >> n;
            if (s.find(n) == s.end()) cout << 0 << '\n';
            else cout << 1 << '\n';
        } else if (op == "toggle") {
            cin >> n;
            if (s.find(n) == s.end()) s.insert(n);
            else s.erase(n);
        } else if (op == "all") {
            s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
        } else if (op == "empty") {
            s = {};
        }
    }
}

2. 배열을 사용한 풀이

1번 방법과 비슷하지만 입력으로 들어오는 수의 범위가 1과 20 사이이기 때문에 굳이 set을 만들지 않고 배열로 해당 원소가 있는지 없는지 체크해주어도 됩니다.

#include <iostream>
#include <set>
using namespace std;

int chk[21];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    string op;
    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> op;
        if (op == "add") {
            cin >> n;
            chk[n] = true;
        } else if (op == "remove") {
            cin >> n;
            chk[n] = false;
        } else if (op == "check") {
            cin >> n;
            if (chk[n]) cout << 1 << '\n';
            else cout << 0 << '\n';
        } else if (op == "toggle") {
            cin >> n;
            if (chk[n]) chk[n] = false;
            else chk[n] = true;
        } else if (op == "all") {
            for (int i = 0; i < 21; i++) chk[i] = true;
        } else if (op == "empty") {
            for (int i = 0; i < 21; i++) chk[i] = false;
        }
    }
}

3. 비트마스킹을 사용한 풀이

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int m, n;
    string op;
    cin >> m;
    int now = 0;

    for (int i = 0; i < m; i++) {
        cin >> op;
        if (op == "add") {
            cin >> n;
            now = now | (1 << (n - 1));
        } else if (op == "remove") {
            cin >> n;
            if ((now & (1 << (n - 1))) != 0) {
                now = now ^ (1 << (n - 1));
            }
        } else if (op == "check") {
            cin >> n;
            if ((now & (1 << (n - 1))) == 0) cout << 0 << '\n';
            else cout << 1 << '\n';
        } else if (op == "toggle") {
            cin >> n;
            now = now ^ (1 << (n - 1));
        } else if (op == "all") {
            now = -1;
        } else if (op == "empty") {
            now = 0;
        }
    }
}

 

---

</1620> 나는야 포켓몬 마스터 이다솜

https://www.acmicpc.net/problem/1620

집합 문제를 빙자한… 빠른 입출력 문제로 유명한 문제입니다.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    map<int, string> num;
    map<string, int> name;
    string input;

    for (int i = 1; i <= n; i++) {
        cin >> input;
        num.insert({i, input});
        name.insert({input, i});
    }

    for (int i = 0; i < m; i++) {
        cin >> input;
        if (input[0] >= 48 && input[0] < 58) {
            cout << num[stoi(input)] << '\n';
        }
        else {
            cout << name[input] << '\n';
        }
    }
}

 

---

</1269> 대칭 차집합

https://www.acmicpc.net/problem/1269

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    set<int> s;
    int x;

    for (int i = 0; i < n; i++) {
        cin >> x;
        s.insert(x);
    }

    for (int i = 0; i < m; i++) {
        cin >> x;
        if (s.find(x) == s.end()) s.insert(x); // 없으면 삽입
        else s.erase(x); // 있으면 삭제
    }

    cout << s.size() << '\n';
}

 

---

</9375> 패션왕 신해빈

https://www.acmicpc.net/problem/9375

경우의 수를 이용하는 맵 문제입니다.

저는 의상의 종류 이름과 개수를 저장하는 맵을 통해 각 의상 종류 별로 몇 개의 의상이 있는지 저장해두고 마지막에 곱셈으로 계산해주었습니다.

아무것도 안 입는 경우, 즉 알몸인 경우는 제외해야 한다는 점만 주의하시면 될 것 같습니다.

#include <iostream>
#include <map>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;  // 테스트 케이스 개수
    cin >> t;

    while (t--) {
        int n;  // 의상 개수
        cin >> n;
        map<string, int> m;  // 의상 종류별 개수를 저장할 맵
        int ans = 1;  // 조합 수 계산을 위한 변수 (곱셈이므로 초기값 1)
        while (n--) {
            string name, type;
            cin >> name >> type;
            if (m.find(type) == m.end()) m.insert({type, 1});  // 새로운 종류이면 초기값 1 삽입
            else m[type]++;  // 기존 종류이면 개수 증가
        }
        for (auto x: m) {
            ans *= x.second + 1;  // 의상 개수 + 1 (선택하지 않는 경우) 곱하기
        }
        cout << ans - 1 << '\n';  // 알몸인 경우 제외
    }
}

 

---

</14675> 단절점과 단절선

https://www.acmicpc.net/problem/14675

단절점과 단절선의 정의는 문제에서 잘 설명되어 있으니까, 이제 트리에서 단절점과 단절선이 뭔지 생각해봅시다.

정점의 수가 n인 트리의 간선의 수는 n-1개 입니다. 그리고 임의의 두 정점을 선택했을 때 그 정점을 잇는 경로는 유일합니다. 즉, 어떤 간선을 제거해도 2개 이상의 그래프로 나뉩니다. 따라서 트리에서 모든 간선은 단절선입니다.

또한 리프 노드는 자식이 없는 정점으로, 하나의 부모만 가집니다. 그렇기 때문에 리프 노드에 연결된 간선은 단 하나이고, 리프 노드가 아닌 노드에 연결된 간선은 2개 이상입니다. 즉, 리프 노드가 아닌 노드를 제거하면 2개 이상의 그래프로 나뉩니다. 따라서 트리에서 단정점은 리프 노드를 제외한 모든 정점이 됩니다.

즉, 이 문제는 리프 노드만 찾으면 되는 문제입니다!

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;  // 트리의 정점 개수
    cin >> n;

    vector<vector<int>> g(n + 1);  // 인접 리스트
    for (int i = 0; i < n - 1; i++) {  // n-1개의 간선 입력 받기
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int q;  // 질의 개수
    cin >> q;

    while (q--) {
        int t, k;
        cin >> t >> k;

        if (t == 1) {  // 단절점 여부 판별
            if (g[k].size() > 1) cout << "yes\n";  // 연결된 정점이 2개 이상이면 단절점
            else cout << "no\n";  // 리프 노드면 단절점 아님
        } else if (t == 2) {  // 단절선 여부 판별
            cout << "yes\n";  // 모든 간선은 단절선
        }
    }
}

 

---

</32942> 그래프와 그래프

https://www.acmicpc.net/problem/32942

문제를 잘 읽고 그대로 코드로 구현하면 되는 문제입니다.

저는 x를 1부터 10까지 바꿔가면서 y를 계산하고, y가 1과 10 사이의 정수라면 출력하고 아니라면 0을 출력하도록 구현해주었습니다.

한 가지 주의할 점은 b가 0인 경우에는 따로 처리해주어야 한다는 점입니다. (a가 0일 때는 따로 처리해줄 필요 없고 기존의 논리 그대로 적용 가능합니다.)

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, b, c;
    cin >> a >> b >> c;

    // b가 0인 경우
    if (b == 0) {
        for (int x = 1; x <= 10; x++) {
            if (a * x == c) cout << "1 2 3 4 5 6 7 8 9 10\n";  // 방정식이 성립하면 모든 y 값 출력
            else cout << "0\n";
        }
        return 0;
    }

    // b가 0이 아닌 경우
    for (int x = 1; x <= 10; x++) {
        int tmp = c - a * x;
        if (tmp % b == 0) {  // y가 정수인지 판별
            int y = tmp / b;
            if (y >= 1 && y <= 10) cout << y << '\n';  // y가 1~10 사이에 있으면 출력
            else cout << "0\n";
        } else cout << "0\n";
    }
}