문제는 여기


특정간선을 포함하는경우, 실제 MST보다 큰 값이 나올 수 있다. (프루스칼로 MST를 구할때는 간선을 정렬한다음에 최소간선부터 시작함을 상기하자)

MST 한 번 하는데 $O(E \times log E)$ 니까, 간선개수만큼 하면 $O(E^2 \times log E)$ 일거고.. E가 10^5보다 크므로 나이브하게 해서는 TLE확정이다.


풀이방법

MST를 구한다음에.. 해당 간선이 이미 포함돼 있으면 MST값을 그냥 찍으면 되고, 만약 포함되어 있지 않으면 포함시키고, 다른 간선중 하나를 빼는식으로 하면 된다.

잘 이해가 가지 않는다면 다음 그래프를 보자. (간선 가중치는 생략돼 있지만 MST를 그린 화면으로 생각하자)

여기서 만약 정점 1과 정점4를 잇는 간선을 포함한 답을 구한다고 생각해보자. (위그림에서는 정점1과 정점4 사이에 간선이 없지만 원래는 있었는데 MST구하면서 제거됐다고 가정)

위 그림에서 알 수 있듯이 MST에 (1,4)간선을 추가한 순간 사이클이 생기기 때문에, (1,6) (6,2) (2,5) (5,3) (3,4) 중 하나를 대신 끊어줘야 한다.

이때 나이브하게 경로를 쭉 따라가면서 가중치 가장 큰 걸 빼주는 식으로 하면, 그래프 구조가 직선적인 경우 O(E)가 걸리게 되어 E개의 쿼리를 처리하는데 O(E^2)이 걸려서 TLE가 나게된다.

따라서 위에 LCA로 표시했지만 공통조상까지 올라가고, 내려오는 경로상에서 스파스 테이블을 사용해서 효율적으로 최대가중치를 가진간선을 골라줘야 한다. 참고로 LCA에서 최대가중치 간선을 고르는 문제는 여기에 있다.


코드

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;
const int INF = (int)1e9;
const int MAXN = 200001;
const int LOG_N = 19;
 
struct node3
{
    int u, v, w;
    bool operator < (const node3& t) const {
        return w < t.w;
    }
};
struct node2 { int v, w; };
bool operator<(node2 l, node2 r) { return l.w > r.w; }
vector<vector<node2>> adj_list(MAXN);
 
ll MST_Kruskal(int max_v, vector<node3> v) {
    struct union_find {
        vector<int> parent;
        union_find(int n) {
            parent.resize(n + 1);
            for (int i = 0; i <= n; i++) parent[i] = i;
        }
        int find(int v) {
            return v == parent[v] ? v : parent[v] = find(parent[v]);
        }
        bool uni(int u, int v) {
            u = find(u), v = find(v);
            if (u == v) return 0;
            parent[u] = v;
            return 1;
        }
    };
    union_find uf(max_v);
    sort(v.begin(), v.end());
    ll ans = 0;
    for (auto a : v) {
        if (uf.uni(a.u, a.v)) {
            adj_list[a.u].push_back({ a.v,a.w });
            adj_list[a.v].push_back({ a.u,a.w });
            ans += a.w;
        }
    }
    return ans;
}
 
 
//무방향그래프를 인풋으로 받아, 트리로 만들어준다.LCA를 위한 작업도 해준다.
struct result { int root; int max_level; };
vi parent(MAXN), level(MAXN), dist2(MAXN);
// ancestor[y][x] :: x의 2^y번째 조상을 의미
vvi ancestor(LOG_N + 1, vi(MAXN, -INF));  
 
result treefy(vector<vector<node2>>& adj_list, int root=-1,bool base1=false) {
    int max_v = (int)adj_list.size();
    int max_level = LOG_N;
    function<void(node2, int, int)> dfs = [&](node2 n, int par, int lv) {
        parent[n.v] = par, level[n.v] = lv, dist2[n.v] = n.w;
        ancestor[0][n.v] = par;  // 첫번째(2^0) 조상은 부모
        for (auto adj : adj_list[n.v]) {
            if (adj.v == par) continue;  // 부모방향 간선제거
            dfs(adj, n.v, lv + 1);
        }
    };
    dfs({ root,0 }, -INF, 1);
    for (int i = 1; i <= max_level; i++) {
        for (int j = 1; j < max_v; j++) {
            int tmp = ancestor[i - 1][j];
            if (tmp == -INF) continue;
            ancestor[i][j] = ancestor[i - 1][tmp];
        }
    }
 
    return { root, max_level };
}
 
int lca(int u, int v, vi& level, vvi& ancestor)
{
    if (level[u] < level[v]) swap(u, v);  // b가 더 깊도록 조정
 
    int diff = level[u] - level[v];
    for (int i = 0; diff; i++) {
        if (diff & 1) u = ancestor[i][u];  //b를 올려서 level을 맞춘다.
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = LOG_N; i >= 0; i--) {
        // a와 b가 다르다면 현재 깊이가 같으니, 깊이를 a,b동시에 계속 올려준다.
        if (ancestor[i][u] != ancestor[i][v]) 
            u = ancestor[i][u], v = ancestor[i][v];
    }
    return ancestor[0][u];
 
 
}
 
