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


최소 공통 조상 (Lowest Common Ancestor)를 찾는 알고리즘이다.


1. dfs로 트리를 만든다. 이때 노드별 깊이 정보와(root 깊이 = 0) 가장 첫번째 부모 정보를 잡아준다.


2. 노드 A의 2^k번째 부모 노드는, A의 2^k-1번째 부모 노드의 2^k-1번째 부모 노드와 같다는 것을 이용해서 바텀업 dp로 부모 배열을 채운다.


3. 공통 조상을 찾을 a, b가 있다면, 우선 깊이가 깊은 곳과 낮은 곳을 확실히 구분해준다. 그리고 둘의 높이를 맞춰준다.


n개의 노드가 있다고 했을 때, 2의 거듭제곱으로 타고 올라갈 수 있는 최대 높이가 MAXK =(int)floor(log2(n)); 이다.


두 노드의 높이 차이가, 위에서부터 보고 내려온 2의k승보다 크거나 같아지는 순간마다 깊은 노드를 해당하는 2의 k번째 부모로 갱신한다.


결국 높이가 같아지게 되고, 이때 두 노드의 값이 같다면 반환해주면 된다.



그렇지 않다면


4. 위와 비슷한 방식으로, 2의최대 거듭제곱부터 아래로 내려오면서 부모의 노드가 같은지 확인한다. 다를때마다 두 노드를 다른 순간의 2의 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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
 
int n, m, dep[100002], MAXK, parent[100002][20];
bool  vis[100002];
 
vector<int> e[100002];
void makeTree(int here, int depth) { //트리 만들면서 첫번째 부모와 깊이를 채움
    //if (vis[here]) return; //continue문 주석 풀고 여길 주석해도 똑같음
    vis[here] = true;
    dep[here] = depth;
    
    for (int i = 0; i < e[here].size(); i++) {
        int next = e[here][i];
        if (vis[next]) continue;
        parent[next][0] = here; //첫번째 부모 저장
        makeTree(next, depth + 1);
    }
}
void fillParent() { //바텀업으로 부모 배열 채워줌
    for (int k = 1; k <= MAXK; k++) 
        for (int i = 1; i <= n; i++) 
            parent[i][k] = parent[parent[i][k - 1]][k - 1];
}
int lca(int swall, int deep) {
    if (dep[deep] < dep[swall]) swap(deep, swall);
    
    for (int k = MAXK; k >= 0; k--) { //높이를 동일하게 맞춰줌
        int dif = dep[deep] - dep[swall];
        if (dif >= (1 << k)) deep = parent[deep][k];
    }
 
    if (deep == swall)
        return deep;
    
    //printf("deep  swall 중간 %d %d\n", deep, swall);
    for (int k = MAXK; k >= 0; k--) {
        if (parent[deep][k] != parent[swall][k]) {
            deep = parent[deep][k];
            swall = parent[swall][k];
        }
    }
    return parent[deep][0];
 
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n-1; i++) { //node가 n개고 간선은 n-1개
        int src, dst;
        cin >> src >> dst;
        e[src].push_back(dst);
        e[dst].push_back(src);
    }
    makeTree(1, 0); //root = 1, root depth = 0
    
    MAXK =(int)floor(log2(n)); //포함 -> 최대높이*****************
    
    fillParent();
 
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
    return 0;
}
 
cs


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

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

백준 1753 최단경로 C++  (0) 2019.08.15
백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15

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


MST를 구현해주면 되고, 크루스칼 알고리즘을 이용한다.


크루스칼 알고리즘은 유니온 파인드를 그대로 옮겨 놨다고 봐도 상관이 없다.


0. 유니온 파인드를 활용하기 때문에, 최상위 부모노드의 값을 자기 자신으로 초기화한다.


1. 간선 정보를 비용 오름차순으로 정렬한다.


2. 간선의 시작점과 끝점을 union해보면서, 같은 그룹에 속해있지 않다면, union 해주고 간선 비용을 추가해준다.

이미 같은 그룹이라면 연결되어 있다는 의미이기 때문에 비용에 더해주지 않고 스킵한다.


3. 모든 노드를 연결하는데에 필요한 간선의 개수는 n-1개이다. 따라서 n-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
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
 
