취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21235번 문제인 Year of the Cow이다.
문제는 아래 링크를 확인하자.
www.acmicpc.net/problem/21235

문제를 간단히 요약하면 다음과 같다.

1) 첫 줄에 앞으로 나올 문장의 수 N을 입력으로 준다.

2) 다음 N줄에는 "(소1) born in (next/previous) (12간지) year from (소2)" 와 같은 문장이 주어진다.

2-1) 소1은 (Bessie 또는 이미 앞선 문장들에서 이름이 등장한 적이 있는 소 이름)이 아닌 이름이 주어진다.

2-2) 소2는 (Bessie 또는 이미 앞선 문장들에서 이름이 등장한 적이 있는 소 이름)인 이름이 주어진다.

2-3) Elsie라는 이름을 가진 소는 반드시 등장한다. 또한, Bessie는 소띠(Ox)이다.

3) Bessie와 Elsie 사이에 생년이 얼마나 차이가 날지를 계산하여 출력한다.

이 문제는 주어진 조건을 그대로 구현하기만 하면 되는 간단한 문제이다.

단, 위에서 주어지는 문장으로는 절대 생년이 같은 소가 주어질 수가 없으므로, 같은 간지에 태어난 소들의 조건을 세울 때 약간의 주의를 기울일 필요가 있다.

문제의 입력이 문자열로 주어지므로, std::map을 이용하여 문제를 해결하였다.

아래는 제출한 소스코드이다.

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

map<string, int> mp;
int arr[101];
int animal[101];

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

    int N;
    cin >> N;

    mp.insert({ "Bessie",0 });
    for (int i = 1;i <= N;i++) {
        string s; cin >> s;
        mp.insert({ s,i });
        cin >> s >> s >> s;
        bool next = 0;
        if (s[0] == 'n') next = 1;
        cin >> s;
        if (s == "Ox") animal[i] = 0;
        else if (s == "Tiger") animal[i] = 1;
        else if (s == "Rabbit") animal[i] = 2;
        else if (s == "Dragon") animal[i] = 3;
        else if (s == "Snake") animal[i] = 4;
        else if (s == "Horse") animal[i] = 5;
        else if (s == "Goat") animal[i] = 6;
        else if (s == "Monkey") animal[i] = 7;
        else if (s == "Rooster") animal[i] = 8;
        else if (s == "Dog") animal[i] = 9;
        else if (s == "Pig") animal[i] = 10;
        else if (s == "Rat") animal[i] = 11;
        cin >> s >> s >> s;
        int idx = mp[s];
        arr[i] = animal[i] - animal[idx];
        if (next) {
            if (arr[i] <= 0) arr[i] += 12;
        }
        else {
            if (arr[i] >= 0) arr[i] -= 12;
        }
        arr[i] += arr[idx];
    }

    cout << abs(arr[mp["Elsie"]]);
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2463번 문제인 비용이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2463

이 문제를 풀기 위해 잠시 생각을 해보자.

어떤 에지가 지워졌을 때 그 두 에지의 양 끝을 잇는 점 사이에 경로가 존재하지 않는다면, 각 에지가 속해있는 component에서 각각 하나씩 뽑은 노드 사이의 경로도 그 순간 전부 사라지게 될 것이다. 따라서, 이러한 에지가 사라질 경우, 이때까지 지운 에지들의 가중치의 합을 답에 두 component의 크기를 곱한 횟수만큼 더하는 것으로 답을 구할 수 있을 것이다.

별개인 집합을 하나로 합치는 Disjoint Set 자료구조를 이용하여 문제에서의 에지가 지워지는 과정을 거꾸로 거슬러올라가면서(에지를 그으며 component를 하나로 합치면서) 위 생각을 이용하면 이 문제를 쉽게 해결할 수 있다.

아래는 제출한 소스코드이다.

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

long long ans = 0;
long long sum = 0;

int arr[100001];
long long cnt[100001];
priority_queue<pair<long long, pair<int, int>>> pq;

int findf(int x) {
    if (x == arr[x]) return x;
    else return arr[x] = findf(arr[x]);
}

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

    int N, M; cin >> N >> M;

    for (int i = 1;i <= N;i++) {
        arr[i] = i;
        cnt[i] = 1;
    }

    for (int i = 0;i < M;i++) {
        int x, y; long long w; cin >> x >> y >> w;
        pq.push({ w,{x,y} });
        sum += w;
    }

    while (!pq.empty()) {
        int x = findf(pq.top().second.first), y = findf(pq.top().second.second);
        long long w = pq.top().first;
        pq.pop();

        if (x != y) {
            ans += cnt[x] * cnt[y] * sum;
            ans %= 1000000000;
            arr[y] = x;
            cnt[x] += cnt[y];
        }
        
        sum -= w;
    }

    cout << ans;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15285번 문제인 Connections이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15285

이 문제에서는 주어진 Strongly Connected Graph(각 노드에서 모든 다른 노드로 가는 경로가 존재하는 방향그래프)에서 에지가 2n개인 Strongly Connected Subgraph를 찾는 문제이다.