int N, M, u, v, w;
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); 
    cin >> N >> M;
    vector<node3> vv;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        vv.push_back({ u,v,w });
    }
    auto mst = MST_Kruskal(N, vv);
 
    result r = treefy(adj_list, 1, true);
    vector<vector<int>> max_dp(r.max_level + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; i++) max_dp[0][i] = dist2[i];
    for (int jump = 1; jump <= r.max_level; jump++)
    {
        for (int here = 1; here <= N; here++)
        {
            int tmp = ancestor[jump - 1][here];
            if (tmp == -INF) continue;
            max_dp[jump][here] = 
                max(max_dp[jump - 1][here], max_dp[jump - 1][tmp]);
        }
    }
 
    for(int i=0;i<M;i++)
    {
        auto [s, e, w] = vv[i];
        int l = lca(s, e, level, ancestor);
 
        int mx = -1;
        int diff = level[s] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][s]), s = ancestor[j][s];
            diff >>= 1;
        }
        diff = level[e] - level[l];
        for (int j = 0; diff; j++) {
            if (diff & 1) mx = max(mx, max_dp[j][e]), e = ancestor[j][e];
            diff >>= 1;
        }
 
        cout << mst + w - mx << '\n';
    }
 
    return 0;
}
cs










반응형
저작자표시 (새창열림)

'Programming > Problem Solving' 카테고리의 다른 글

double과 관련된 핸들링  (0) 2021.12.26
백준 4103 ATM  (1) 2020.05.05
BST 트리 구현  (0) 2020.04.09
인접행렬, 인접리스트  (1) 2020.04.09
[코뽕] AtCoder Beginner Contest 161 - D Lunlun Number  (0) 2020.04.05

여기, 여기, 여기를 보면 기본 개념에 대해서는 얼추 파악할 수 있다.

LCA를 구할때 쓰는 Binary Lifting도 sparse table의 일종이다.

기본 개념은 O(N)걸리는 쿼리를 전처리 작업을 통해서 O(log N)이나 O(1)로 줄인다고 하는것

그걸 위해서 A[N] 이란게 있다고 하면 ST[log2(N)][N] 이런 스케일로 테이블 정의하고..

ST[0][N] = A[N]으로 초기화 한다음에

REP1(i, max_level)REP(j,N) ST[i][j] = ST[i-1][어쩌구]..저쩌구 이런식으로 한다.

i가 1증가할때 마다 2배씩 뛰는건데 자세한건 위의 링크를 참조하자.


기본LCA문제를 풀 때에도 ancestor 만들때 위의 기술을 사용하고,

단순히 합성함수를 효율적으로 구하는 문제에서도 사용된다.

트리 정점 a, b의 경로에서 가장 가중치 큰거나 작은거 하나 출력하는 문제에서도 사용되고,

a,b경로중 k번째 정점을 찾는 문제에서도 사용된다.


아직 나도 통달한건 아니라 이정도로 기록해둔다.

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

단절점(Cut Vertex, Articulation Point)과 단절선(Bridge)  (0) 2020.05.03
강한연결요소(SCC, Strongly Connected Component), 코사라주, 타잔  (0) 2020.05.03
공통조상(LCA, Lowest Common Ancestor) 알고리즘  (0) 2020.04.29
위상정렬(Topological Sort)  (0) 2020.04.23
트라이(Trie)  (0) 2020.04.22

여기보면 개념자체는 간단한다.


$O(N)$ 나이브 구현

더깊은 애부터 하나씩 올려서 만나는데 까지 해보는 방식으로 해보면 된다.

구현도 트리로 인한 복잡성은 약간 있지만, 나이브한 편이고 내가 구현해본 건 다음과 같다. 이 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
const int INF = (int)1e9;
 
 
//무방향그래프를 인풋으로 받아, 특정 정점을 루트를 가지는 방향그래프(트리)로 만들어준다.
struct result { vector<vi> tree; int root; vi parent, level; };
result treefy(vector<vi>& adj_list, int root = -1, bool base1 = false) {
    int max_v = (int)adj_list.size();
    vector<vi> tree(max_v);
    if (root == -1)
    {
        //find root(왼쪽이 parent인경우만 성립)
        map<int, int> m;
        for (int i = (int)base1; i < max_v; i++)
            for (auto a : adj_list[i]) m[a]++;
        for (int i = (int)base1; i < max_v; i++)
            if (m[i] == 0) { root = i; break; }
    }
    vi parent(max_v), level(max_v);
    function<void(int, int, int)> dfs = [&](int node, int par, int lv) {
        parent[node] = par, level[node] = lv;
        for (auto adj : adj_list[node]) {
            if (adj == par) continue;  // 부모방향 간선제거
            tree[node].push_back(adj);
            dfs(adj, node, lv + 1);
        }
    };
    dfs(root, -INF, 1);
 
    return { tree, root, parent, level };
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T; cin>>T;while(T--){
        int N;cin>>N;
        vvi adj_list(N + 1);
        REP(i,N - 1)
        {
            int u,v;cin>>u>>v; adj_list[u].push_back(v);
        }
        result r = treefy(adj_list, -1, true);
        int a,b;cin>>a>>b;
        if (r.level[a] > r.level[b]) swap(a, b);
        while (r.level[a] < r.level[b]) b = r.parent[b];
        while (a != b) a = r.parent[a], b = r.parent[b];
        cout << (a) << '\n';
    }
 
    return 0;
}
cs