int n, e, r[10002];
struct EDGE {
    int from, to, cost;
};
vector<EDGE> edge;
bool cmp(EDGE a, EDGE b) {
    return a.cost < b.cost;
}
int getParent(int a) {
    if (r[a] == a) return a;
    else return r[a] = getParent(r[a]);
}
bool join(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) return false; //이미 연결되어 있음
    else if (a < b)
        r[b] = a;
    else
        r[a] = b;
    return true;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> e;
 
    while (e--) {
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge.push_back({ src, dst, cost });
    }
    sort(edge.begin(), edge.end(), cmp);
 
    for (int i = 1; i <= n; i++)
        r[i] = i;
 
    //연결 안 되어 있는 노드 찾아서 연결 해보고, 연결 안 되어 있으면 연결하고 비용 추가
    ll res = 0;
    int cnt = 0;
    for (int i = 0; i < edge.size(); i++) {
        if (join(edge[i].from, edge[i].to)) {
            res += edge[i].cost;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    printf("%lld ", res);
 
    return 0;
}
 
cs


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

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

백준 1916 최소비용 구하기 C++  (0) 2019.08.15
백준 11438 LCA2 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15

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



각 단계별로 시간(비용)이 있을 때, 위상 정렬을 할 수 있는 정보가 주어지는 경우이다.


입력을 받을 때, indegree를 모두 구하면서 입력을 받는다.


초기에 indegree가 0인 지점을 큐에 넣고 시작하는데, 이런 지점은 이전에 필요로 하는 단계가 없기 때문에, 그 지점의 비용이


그 지점까지 총 비용이 된다.



이후에는 위상 정렬을 진행하는데, 현재 단계까지의 총 비용은 확정이므로, 다음 단계의 총 비용을 구해준다. 이 때, 시간의 경우, 가장 오래걸리는 시간을 넣어줘야 한다.


이게 당연한 것이, 4번을 수행하기 위해 1번과 3번을 사전에 수행해야 한다고 해보자.


다른 조건이 없다는 가정하에, 1번과 3번중에서는 어떤 것을 먼저해도 상관이 없다.


그렇다면 예를들어 1번을 하는데에 3초가 걸리고, 3번을 하는데에 6초가 걸린다고 쳐보자. 그리고 4번만을 수행하는 데에는 5초가 걸린다고 하자.


1번을 볼 때, 1번 다음에 4번을 수행해야 한다는 것을 알고 있고, 이 시점에서 4번을 완수하기 위해서는 1번의 시간 + 4번의 시간이 필요하다.


1번을 하면서 동시에 3번도 수행할 수 있기 때문에, 앞서 구한 1번 시간 + 4번시간과 3번 시간 + 4번시간을 비교해서, 오래 걸리는 시간으로 갱신해줘야 한다.


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>
#include<vector>
#include<queue>
 
using namespace std;
int t[502], n, ind[502], done[502];
vector<int> v[502];
queue<int> q;
 
void tpgSort() {
    for (int i = 1; i <= n; i++)
        if (ind[i] == 0) {
            q.push(i);
            done[i] = t[i];
        }
 
    for (int i = 0; i < n; i++) {
        if (q.empty()) cout << "cycle\n";
 
        int cur = q.front();
        q.pop();
        
            int Max = -1;
            for (int j = 0; j < v[cur].size(); j++) {
                ind[v[cur][j]]--;
                if (ind[v[cur][j]] == 0) q.push(v[cur][j]);
                //다음 단계 비용 = 현재 단계까지 총비용중 가장 오래걸리는 비용 + 다음 단계 비용
                if (done[v[cur][j]] < done[cur] + t[v[cur][j]]) {
                    done[v[cur][j]] = done[cur] + t[v[cur][j]];
                }
            }
 
    }
}
int main(void) {
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int time;
        cin >> time;
        t[i] = time;
        while (1) {
            int pre;
            cin >> pre;
            if (pre == -1) break;
            v[pre].push_back(i);
            ind[i]++;
        }
    }
    tpgSort();
    for(int i = 1 ; i <= n ; i++ )
        printf("%d\n", done[i]);
    return 0;
}
 
cs


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

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

백준 11438 LCA2 C++  (0) 2019.08.15
백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15

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


dp느낌으로 해결이 가능하다. . 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다


이 문장때문에 아래 풀이로 가능한 것이다.


d[i] = i의 사전작업까지 모두 포함해서 작업 i를 끝내는 데에 걸리는 시간


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>
#include<functional>
using namespace std;
 
int n, m, t[10001], d[10001];
vector<int> v[10001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tm, num;
        cin >> tm >> num;
        t[i] = tm;
        while (num--) {
            int pre;
            cin >> pre;
            v[i].push_back(pre);
        }
    }
    //d[i] = i의 사전작업까지 다 포함해서 작업 i 끝내는데 드는 시간
    d[1] = t[1];
    for (int i = 2; i <= n; i++) {
        if (v[i].size() == 0) d[i] = t[i]; //사전 작업 없으면 그 작업 끝내는 시간
        else {
            int Max = -1;
            for (int j = 0; j < v[i].size(); j++) {
                if (Max < d[v[i][j]]) Max = d[v[i][j]];
            }
            d[i] = Max + t[i];
        }
    }
    //어떤 작업이 제일 마지막에 끝날지는 알 수 없지만, 필요 시간이 가장 긴게 마지막에 끝나는 것
    int ret = -1;
    for (int i = 1; i <= n; i++)
        if (ret < d[i]) ret = d[i];
    cout << ret;
    return 0;
}
 
cs


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

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

백준 1197 최소 스패닝 트리 C++  (0) 2019.08.15
백준 1516 게임 개발 C++  (0) 2019.08.15
백준 1766 문제집 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14

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


풀어야할 문제들이 난이도로 주어진다. 또한 어떤 문제를 어떤 문제보다 먼저 풀어야한다는 식의 데이터가 주어지므로, 위상 정렬을 활용한다.


다만 큐에서 꺼낼때, 난이도가 낮은 문제를 먼저 꺼내야 하기 때문에, min heap을 사용해주면 된다.



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>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
 
int n, m, ind[32002];
vector<int> v[32002];
priority_queue<int, vector<int>, greater<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.top(); 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


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

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

백준 1516 게임 개발 C++  (0) 2019.08.15
백준 2056 작업 C++  (0) 2019.08.15
백준 2252 줄 세우기 C++  (0) 2019.08.15
백준 4195 친구 네트워크 C++  (0) 2019.08.14
백준 1717 집합의 표현 C++  (0) 2019.08.14

+ Recent posts

티스토리툴바