(정확히는, 2n개의 에지를 제외한 지울 에지를 전부 출력하는 문제이다.)

글쓴이는 다음과 같은 아이디어를 바탕으로 이 문제를 해결하였다.

노드 X를 하나 정해, 그 노드에서 정방향 에지로 DFS를 하면서 지나는 간선과, 역방향 에지로 DFS를 하면서 지나는 간선만 남아있는 Subgraph 또한 Strongly Connected Graph가 된다. X에서 임의의 노드로 가는 경로가 항상 존재하고(정방향 에지 DFS), 임의의 노드에서 X로 가는 경로가 항상 존재하기 때문이다(역방향 에지 DFS).

위 Subgraph는 에지가 최대 2N-2개이므로, 항상 2N개 이하의 에지로 이루어져있다.

따라서, (편의상) 1번 노드에서 정방향 에지를 이용한 DFS에 사용된 에지와 역방향 에지를 이용한 DFS에 사용한에지를 제외한 에지에서 개수만 맞춰 아무 에지나 출력하면 된다.

아래는 제출한 소스코드이다.

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

vector<pair<int,int>> G[50001];
vector<pair<int,int>> invG[50001];
bool visited[100001];

bool dfsvisited[100001];
bool invdfsvisited[100001];

void dfs(int current, int parent) {
    for (auto node : G[current]) {
        if (dfsvisited[node.first]) continue;
        dfsvisited[node.first] = 1;
        visited[node.second] = 1;
        dfs(node.first, current);
    }
}

void invdfs(int current, int parent) {
    for (auto node : invG[current]) {
        if (invdfsvisited[node.first]) continue;
        invdfsvisited[node.first] = 1;
        visited[node.second] = 1;
        invdfs(node.first, current);
    }
}