$O(log N)$ 구현 (쿼리 형태면 $O(M \times log N)$)

역시 여기를 보면 과정을 이해하기 쉽도록 설명되어 있다. 다만, 그 구현과정에서 실수가 들어가기 쉬운데, 이건 내가 직접 구현하기보다 구현되어 있는걸 가져다 쓰는 형식이 좋을 것 같다. 내 라이브러리와 합쳐진 버전은 다음과 같다.

이 문제의 답안이기도 하다.

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
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = (int)1e9;
 
//무방향그래프를 인풋으로 받아, 트리로 만들어준다.LCA를 위한 작업도 해준다.
struct result {vvi tree;int root;vi parent,level; int max_level;vvi ancestor;};
result treefy(vector<vi>& adj_list, int root = -1, bool base1 = false) {
    int max_v = (int)adj_list.size();
    vector<vi> tree(max_v);
    if (root == -1)
    {
        // find root(왼쪽이 parent인경우만 성립하는듯, 안그러면 root가 여러개다)
        map<int, int> m;
        for (int i = (int)base1; i < max_v; i++)
            for (auto a : adj_list[i]) m[a]++;
        for (int i = (int)base1; i < max_v; i++)
            if (m[i] == 0) { root = i; break; }
    }
    vi parent(max_v), level(max_v);
    int max_level = (int)floor(log2(max_v));
    // ac[y][x] :: x의 2^y번째 조상을 의미
    vvi ac(max_level + 1, vi(max_v, -INF));
    function<void(int, int, int)> dfs = [&](int node, int par, int lv) {
        parent[node] = par, level[node] = lv;
        ac[0][node] = par;  // 첫번째(2^0) 조상은 부모
        for (auto adj : adj_list[node]) {
            if (adj == par) continue;  // 부모방향 간선제거
            tree[node].push_back(adj);
            dfs(adj, node, lv + 1);
        }
    };
    dfs(root, -INF, 1);
    for (int i = 1; i <= max_level; i++) {
        for (int j = 1; j < max_v; j++) {
            int tmp = ac[i - 1][j];
            if (tmp == -INF) continue;
            ac[i][j] = ac[i - 1][tmp];
        }
    }
 
    return { tree, root, parent, level,max_level, ac };
}
 
int lca(int u, int v, int max_level, vi& level, vvi& ancestor)
{
    if (level[u] < level[v]) swap(u, v);  // b가 더 깊도록 조정
    int diff = level[u] - level[v];
    for (int i = 0; diff; i++) {
        if (diff & 1) u = ancestor[i][u];  //b를 올려서 level을 맞춘다.
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = max_level; i >= 0; i--) {
        // a와 b가 다르다면 현재 깊이가 같으니, 깊이를 a,b동시에 계속 올려준다.
        if (ancestor[i][u] != ancestor[i][v]) 
            u = ancestor[i][u], v = ancestor[i][v];
    }
    return ancestor[0][u];
}
 
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    int N; cin >> N; vvi adj_list(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    result r = treefy(adj_list, 1, true);
    int m; cin >> m; for (int z = 0; z < m; z++)
    {
        int a, b; cin >> a >> b;
        int ans = lca(a, b, r.max_level, r.level, r.ancestor);
        cout << (ans) << '\n';
    }
    return 0;
}
cs




반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

강한연결요소(SCC, Strongly Connected Component), 코사라주, 타잔  (0) 2020.05.03
스파스 테이블(Sparse Table), Binary Lifting  (0) 2020.05.01
위상정렬(Topological Sort)  (0) 2020.04.23
트라이(Trie)  (0) 2020.04.22
KMP( Knuth, Morris, Prett)  (0) 2020.04.20

여기참조

 

유향그래프가 있을 때, 오더링 하는 방법론에 대한게 위상정렬이고, 

DFS를 이용한 방법(DFS Spanning Tree)과

Queue를 이용한 방법(indgree)이 있다. 나한테는 이방식이 편했다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(DAG)여야 한다.

 

사이클이 있는 경우는 오더링이 불가 하고, DFS와 Queue모두 이를 중간 과정을 통해 디텍트 할 수 있다.

 

위키피디아의 다음 설명을 읽어보자

위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 

