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


뭐의 앞에 뭐가 오고, 뭐의 앞엔 뭐가 온다 이런 형태로 정보가 주어지면 위상 정렬을 수행한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
queue<int> q;
void tpgSort() {
    for (int i = 1; i <= n; i++) { //indegree 0인거 큐에 넣고 시작
        if (ind[i] == 0) q.push(i);
    }
 
    for (int i = 0; i < n; i++) { // 노드의 개수보다 더 많이 돌면 사이클
        if (q.empty()) cout << "cycle occured\n";
 
        int cur = q.front(); q.pop();
        cout << cur << ' '; //노드 삭제
 
        
        for (int i = 0; i < v[cur].size(); i++) {
            ind[v[cur][i]]--; //삭제된 노드와 연결된 간선 제거
            if (ind[v[cur][i]] == 0) q.push(v[cur][i]);
        }
 
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
    tpgSort();
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14

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


유니온 파인드를 단순히 적용하면 TLE를 맞는 문제이다.


따라서 배열에 지속적으로 그룹의 크기를 저장해줘야 하는데, 따라서 일관성을 가지도록 union함수를 구현해줘야한다.


무조건 작은 값이 부모가 되도록 하는 것이다.



처음에는 단순하게 주석 처리된 부분으로 제출해서 TLE를 맞았다. 가장 단순하게 할 수 있는 해결법이, 쿼리를 진행하기 전에,


모든 원소에 대해서 부모 검색을 다시 수행해서 제대로 된 부모들을 찾아두는 것인데, 이 방법을 사용할 수 없다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<map> //찾는 게 없으면 0반환
#include<string>
#include<algorithm>
using namespace std;
map<string, int> mp;
 
int r[200002], fcnt[200002];
 
int getParent(int a) {
    if (r[a] == a) return r[a];
    else
        return r[a] = getParent(r[a]);
}
int join(int a, int b) {
    
    a = getParent(a);
    b = getParent(b);
    if (a < b) {
        r[b] = a;
        fcnt[a] += fcnt[b];
        fcnt[b] = 1;
        return fcnt[a];
    }
    else if (a > b) {
        r[a] = b;
        fcnt[b] += fcnt[a];
        fcnt[a] = 1;
        return fcnt[b];
    }
    return fcnt[b];
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int idx = 0;
        for (int i = 0; i < 2 * n; i++) {
            r[i] = i;
            fcnt[i] = 1;
        }
        for (int i = 0; i < n; i++) {
            string fir, sec;
            cin >> fir >> sec;
 
            if (mp.count(fir) == 0) {
                mp.insert({ fir, idx });
                idx++;
            }
            if (mp.count(sec) == 0) {
                mp.insert({ sec, idx });
                idx++;
            }
            
            cout << join(mp[fir], mp[sec]) << '\n';
            
            //for (int i = 1; i < idx; i++) getParent(i);
 
            //int cnt = 0;
            //for (int i = 0; i < idx; i++)
            //    if (r[i] == r[mp[fir]])
            //        cnt++;
            //cout << cnt << '\n';
        
        }
        mp.clear();
        
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14

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


유니온파인드를 활용하는 문제이다.


주의할 점은, 항상 특정 노드의 최상위 부모가, 업데이트가 되어있지 않을 수 있다는 생각을 하고, 구현을 해야한다는 것이다.


따라서 최상위 부모를 찾으러 올라갈 때도, 항상 getParent 함수를 호출하면서 올라간다.


마찬가지로 union연산을 할 때에도, a혹은 b의 최상위 부모가 제대로 갱신이 되어있지 않을 수 있기 때문에 마찬가지로 갱신을 하면서 찾아준다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int r[1000002], n;
 
int getParent(int a) {// 마찬가지로 갱신하면서 찾으러 올라감
    if (r[a] == a) return r[a];
    else return r[a] = getParent(r[a]);
}
 
void join(int a, int b) { //갱신하면서
    r[getParent(a)] = getParent(b); //a의 부모를 b의 부모로 update 한다
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++)
        r[i] = i;
 
    for (int i = 0, cmd, a, b; i < m; i++) {
        cin >> cmd >> a >> b;
        if (cmd == 0)
            join(a, b);
        else if (cmd == 1) {
            //for (int i = 0; i <= n; i++) getParent(i);
            int pa = getParent(a);
            int pb = getParent(b);
            if (pa == pb) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14

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


그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.


DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
using namespace std;
int v[1002];
bool vis[1002];
 
void dfs(int cur) {
    if (vis[cur]) return; //이미 방문한 곳을 재방문 했다는 건 사이클이라는 뜻
 
    vis[cur] = true;
    int next = v[cur];
    dfs(next);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) 
            cin >> v[i];
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && v[i] != 0) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << '\n';
 
        for (int i = 1; i <= n; i++) 
            vis[i] = false;
        
    }
 
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14

기본이 max이고 less<>라고 외우면 되겠다.


greater 을 사용하려면 functional 헤더를 인클루드 시켜줘야한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <queue>
using namespace std;
 
struct a{
    int start;
    int en;
    int value;
};
 
bool operator<(a t, a u){
    return t.value < u.value;
}
 
priority_queue<a> pq;
 

cs



구조체와 함께 사용한다면 위와 같이 < 연산자를 오버로딩해서 사용하는데, value가 큰 것부터 나온다.


value가 작은 것부터 나오게 하려면, 12번째 줄의 <를 >로 바꿔주면 된다.



저작자표시 비영리 변경금지

'Programming Language > C++' 카테고리의 다른 글

vector upper_bound, lower_bound 사용 (C++)  (0) 2019.09.01
string 대소문자 변환  (0) 2019.08.25
(C++) abs 함수의 사용  (0) 2019.08.07
(C++) list STL 출력 및 iterator  (0) 2019.08.04
next_permutation  (0) 2019.07.21

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


인덱스 트리를 활용하여 해결했다.


앞선 인덱스 트리를 활용하는 문제들과 같이, 이 문제도 말만 다르지, 결국 원소 업데이트가 빈번하게 일어나는 동시에 구간합을 구하는 문제이다.


특정 맛의 사탕을 빼거나 더하는 것은, 인덱스 트리의 기본적인 업데이트 쿼리와 동일하기 때문에 따로 설명하지는 않을 것이고, 특정 순위의 사탕을 가져오는 부분에 대해서만 살펴보겠다.



a == 1인 경우에 k번째 순위를 가지는 사탕을 가져와야 하는 상황이다.


root에서부터 노드 하나하나가 사탕의 개수를 구간합으로 가지고 있는 형태로 트리를 만들어준다. leaf 노드의 수는 가능한 맛의 범위로 잡아주면 된다. 이 문제에서는 100 만이었던 것으로 기억한다.


이렇게 leaf 노드는 그 맛의 사탕이 몇 개 있다는 것을 의미한다.



이제 k번째 순위의 사탕을 찾는다고 하면, 트리의 왼쪽에서부터(가장 맛있는 사탕부터) k번째인 것이다. 이때 k보다 한 노드의 값(거기까지 구간합)이 크다면 그 노드의 자손 부분에 우리가 찾는 k번째 사탕이 존재한다는 의미이므로 계속 아래로 내려가준다.


반대로 k보다 작다면, 우리가 찾는 k번째 사탕이 그 노드의 오른쪽 트리에 있다는 것이기 때문에 오른쪽으로 이동해주고, 왼쪽에 있는 사탕의 개수(확인했던 구간합의 값)만큼 k를 감소시켜준다.


또한 리트 노드에 도달했다면 위의 작업을 해줄 필요가 없기 때문에, 리프 노드인지 아닌지 확인해 주는 작업을 함께 진행해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#define MAX 1000000
using namespace std;
 
int idxT[4 * MAX+2], start = 1;
 
void Update(int idx, int delta) {
    while (idx > 0) {
        idxT[idx] += delta;
        idx /= 2;
    }
}
 
int getCandy(int k) {
    int i = 1;
    while (1) {
        if (idxT[i] >= k) { //이 지점의 서브트리에 우리가 찾는 사탕이 속해 있다면
            if (i >= start && i < start + MAX) { //그 지점이 leaf라면 종료
                Update(i, -1);
                return i - start + 1;
            }
            i *= 2; //leaf가 아니라면 이어서 탐색
            continue;
        }
        else { //이 지점이 아닌 반대쪽에 우리가 찾는 사탕이 있다면
            k = k - idxT[i]; 
            i++;
            continue;
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    while (start < MAX) //MAX보다 크거나 같으면서 가장 큰 2의 제곱수
        start *= 2;
    
    int n; 
    cin >> n; //쿼리의 수
    for (int i = 0, a, b, c ; i < n; i++) {
        cin >> a >> b;
        if (a == 1) 
            cout << getCandy(b) << '\n'; //사탕 꺼내기
        
        else {
            cin >> c; //사탕의 변화량
            Update(b + start - 1, c);
        }
    }
    
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1717 집합의 표현 C++  (0) 2019.08.14
백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13

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


수열의 성분이 빈번하게 바뀌면서, 구간합을 물어보는 문제이기 때문에 인덱스 트리를 구현해주면 된다.


인덱스 트리에 대한 좀 더 자세한 설명은 https://hugssy.tistory.com/132 를 참고하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll idxTree[4 * 100002];
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q;
    cin >> n >> q;
 
    int start = 1;
    while (start < n)
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
 
    for (int i = 0; i < n; i++)
        cin >> idxTree[i + start];
 
    for (int i = start - 1; i >= 1; i--)
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
 
    while (q--) {
        int x, y, a, b;
        cin >> x >> y >> a >> b;
        if (x > y) swap(x, y);
        cout << findSum(x + start - 1, y + start - 1) << '\n';
        Update(a + start - 1, b - idxTree[a + start - 1]);
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 10451 순열 사이클 C++  (0) 2019.08.14
백준 2243 사탕상자 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13

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


이진 검색 트리를 구현해주면 된다.


왼쪽 자식은 부모보다 작은 값이고, 오른쪽 자식은 부모보다 큰 값이다.


이진 검색 트리의 서브트리는, 마찬가지로 이진 검색 트리이다.



이 문제에서는 node 구조체를 root값 자체를 인덱스로 하도록 잡았다.


이전에 트리 순회 문제에서도 봤듯이, 순회가 문제에 섞일 때에는 인덱스를 루트의 값과 연결시켜서 잡아주는 것이 좋은 것 같다.



이 문제에서 주의할 사항은, 루트의 값 자체를 인덱스로 사용하기 때문에, 전체 노드의 개수가 아닌, root값의 허용 범위를


인덱스로 잡아줘야하다는 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
using namespace std;
 
struct NODE{
    int l, r;
}n[1000002]; //인덱스가 root
//노드의 개수는 1000개인데, 인덱스를 루트로 쓰고 있기 때문에 루트의 허용 범위만큼 인덱스 필요
 
void postOrder(int rt) {
    if (rt == 0) return;
    postOrder(n[rt].l);
    postOrder(n[rt].r);
    cout << rt << '\n';
}
 
int main(void) {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    int root;
    cin >> root; //전위순회니까 처음 나오는 게 무조건 tree의 root
    int num;
    while (cin >> num) {
        int cur = root;
        while (1) {
            if (num < cur) {
                if (n[cur].l != 0) cur = n[cur].l;
                else {
                    n[cur].l = num;
                    break;
                }
            }
            else {
                if (n[cur].r != 0) cur = n[cur].r;
                else {
                    n[cur].r = num;
                    break;
                }
            }
 
        }
    }
    postOrder(root);
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 2243 사탕상자 C++  (0) 2019.08.14
백준 1275 커피숍2 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13

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


트리는


1. 간선의 개수 + 1 == 노드의 개수


2. 들어오는 간선이 없는 노드는 하나



1번 사실을 이용해서 node를 담는 set을 만들고, 간선의 개수를 카운트해서 개수 비교를 통해 풀었다.


추가적으로, 간선이 하나도 없어도 트리가 될 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<unordered_set>
using namespace std;
unordered_set<int> nodes;
int main(void) {
 
    bool endFlag = false;
    int lineCnt = 0, caseCnt = 1;
    while (1) {
        int a, b;
        cin >> a >> b;
        if (a == -1 && b == -1) {
            endFlag = true;
            break;
        }
        if (a == 0 && b == 0) {
            if (lineCnt == 0 || nodes.size() == lineCnt + 1 ) {
                printf("Case %d is a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
            else{
                printf("Case %d is not a tree.\n", caseCnt);
                caseCnt++;
                nodes.clear();
                lineCnt = 0;
                continue;
            }
 
        }
        nodes.insert(a);
        nodes.insert(b);
        lineCnt++;
    }
 
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1275 커피숍2 C++  (0) 2019.08.14
백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 2042번 구간합 구하기 C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12

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


일반적인 구간합 구하기 문제라면, 배열을 별도로 두고 특정 인덱스까지 구간합을 저장해서 구하겠지만,


이 문제의 경우처럼 원소 자체가 빈번하게 업데이트 되면서 구간합을 구해야 한다면 인덱스 트리를 사용하는 게 편리하다.



인덱스 트리를 만드는 과정은 다음과 같다.


우선 leaf가 꽉 찬 트리로 만들어야 하기 때문에 원소의 개수보다 큰 가장 작은 2의 제곱수를 찾는다.


가령 예시의 경우처럼 원소가 5개라면 5보다 큰 가장 작은 2의 제곱수는 8이다.


기본적으로 배열은 1-indexed로 한다. 따라서 leaf에 처음 숫자들이 저장될 텐데, 인덱스 8부터 들어가면 된다.


비는 공간은 쿼리와 상관없는 수로 채워준다. (구간합 구하기 문제 같은 경우 0은 합에 영향을 미치지 않기 때문에 0으로 채워준다)


(가령 구간의 최댓값을 저장하는 인덱스 트리라면 구간의 최댓값에 영향을 미치지 않게 가장 작은 수로 비는 부분을 채워주면 된다)



인덱스를 찾았으니 구간합을 채워주면 된다.


부모의 인덱스는 자식 인덱스 /2, 왼쪽 자식은 부모 인덱스 *2, 오른쪽은 *2 +1 이라는 것을 이용해서 쿼리를 만들어주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#define MAX 1000002
using namespace std;
 
typedef long long ll;
ll idxTree[4 * MAX];
 
void Update(int idx, ll delta) {
    while (idx > 0) {
        idxTree[idx] += delta;
        idx /= 2;
    }
}
 
ll findSum(int st, int en) {
    ll ret = 0;
    while (st <= en) {
        if (st % 2 == 1) ret += idxTree[st];
        if (en % 2 == 0) ret += idxTree[en];
        st = (st + 1) / 2;
        en = (en - 1) / 2;
    }
    return ret;
}
 
int main(void) {
    int n, m, k;
    cin >> n >> m >> k;
    int start = 1;
    while (start < n) {
        start *= 2; //n보다 큰 가장 작은 2의 제곱수
    }
    
    for (int i = 0; i < n; i++) { //원래 빈공간도 채워줘야 한다. 쿼리에 영향을 받지 않는 값으로
        cin >> idxTree[start + i];
    }
    //트리의 아래에서 위로 채워가기
    for (int i = start - 1; i >= 1; i--) {
        idxTree[i] = idxTree[2 * i] + idxTree[2 * i + 1];
    }
    for (int i = 0; i < m + k; i++) {
        int a, b, c;
        cin >> a >> b >> c; //두 경우 모두 인덱스를 계산해서 넘겨야함, 차이는 새거-있던거
        if (a == 1) Update(b + start - 1, c - idxTree[b + start - 1]);
        else if (a == 2) cout << findSum(b + start - 1, c + start - 1) << '\n';
    }
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 5639 이진 검색 트리 C++  (0) 2019.08.14
백준 6416 트리인가? C++  (0) 2019.08.13
백준 1991 트리 순회 C++  (0) 2019.08.13
백준 3878 점 분리 C++  (0) 2019.08.12
백준 1708 볼록 껍질 C++  (0) 2019.08.12

+ Recent posts

티스토리툴바