void solve() {
    int V, E; cin >> V >> E;
    
    for (int i = 1;i <= V;i++) {
        G[i].clear();
        invG[i].clear();
    }

    memset(visited, 0, sizeof(visited));
    memset(dfsvisited, 0, sizeof(dfsvisited));
    memset(invdfsvisited, 0, sizeof(invdfsvisited));

    pair<int, int> edge[100001];

    for (int i = 0;i < E;i++) {
        int x, y; cin >> x >> y;
        edge[i] = { x,y };
        G[x].push_back({ y,i });
        invG[y].push_back({ x,i });
    }

    dfsvisited[1] = invdfsvisited[1] = 1;
    dfs(1, 1);
    invdfs(1, 1);

    int cnt = E - V * 2;
    int idx = -1;
    while (cnt > 0) {
        idx++;
        if (visited[idx]) continue;
        cout << edge[idx].first << ' ' << edge[idx].second << '\n';
        cnt--;
    }
}

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

    int T; cin >> T;
    for (;T > 0;T--) {
        solve();
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15517번 문제인 Array Manipulation at Moloco (Hard)이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15517

이 문제는 절댓값이 20억 이하인 정수들이 N개 주어질 때, 각 i번째 정수에 대하여 앞서 나온 정수 중 그 정수보다 작은 정수의 개수를 출력하는 문제이다.

다음 정수를 받을 때마다 최솟값을 다시 한번씩 탐색하는 알고리즘의 시간복잡도는 O(N^2)로, N이 100만까지 커질 수 있는 이 문제를 풀기에 적합하지 않다. 위 시간복잡도로 문제를 해결하고 싶다면 15516번(www.acmicpc.net/problem/15516)을 푸는 것을 권장한다.

이 글에서는 세그먼트 트리를 이용해 O(NlgN)으로 문제를 해결해보자.

크기가 40억1인 배열을 준비해 i번째 정수를 받아 입력받은 정수 미만인 수들의 개수를 모두 더해 저장하는 구간합 세그먼트 트리를 이용하면 문제를 풀 수 있을 것 같지만, 배열의 크기가 너무 커 메모리제한에 걸릴 것이다.

따라서, 입력받은 정수들을 크기순으로 1, 2, 3, ... , N과 같이 바꿔준 뒤에(좌표압축) 세그먼트트리를 이용하는 것으로 이 문제를 풀 수 있다.

아래는 제출한 소스코드이다.

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

pair<int,int> arr[1000000]; // {원래 정수, index}
int idx[1000000]; // 좌표압축이 된 배열
int seg[2097153];

void update(int L, int R, int qI) {
    int sI = 1;
    while (L != R) {
        seg[sI]++;
        int mid = (L + R) / 2;
        if (qI <= mid) {
            R = mid;
            sI = sI * 2;
        }
        else {
            L = mid + 1;
            sI = sI * 2 + 1;
        }
    }
    seg[sI]++;
}

int query(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 0;
    if (qL <= L && R <= qR) return seg[sI];
    return query(L, (L + R) / 2, qL, qR, sI * 2) + query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

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

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        int x; cin >> x;
        arr[i] = { x,i };
    }
    
    // 좌표압축
    sort(arr, arr + N);

    for (int i = 0;i < N;i++) {
        idx[arr[i].second] = i + 1;
    }
	
    // 세그먼트트리를 이용한 문제 해결
    for (int i = 0;i < N;i++) {
        cout << query(1, N, 1, idx[i] - 1, 1) << '\n';
        update(1, N, idx[i]);
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1688번 문제인 지민이의 테러이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1688

세 사람을 지키기 위한 꼭짓점이 N개인 다각형이 주어진다. 세 사람이 이 다각형의 내부에 있을 때(경계 포함), 각 사람은 안전하다고 말할 수 있다. 그러므로, 이 문제를 해결하기 위해서는 각 사람의 좌표가 주어진 다각형의 외부에 있는지 내부 또는 경계 위에 있는지를 확인해야 한다.

주어진 다각형이 볼록다각형이라는 보장이 없으므로, 주어진 점이 다각형 내부에 있는지를 확인하기 위해 Ray Casting 알고리즘을 이용하자. 

Ray Casting 알고리즘은 주어진 점에서 한 방향으로 무한한 (것과 같은 취급을 할 수 있는) 길이의 반직선을 그었을 때, 다각형의 변과 만나는 횟수를 세어 주어진 다각형의 내부에 있는지 외부에 있는지를 판단하는 알고리즘이다. 구체적으로, 만약 이 반직선과 다각형이 홀수번 만났다면 주어진 점은 다각형의 내부에 있는 것이고, 그렇지 않다면 주어진 점은 다각형의 외부에 있는 것이다.

Ray Casting 알고리즘에서 사용하는 반직선의 일부가 한 변과 무수히 많은 교점이 생기거나, 꼭짓점을 지나 한 점이 두 번 세어지는 일이 발생하면 반직선과 다각형의 변이 만나는 횟수를 제대로 셀 수 없게 된다. 이를 피하기 위하여 반직선을 정할 때 주어진 범위 내의 정수점으로 만들 수 없는 기울기의 직선을 잡으면 편하다.

그 외로, 다각형의 변과 반직선이 교차하는지를 판정해야하므로 CCW를 이용한 선분교차 판정법을 사용하였다.

Ray Casting 알고리즘은 주어진 점이 다각형의 경계 위에 있을 때에는 정상적으로 작동하지 않으므로(반직선의 방향에 따라 교점이 홀수개일수도, 짝수개일수도 있기 때문), 점이 다각형의 경계 위에 있는지는 별도로 검사해주자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

pll points[10001];

int CCW(pll A, pll B, pll C) {
    ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
    if (ccw > 0) return 1;
    if (ccw < 0) return -1;
    return 0;
}

int intersection(pll A, pll B, pll C, pll D) {
    int ccw1 = CCW(A, B, C);
    int ccw2 = CCW(A, B, D);
    int ccw3 = CCW(C, D, A);
    int ccw4 = CCW(C, D, B);

    if (ccw1 * ccw2 == 0 && ccw3 * ccw4 == 0) {
        if (A > B) swap(A, B);
        if (C > D) swap(C, D);
        if (B < C || D < A) return 0;
        else return 1;
    }
    else if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) return 1;
    else return 0;
}

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

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        ll x, y; cin >> x >> y;
        points[i] = { x,y };
    }
    points[N] = points[0];

    for (int i = 0;i < 3;i++) {
        int cnt = 0;
        ll x, y; cin >> x >> y;
        pll X = { x,y }, Y = { x + 1000000007, y + 1 }; // 선분 XY가 X에서 뻗어나가는 반직선 역할
        bool chk = 0;
        for (int j = 0;j < N;j++) {
            cnt += intersection(X, Y, points[j], points[j + 1]);
            if (CCW(points[j], X, points[j + 1]) == 0) { //다각형의 경계 위에 있는지 검사
                if ((points[j] <= X && X <= points[j + 1]) || (points[j + 1] <= X && X <= points[j])) {
                    chk = 1;
                    break;
                }
            }
        }
        if (chk) cout << 1 << '\n';
        else if (cnt & 1) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1182번 문제인 부분수열의 합이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1182

N의 최댓값이 20이므로, 모든 경우의 수는 많아봐야 2^20(대략 100만)가지가 된다는 것을 알 수 있다.

따라서, 단순히 모든 경우의 수를 탐색하는 것으로 이 문제는 해결할 수 있다.

같은 경우를 중복을 피해 계수하자.

아래 제출 코드에서 주석이 달린 부분이 있는 것은, 총합이 0인 경우 초기값때문에 코드상 경우의 수가 하나 더 세어지기 때문이다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[20];
int currentsum = 0;
int N, S, ans = 0;

void func(int current) {
    if (currentsum == S) ans++;
    for (int i = current;i < N;i++) {
        currentsum += arr[i];
        func(i + 1);
        currentsum -= arr[i];
    }
}

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

    cin >> N >> S;
    for (int i = 0;i < N;i++) {
        cin >> arr[i];
    }

    if (S == 0) ans--; // currentsum의 초기값 0과 겹쳐서 한번 더 세지므로
    func(0);

    cout << ans;
}