그렇다면 위상정렬과 DAG과의 관계는 무엇인가.. 위상정렬이 가능하려면 (사이클이 없는) DAG이어야 한다고 말할 수 있다.

 

위상정렬에 대한 풀어보면 좋은 문제는 다음과 같다.

 

백준 ACM Craft : 바닐라 한데, 제약조건이 좀 빡빡하다(100,000이라 adjacent matrix 사용 불가)

 

 

BFS방식

여기 예제를 통한 설명 좋다.

일반 BFS와의 차이점은 사이클 처리를 위해서 while(q.empty()==false) 이걸로 루프돌리는게 아니라,

for(int i=0;i<N;i++) 이걸로 루프돌리는게 특이하고, 인접리스트와 별도로 in-edge카운팅해줘서 0이되는것만 enqueue하면 된다.

아래는 내가 구현하고 이 문제로 검증한 코드이다.

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
#include <bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
#define OUT(x) {cout << (x) << '\n'; }
#define IN(n) int n;cin>>n
 
int32_t main()
{
    FastIO; IN(N); IN(M);
    vi in(N + 1); // in-edge를 관리해주는게 핵심
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        IN(u); IN(v); adj_list[u].push_back(v); in[v]++;
    }
    queue<int> q;
    function<void(int n)> enqueue = [&](int n) {
        if ((in[n]--) > 0) return;
        q.push(n);
    };
    vi ans;
    REP1(i, N) enqueue(i);
    while (N--) {  // 정확히 n번 dequeue로 끝난다.
        if (!q.size()) { break; }//cycle!
        int n = q.front(); q.pop();
        ans.push_back(n);
        for (auto adj : adj_list[n]) {
            enqueue(adj);
        }
    }
    for (auto a : ans) cout << a << ' ';
    return 0;
}
 cs

 

 

DFS방식

BFS방식이 좀 더 직관적이긴 하지만, DFS방식은 DP연계가 쉽다는 점에서 알아둘 필요가 있다.
DFS방식은 말하자면 다음과 같다.
DFS로 방문할 수 있는 모든 노드를 재귀적으로 방문한뒤..
방문할 수 있는 next가 없으면
topological_sort 와 같은 큐에 데이터를 집어넣고, 이를 역순으로 표시
여기를 보면 알기 쉽게 설명돼있다. 위의 BFS버전과 같은 문제에 대한 답안이기도 하다.
DFS의 경우는 in-edge관리를 안해줘도 돼서 어떻게 보면 훨씬 더 다루기 쉽다. (사이클 처리는 대신 약간 복잡)
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
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
struct result { bool cycle; vi sorted; };
result topological_sort(int max_v, int start_v, vvi& adj_list, bool base1=false) {
    if (base1) max_v++;
    // cycle 검출을 위해 finish배열 하나더 기용해준다.
    // visit되고 finish되기전에 다시 방문되면 사이클로 보는것
    vi visit(max_v), finish(max_v);
    result r = { false, vi() };
    deque<int> sorted; bool cycle = false;
    function<void(int)> dfs = [&](int v) {
        visit[v] = 1;
        for (auto adj : adj_list[v]) {
            if (visit[adj] == 0) dfs(adj);
            else if (finish[adj] == 0) {
                cycle = 1;// visit은 1인데, finish 는 0으로 들어왔다? cycle!
            }
        }
        finish[v] = 1;
        sorted.push_front(v);
    };
    if (start_v == -1) {
        for (int i = (int)base1; i < max_v; i++) 
            if (visit[i] == 0) dfs(i);
    }
    else dfs(start_v);
    return { cycle, vi(sorted.begin(), sorted.end()) };
}
 
int32_t main()
{
    int N, M; cin >> N >> M;
    //vi in(N + 1);  // DFS버전에서는 in-edge관리를 안해도 된다.
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; adj_list[u].push_back(v);
    }
 
    // 일단 아이디어는 DFS돌려서 말단까지 가고,
    // 거기서 부터 stack에 넣어주면 위상정렬 정순위가 된다는것.
    result r = topological_sort(N, -1, adj_list, true);
    for (auto a : r.sorted) cout << a << ' ';
    return 0;
}
 cs
그런데, visit, finish 처리를 위처럼 하면 경로 카운팅 문제에서는 문제가 생긴다.
예를 들어 1번 정점에서 2번 정점으로의 경로가 하나가 아니라 여러개인경우,
visit만 1인상태에서 finish전에 여러경로를 다 세주어야 하는데,
if (visit[adj] == 0) dfs(adj) 이부분 때문에 하나의 경로만 카운팅 되는 것
 

 

 

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

스파스 테이블(Sparse Table), Binary Lifting  (0) 2020.05.01
공통조상(LCA, Lowest Common Ancestor) 알고리즘  (0) 2020.04.29
트라이(Trie)  (0) 2020.04.22
KMP( Knuth, Morris, Prett)  (0) 2020.04.20
기하  (0) 2020.04.19

개념은 매우 간단하다. 여기보면 이해하기 쉬운편(PS관점에서 trie에 관한 다른 인사이트도 얻을 수 있다)

단어가 끝나는 지점에 마킹해야함에 유의


글자단위 Trie

아래는 내가 구현해본 Trie코드이며, 이 문제의 답안이기도 하다.

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
 
struct trie {
    struct node { map<char, node> child; bool end = false; };
    node root;
    node* insert(node* n, char c) {
        auto& m = n->child;
        if (m.count(c) == 0) m[c] = node();
        return &m[c];
    }
    void insert(string s) {
        node* n = &root;
        int m = s.length();
        for(int j=0;j<m;j++) n = insert(n, s[j]);
        n->end = true;
    }
 
    node* find(node* n, char c) {
        auto& m = n->child;
        if (m.count(c) == 0) return NULL;
        return &m[c];
    }
 
    bool find(string s) {
        node* n = &root;
        int m = s.length();
        for (int j = 0; j < m; j++) {
            n = find(n, s[j]);
            if (n == NULL) return false;
        }
        return n->end;
    }
};
 
int32_t main()
{
    int N, M; cin >> N >> M;
    trie t;
    REP(i, N) {
        string s; cin >> s;
        t.insert(s);
    }
    int ans = 0;
    REP(i, M) {
        string s; cin >> s;
        ans += t.find(s) ? 1 : 0;
    }
    cout << ans << '\n';
    return 0;
}
cs


단어단위 Trie

이건 응용인데 글자단위와 비슷한 개념으로 풀 수 있다. 이 문제 참조.

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

공통조상(LCA, Lowest Common Ancestor) 알고리즘  (0) 2020.04.29
위상정렬(Topological Sort)  (0) 2020.04.23
KMP( Knuth, Morris, Prett)  (0) 2020.04.20
기하  (0) 2020.04.19
포화이진트리(perfect binary tree), 완전이진트리  (2) 2020.04.19

여기를 보면 기본 개념에 대해서 쉽게 익힐 수 있다. 본 글에서는 그럼에도 헷갈리는 점 위주로 써본다.

전체 문자열 텍스트T(길이 N)와, 찾으려는 패턴P(길이 M)가 있을때, 나이브하게 구현하면 $O(NM)$이 걸린다.

KMP를 사용하면 이를 $O(N+M)$으로 줄일 수 있다.


Pi함수(실패함수, 오버랩함수)

Pi함수는 위의 텍스트T와 패턴P중에서 패턴P에 대해서 미리 계산해놓는 함수이다. 실패함수라고도 하며, 문자열 매칭이 미스났을때 어디까지 back할지 정보를 제공한다.

pi[i]는 실패후에 앞부분에 이미 매칭한걸로 치는 오버랩구간을 의미하기 때문에 나는 오버랩함수라고 부른다.

인덱스01234567891011
텍스트ABCDABCDABEE
패턴ABCDABE

예를 들어 위와 같은 형태가 있을때, 6번 인덱스에서 불일치가 일어났는데 


인덱스01234567891011
텍스트ABCDABCDABEE
패턴ABCDABE

위와 같이 텍스트에서 불일치가 발생한 C왼쪽 부분에서 이미 매칭한걸로 치는 오버랩 구간은 최대한 길게 잡았을때 AB임을 알 수 있다. 

좀더 길게 DAB로 잡고 싶어도 패턴이 D로 시작하지 않는다. 아예 ABCDAB로 잡으려고 하면 이미 실패한 패턴이고 제자리걸음이라 택할수 없다.


인덱스01234567891011
텍스트ABCDABCDABEE
패턴ABCDABE

따라서 위와 같이, 텍스트의 C왼쪽 postfix AB와 패턴의 prefix AB를 위처럼 오버랩시키고 나면 인덱스 6부터 다시 비교를 시작하면 된다.

오버랩함수가 2일때 패턴을 보면 오른쪽으로 6-2=4칸 점프(?)한걸 볼 수 있는데,

이처럼 오버랩함수의 값이 오히려 작으면 작을수록 점프를 많이한다.

오버랩함수가 5이면 6-5=1이라서 한 칸만 오른쪽으로 이동한다.

오버랩이 많이 되면 오른쪽이동량은 적은대신 이미 많이 오버랩되어 있으므로 적게 추가로 매칭되면 매칭이 완성되는 장점이 있으므로 무조건 오버랩이 적게되서 오른쪽으로 점프를 많이 하는게 좋은건 아니다.


그래서 pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 최대 prefix == suffix길이로 세팅한다.

문자열 "ABAABAB"의 pi배열을 구해봅시다.

 i

부분 문자열 

 pi[i]

 0

A

 0

 1

AB 

 0

 2

ABA

 1

 3

ABAA

 1

 4

ABAAB

 2

 5

ABAABA

 3

 6

ABAABAB

 2

팰린드롬 개념이 아님에 주의!


문자열 "ABABABC"의 pi배열을 구해봅시다.

 i

부분 문자열 

 pi[i]

 0

A

 0

 1

AB 

 0

 2

ABA

 1

 3

ABAB

2

 4

ABABA

 3

 5

ABABAB

 4

 6

ABABABC

 0

prefix와 posfix가 오버랩되도 문제없음에 주의(위의 초록색 글자)


이해하기는 쉽지만, 효율적으로 $O(M)$에 pi함수를 구하는건 약간 어렵다.

그래도 맨위 링크를 통해 공부하고 아래와 같은 함수를 짤 수 있었다.

1
2
3
4
5
6
7
8
9
10
using vi = vector<int>;
vi getPi(string p) {
    int m = (int)p.length();
    vi pi(m);
    for (int j = 0, i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}
cs

오버랩을 while로 여러번 적용하는 케이스가 발생하는 것은 아래를 참조하자.


불일치 발생

오버랩 함수 1차적용


오버랩 함수 2차 적용

오버랩함수 3차적용

"AABAAA"에 대해서 Pi를 구해보면 Pi = {0,1,0,1,2,2} 이렇게 나오는데 중간에 0이 섞이기도 하고 마지막 2가 찍힐때 내가 원하던 조금 복잡한 다이나믹이 나오니 필요하면 검토해보자.

Pi함수가 갖는 오버랩의 의미에 대해서는 백준 1305 광고 문제를 풀어보면 직접적인 도움이 된다.

KMP

Pi함수를 이해했다면 KMP는 이를 이용해서 어렵지 않게 아래와 같이 짤 수 있다.
(물론 스크래치부터 짜면 구현실수를 많이 포함되게 된다. 대략적인 흐름만 이해하고 복사해서 쓰자)
이 문제의 답안이기도 하다.
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
#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
vi getPi(string p) {
    int m = (int)p.length();
    vi pi(m);
    for (int j = 0, i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}
//p가 발견된 위치들을 리턴(0 base)
vi KMP(string t, string p) {
    int n = (int)t.length(), m = (int)p.length();
    vi pi = getPi(p);
    vi r;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && t[i] != p[j]) j = pi[j - 1];
        if (t[i] == p[j]) {
            if (j == m - 1) 
                r.push_back(i - m + 1), 
                j = pi[j];  //j=0이 아님에 주의(오버랩고려)
            else j++;
        }
    }
    return r;
}
 
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
 
    string t, p;
    getline(cin, t), getline(cin, p);
    vi v = KMP(t,p);
    cout << v.size() << '\n';
    for (auto a : v)cout << a + 1 << ' ';
    cout << '\n';
    return 0;
}
cs






반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

위상정렬(Topological Sort)  (0) 2020.04.23
트라이(Trie)  (0) 2020.04.22
기하  (0) 2020.04.19
포화이진트리(perfect binary tree), 완전이진트리  (2) 2020.04.19
트리DP  (0) 2020.04.15

 

CCW(Counter Clock-Wise)

이론적으로는 외적을 구하는것 같은데, 알고리즘 기하문제를 풀기위해 사용한다. 

 

용도1. 다각형 면적구하기

점3개를 주면 꼭지점 3개로 해석해 면적을 구해준다. (정확히는 평행사변형의 면적을 주는건데 삼각형의 면적이 더 유용해서 2로 나눠서 쓴다)

이걸 사용하면 도형의 외각선 좌표들이 순서대로 주어질때 아래처럼 삼각형으로 쪼개면 다각형의 면적을 구할 수 있다.

 

점 3개가 순서대로 반시계 방향을 이루면 +값을 가지고 시계방향을 이루면 -값을 가진다. (오른손 법칙을 떠올리면 좋다)따라서 최종결과에 절대값을 씌워야 할 수 있다.
 
재밌는 점은 아래와 같은 볼록다각형에 대해서도 자동으로 삭감이 이루어지면서 면적계산이 제대로 된다는 점이다.
 
 
내 소스는 다음과 같다. 이 문제의 답안이기도 하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
 
struct point { int x, y; };
double CCW(point A, point B, point C) {
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}
 
int32_t main()
{
    vector<point> v;
    int N, x, y; cin >> N; REP(i, N)cin >> x >> y, v.push_back({ x,y });
 
    double sum = 0;
    for (int i = 1; i < N-1; i++) {
        sum += CCW(v[0], v[i], v[i + 1]);
    }
    cout.precision(1);
    cout << fixed << (double)abs(sum)/2 <<'\n';
    return 0;
}
 cs
 

용도2. 점 3개의 방향성 구하기

위에서 반시계 방향일때 CCW가 +값을 리턴한다고 했는데 +,0,-를 이용해서 방향성을 판단할 수 있다는 것. 아래 선분교차 판단 등에 쓰인다.

 

용도3. 선분교차 판단

여기에 설명 잘 나와있어서 보고 이해하면 될 것 같다.

주의할점은 CCW를 1,0,-1을 리턴하는 것으로 변경하지 않으면 long long을 사용해도 오버플로가 날 수 있다는 점이다(아래코드 보면 CCW간 곱셈이 들어가서..)

아래코드를 나중에 활용하자. 이 문제의 답안이기도 하다.

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 <bits/stdc++.h>
#define int long long
using namespace std;
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
 
struct point { double x, y; };
double CCW(point A, point B, point C, bool sign_only=true) {
    double r = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
    if (sign_only == false) return r;
    if (r == 0)return 0;
    return r > 0 ? 1 : -1;
}
struct line { point s, e; };
//touch_ok가 false이면, 두 선분이 교차하지 않고 만나기만 하는 경우에는 false를 리턴
bool Intersect(line x, line y, bool touch_ok=false) {
    point a = x.s, b = x.e;
    point c = y.s, d = y.e;
    double ab = CCW(a, b, c) * CCW(a, b, d);
    double cd = CCW(c, d, a) * CCW(c, d, b);
    if (ab == 0 && cd == 0) { // 이건 두 선분이 평행한 경우
        pair<double, double> aa = { a.x, a.y }, bb = { b.x,b.y }, 
            cc = { c.x, c.y }, dd = { d.x,d.y };
        if (aa > bb)swap(aa, bb);
        if (cc > dd)swap(cc, dd);
        if(touch_ok) return cc <= bb && aa <= dd; // 0이면 점끼리 만나는 것
        return cc < bb && aa < dd; // a<d이면서 b,c가 교차하면 선분
    }
    if(touch_ok) return ab <= 0 && cd <= 0; // 0이면 두 선분이 한점에서 만나는 것
    return ab < 0 && cd < 0; // 이게 기본. 각선분에서 나머지 2개점 방향이 달라야 교차
}
 
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
#endif
 
    vector<line> l;
    double a, b, c, d; REP(i, 2)cin >> a >> b >> c >> d, l.push_back({ a,b,c,d });
    cout << (Intersect(l[0],l[1])?1:0) <<'\n';
    return 0;
}
 cs

 

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

트라이(Trie)  (0) 2020.04.22
KMP( Knuth, Morris, Prett)  (0) 2020.04.20
포화이진트리(perfect binary tree), 완전이진트리  (2) 2020.04.19
트리DP  (0) 2020.04.15
세그멘트 트리  (0) 2020.04.13

이진으로 꽉차있는 다음과 같은 트리를 말한다.

leaf node에서 오른쪽에서 부터 몇개 비면 완전이진트리라고도 한다. (때로는 포화이진트리를 완전이진트리라고 부르기도 한다.)

배열로 표현하기 좋다.

1베이스로 볼때.. 자식 노드는 2n, 2n+1 인덱스에 위치함을 알 수 있다.
레벨별 인덱스 위치는 1레벨이 1이고 2레벨이 2이고, 3레벨이 4이고, 4레벨이 8인것을 보아 
n레벨의 시작인덱스 위치는 $2^n$임을 알 수 있다.

포화이진트리코드

아래는 내가 작성한 코드이며, 배열로 포화이진트리를 받아서 preorder로 방문해준다.
이 문제의 답에 쓰이기도 했다.
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 <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
 
//포화 이진 트리 (0-base)
struct perfect_binary_tree {
    vi v;
    int n;
    perfect_binary_tree(int* arr, int arr_size) {
        v.assign(arr, arr + arr_size);
        n = arr_size;
    }
    perfect_binary_tree(vi& v) {
        this->v = v;
        n = (int)v.size();
    }
    vi preorder() {
        vi ret;
        function<void(int)> dfs = [&](int ix) {
            ret.push_back(v[ix]);
            int l = (ix+1) * 2-1;
            int r = (ix+1) * 2 ;
            if (l < n-1) dfs(l);
            if (r < n-1) dfs(r);
        };
        dfs(0);
        return ret;
    }
};
 
int32_t main()
{
    vi v = { 1,2,3,4,5,6,7,8 };
    perfect_binary_tree t(v);
    vi p = t.preorder();
    for(int a:p)cout << a << ' ';
    return 0;
}
cs




반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

KMP( Knuth, Morris, Prett)  (0) 2020.04.20
기하  (0) 2020.04.19
트리DP  (0) 2020.04.15
세그멘트 트리  (0) 2020.04.13
최소신장트리(MST, Minimum Spanning Tree)  (0) 2020.04.12

트리의 속성

정점이 N이면 간선의 개수는 N-1개이다.

인접리스트를 트리로 만들때 root노드는 아무거로나 선택해도 답에 지장이 없(었다 지금까지는).

인접리스트를 트리로 전환하기

간선 가중치 없는 무방향 인접리스트를 방향그래프 형태의 트리로 전환해준다.

이렇게 했을때 이점은 parent방향으로 이동하는 간선을 끊어버리기 때문에 순서를 매겨서 루트부터 전 노드 방문하기가 편해진다.

아래 코드에서 treefy()를 재활용하면 된다.이 문제의 답안이기도 하다. 하나의 함수로 패키징하기 위해서 람다(lambda) 함수를 사용했고, 재귀를 가능하게 하기 위해서 std::function을 사용했다.

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
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using vi = vector<int>;
const int INF = (int)1e9, MAXN = 100001;
 
//무방향그래프를 인풋으로 받아, 특정 정점을 루트를 가지는 방향그래프(트리)로 만들어준다.
struct result { vector<vi> tree; int root; vi parent, level; };
result treefy(vector<vi>& adj_list, int root = -1, bool base1 = false) {
    int max_v = (int)adj_list.size();
    vector<vi> tree(max_v);
    if (root == -1)
    {
        //find root(왼쪽이 parent인경우만 성립)
        map<int, int> m;
        for (int i = (int)base1; i < max_v;i++)
            for (auto a : adj_list[i]) m[a]++;
        for (int i = (int)base1; i < max_v; i++) 
            if (m[i] == 0) { root = i; break; }
    }
    vi parent(max_v), level(max_v);
    function<void(int, int,int)> dfs = [&](int node, int par,int lv) {
        parent[node]=par,level[node] = lv;
        for (auto adj : adj_list[node]) {
            if (adj == par) continue;  // 부모방향 간선제거
            tree[node].push_back(adj);
            dfs(adj, node, lv+1);
        }
    };
    dfs(root, -INF, 1);
 
    return { tree, root, parent, level };
}
 
int N, R, Q, U, V;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> R >> Q;
    vector<vi> adj_list(N + 1);
    REP(i, N - 1) {
        cin >> U >> V;
        adj_list[U].push_back(V);
        adj_list[V].push_back(U);
    }
    vector<vi> tree = treefy(adj_list, R).tree;
 
    vi dp(MAXN, INF);
    function<int(int)> cnt_sub = [&](int root) {
        int& res = dp[root];
        if (res < INF) return res;
        int sum = 1; for (auto adj : tree[root]) sum += cnt_sub(adj);
        return res = sum;
    };
    cnt_sub(R);
 
    while (Q--) cin >> U, cout << dp[U] << '\n';
    return 0;
}
 cs

 

랜덤으로 트리 인풋만들기

디버깅을 하거나 문제를 출제하다보면, 랜덤한 트리를 만들 필요가 있는데, 임의로 간선을 선택하다보면 사이클이 생겨서 잘 안된다.

이럴때 MST구할때 쓰는 크루스칼 알고리즘을 사용하면 간단하게 사이클 없는 트리를 만들 수 있다.

아래는 내가 구현한 코드이다.

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 <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
struct union_find {
    vi parent;
    union_find(int n) {
        parent.resize(n + 1);
        REP1(i, n)parent[i] = i;
    }
    int find(int x) {
        int ox = x;
        while (parent[x] != x) x = parent[x];
        return parent[ox] = x;;
    }
 
    void uni(int x, int y) {
        int xp = find(x), yp = find(y);
        parent[yp] = xp;
    }
};
 
int main()
{
    int N = 7;
    cout << N << '\n';
    vvi adj_list(N + 1);
    union_find uf(N);
    int U, V; 
    REP(i, N - 1) {  // 트리는 반드시 N-1개의 간선을 가진다.
        A:
        U = rand() % N + 1;
        V = rand() % N + 1;
        if (uf.find(U) == uf.find(V)) goto A;  // 사이클을 가지면 채택하지 않는다.
        uf.uni(U, V);
        cout << U << ' ' << V << '\n';
        adj_list[U].push_back(V);
        adj_list[V].push_back(U);
    }
    return 0;
}
 
 cs

돌리면 아래와 같은 결과를 출력한다.

1
2
3
4
5
6
7
7
7 2
7 6
4 3
6 1
4 7
1 5
 cs

 

트리 모양을 툴로 확인해보면 다음과 같다.

 
 

 

 
 

주어진 그래프가 트리인지 판정하기

일단 트리는 undirected graph에서만 정의되기 때문에, undirected로 한정할 수 있고,

이 문제의 경우처럼, 유니온파인드로 판정하는게 비교적 쉬운 방법인 것 같다.

 

 

 

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

기하  (0) 2020.04.19
포화이진트리(perfect binary tree), 완전이진트리  (2) 2020.04.19
세그멘트 트리  (0) 2020.04.13
최소신장트리(MST, Minimum Spanning Tree)  (0) 2020.04.12
유니온 파인드(Union-Find), 서로소 집합(Disjoint Set)  (0) 2020.04.10

여기 참조


작성중

반응형
저작자표시 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

포화이진트리(perfect binary tree), 완전이진트리  (2) 2020.04.19
트리DP  (0) 2020.04.15
최소신장트리(MST, Minimum Spanning Tree)  (0) 2020.04.12
유니온 파인드(Union-Find), 서로소 집합(Disjoint Set)  (0) 2020.04.10
그래프 최장거리, 최대이득, 최다비용등  (1) 2020.04.09

+ Recent posts

티스토리툴바