문제 정의

  • 구간의 합을 여러번 구하고, 수정할때
    • 그냥 구간의 합을 구할 경우 : N개를 탐색 >> O(N)
    • 세그먼트 사용할 경우 : O(NlgN)

문제 접근

  • segment tree의 빈 리스트를 먼저 만듬
    • 재귀함수를 통해 초기 세그먼트 트리 만들때, 업데이트할때, 구간합 구할때를 만들어줌

시간복잡도

  • 구간 합 구하기, 수정하기 : O(lgN)

대표예제 : 백준 2042 구간 합 구하기

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
#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
int nums[1000010];
 
ll make(int node, int st, int en) {
    // 시작값과 끝값이 같으면 종료
    if(st == en) return tree[node] = nums[st];
    
    int mid = (st+en)/2;
    ll rsl = make(node*2, st, mid);
    ll rsr = make(node*2+1, mid+1, en);
    // st ~ mid, mid+1 ~ en 의 합으로 리턴
    return tree[node] = rsl + rsr;
}
 
void update(int node, int st, int en, int idx, ll diff) {
    if(idx < st || en < idx) return;
    tree[node] += diff;
    if(st != en) {
        int mid = (st+en)/2;
        update(node*2, st, mid, idx, diff);
        update(node*2+1, mid+1, en, idx, diff);
    }
    return;
}
 
ll sumt(int node, int st, int en, int li, int ri) {
    if (ri < st || en < li) return 0;
    if(li <= st && en <= ri) return tree[node];
    
    int mid = (st+en)/2;
    ll rsl = sumt(node*2, st, mid, li, ri);
    ll rsr = sumt(node*2+1, mid+1, en, li, ri);
    
    return rsl + rsr;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M,K; cin >> N >> M >> K;
    for(int i=0; i<N; i++) cin >> nums[i];
    
    // 세그먼트 크기 초기화
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    // 초기 세그먼트 트리 생성
    make(1,0,N-1);
    
    for(int i=0; i<M+K; i++) {
        int a,b; cin >> a >> b;
        ll c; cin >> c;
        if(a==1) {
            ll diff = c - nums[b-1];
            nums[b-1] = c;
            // 구간 업데이트
            update(1,0,N-1,b-1, diff);
        } else {
            // 구간합 구함
            cout << sumt(1,0,N-1,b-1,c-1) << '\n';
        }
    }
    return 0;
}
 
cs

문제 유형

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Bellman Ford, 벨만 포드 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

문제 정의

  • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
    • 밸만 포드 : O(VE)
    • 문제의 유형에 따라서 적합한 알고리즘 선택
    • Floyd를 사용할경우 O(V^3)
    • 다익스트라 : O(ElgE)
      • 음수의 간선 확인 가능
  • 음수로 인한 거리 무한감소 사이클 확인 가능

문제 접근

  • 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)
  • dist배열의 시작 노드값을 0으로 만듬
  • 모든 간선에 대해서, 간선을 지나는 경우 비용이 더 감소할 경우 업데이트
  • 위 과정을 노드의 개수만큼 반복
  • 마지막 한번 모든 간선에 대해서, 위 과정을 반복
    • 이때 비용이 더 감소하는 경우가 있다면 >> 무한 사이클 확인

시간복잡도

  • 모든 간선을 : O(V)
    • 노드의 개수만큼 반복 : O(E)
    • O(V*E)

대표예제 : 백준 11657 타임머신

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
#include <iostream>
#include <tuple>
#include <vector>
 
using namespace std;
typedef tuple<int, int, int> ti3;
typedef long long ll;
 
const int inf = 1e8+10;
 
// 거리배열 생성
ll dist[510];
ti3 edge[6010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    fill(dist, dist+510, inf);
    
    for(int i=0; i<E; i++){
        int a,b,c; cin >> a >>b >> c;
        edge[i] = {a,b,c};
    }
    
    // 시작노드 0으로 초기화
    dist[1] = 0;
    
    // 모든 간선을 노드 갯수만큼 반복
    for(int j=0; j<V; j++) {
        for(int i=0; i<E; i++) {
            int a,b,c; tie(a,b,c) = edge[i];
            
            // 아직 거치지 않은 점일경우
            if(dist[a] == inf) continue;
            // a점을 거친 경우 거리가 더 작아질경우
            if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
        }
    }
    
    // 사이클 확인
    for(int i=0; i<E; i++) {
        int a,b,c; tie(a,b,c) = edge[i];
        
        if(dist[a] == inf) continue;
        // a점을 거친 후 거리가 작아질경우 사이클
        if(dist[b] > dist[a] + c) {
            cout << -1 << '\n';
            return 0;
        }
    }
    
    for(int i=2; i<=V; i++) {
        if(dist[i] == inf) cout << -1 << '\n';
        else {
            cout << dist[i] << '\n';
        }
    }
    
    return 0;
}
 
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree, 세그먼트 트리 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

문제 정의

  • 문제유형
    • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
      • 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
      • Floyd를 사용할경우 O(V^3)
      • 다익스트라 : O(ElgE)

문제 접근

  • 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)

    • dist배열의 시작 노드값을 0으로 만듬

  • 시작 노드 연결된 간선을 모두 우선순위 큐에 넣음

  • 우선순위 큐가 가지고 있는 가장 작은 간선을 꺼냄

  • 이 간선을 통할경우 기존의 거리 값보다 작아질때, 해당 노드에 연결된 간선을 우선순위 큐에 추가

  • 위 과정을 우선순위 큐가 empty될때까지 반복


시간복잡도

  • 모든 간선을 우선순위 큐에 넣음 : ElgE


대표예제 : 백준 1913 최소비용 구하기

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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    cout << dist[en] << '\n';
    
    
    return 0;
}
 
cs

문제 유형

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Segment Tree, 세그먼트 트리 알고리즘  (0) 2021.02.14
[알고리즘] Bellman Ford, 벨만 포드 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07

문제 정의

  • 여러개의 노드에서 다른 노드까지의 최소 비용을 구할때
    • 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
    • Floyd를 사용할경우 O(V^3)
    • 다익스트라 : O(ElgE)
  • 노드 끼리의 순위가 일부 주어졌을떄, 전체 중 노드의 순위를 구하는 문제

문제 접근

  • 노드 A에서 B까지 가는데 다른 노드(C)를 거쳐서 갈경우 더 비용이 적으면 갱신
  • A,B,C를 모두 V번 반복

시간복잡도

  • 노드를 3번 순회해야함 >> O(V^3)

대표예제 : 백준 11404 플로이드

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 <vector>
 
using namespace std;
 
const int inf = 1e8+10;
int map[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&map[0][0], &map[109][110], inf);
    
    int V,E; cin >> V >> E;
    
    // 자기 자신으로 가는 비용은 0으로 초기화
    for(int i=1; i<=V; i++) map[i][i] = 0;
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        map[a][b] = min(c, map[a][b]);
    }
    
    
    for(int k=1; k<=V; k++) {
        for(int j=1; j<=V; j++) {
            for(int i=1; i<=V; i++) {
                // k를 거치는 경우 더 비용이 작으면 갱신
                // 이때 다음 노드는 k가 아닌, j에서 k로 가는 노드로 대체
                if(map[j][i] > map[j][k] + map[k][i]) {
                    map[j][i] = map[j][k] + map[k][i];
                }
            }
        }
    }
    
    for(int j=1; j<=V; j++) {
        for(int i=1; i<=V; i++) {
            if(map[j][i] == inf) cout << 0 << ' ';
            else cout << map[j][i] << ' ';
        }
        cout << '\n';
    }
        
    
    return 0;
    
}
cs

문제 유형

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Bellman Ford, 벨만 포드 알고리즘  (0) 2021.02.14
[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07
[알고리즘] 문자열 TRIE  (0) 2021.02.07

문제 정의

  • 모든 노드가 연결되어 있는 상태를 만들기 위해 최소한으로 필요한 비용을 구하는 문제

문제 접근

  • Kruscal
    • 가장 작은 간선 순으로 추가하는 방식
    • 기존에 추가된 노드를 추가하면 안되니까, 기존에 이미 추가되었던 간선이라면 추가하지 않음
    • 기존에 추가된 간선인지 확인하는 방법은 Union-Find로 결정
      • Union Find
        • 두개의 노드가 같은 그룹에 있는지 확인하는 방법
        • 모든 노드의 부모를 찾는 배열을 설정 후 모두 -1로 초기화 시킨다음
        • 간선을 추가할때마다 두 노드를 비교한 후, 부모가 같지 않으면 두 노드중 하나를 부모로 결정
        • 위 과정을 반복
    • 총 추가한 노드의 개수가 N개가 되면 종료

  • Prim

    • 현재 추가된 노드를 기준으로, 주변에 있는 간선 중 작은 간선부터 추가하는 방식
    • 처음에 한점을 잡고 인접한 간선을 모두 우선순위 큐에 추가
    • 우선순위 큐에서 하나씩 꺼냄
    • 꺼낸 후 이미 선택되었던 노드인지 확인
    • 선택되었던 노드아니라면, 노드의 주변에 있는 간선을 우선순위 큐에 추가
    • 총 추가한 노드의 개수가 N개가 되면 종료

시간복잡도

  • Kruscal
    • 모든 간선 정렬 : ElgE
    • V개의 노드 : V
    • E개의 간선 : E
    • 총 시간복잡도 : O(ElgE + V + E) = O(ElgE)
  • Prim
    • 모든 간선 우선순위 큐에 삽입 및 자동 정렬 : ElgE
    • V개의 노드 : V
    • E개의 간선 : E
    • 총 시간복잡도 : O(ElgE + V + E) = O(ElgE)

대표예제 : 백준 1197 최소 스패닝 트리

  • Kruscal
    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
    #include <iostream>
    #include <tuple>
    #include <algorithm>
     
    using namespace std;
    typedef tuple<int, int, int> ti3;
     
    int p[10010];
    ti3 edge[100010];
     
    int find(int v) {
        if(p[v] < 0) return v;
        return p[v] = find(p[v]);
    }
     
    // union find
    bool is_diff_group(int v1, int v2) {
        // 각 부모노드를 찾음
        v1 = find(v1); v2 = find(v2);
        
        // 부모가 같은 노드라면 종료
        if(v1==v2) return 0;
        
        if(p[v1] == p[v2]) p[v1]--;
        if(p[v1] < p[v2]) p[v2] =v1;
        else p[v1] = v2;
        return 1;
        
        
    }
     
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        
        int V,E; cin >> V >> E;
        fill(p, p+10010, -1);
        
        // E개의 간선 추가
        for(int i=0; i<E; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge[i] = {c,a,b};
        }
        sort(edge, edge+E);
        
        int cnt=1;
        int ans=0;
        for(int i=0; i<E; i++) {
            int a,b,c; tie(c,a,b) = edge[i];
            
            // 둘이 같은 그룹이라면 건너뜀
            if(!is_diff_group(a,b)) continue;
            
            // 다른그룹이라면
            cnt++;
            ans+=c;
            
            // 모든 노드 추가되면 종료
            if(cnt == V) break;
            
        }
        
        cout << ans << '\n';
        
        
        
        return 0;
    }
     
    		cs

  • Prim
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 <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<pair<int, int>> adj[10010];
bool chk[10010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E; cin >> V >> E;
    
    fill(chk, chk+10010, false);
    
    for(int i=0; i<E; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    // 한 간선에 대해서 인접한 간선 모두 추가
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(auto x : adj[1]) {
        pq.push(x);
    }
    chk[1] = 1;
    
    int cnt=1;
    int ans=0;
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(chk[ei] == true) continue;
        chk[ei] = true;
        cnt++;
        ans += ec;
        
        // 모든 노드 추가되면 종료
        if(cnt== V) break;
        
        // 인접한 간선 추가
        for(auto nq : adj[ei]) {
            int nc = nq.first;
            int ni = nq.second;
            if(chk[ni] == true)continue;
            pq.push(nq);
        }
        
    }
    
    cout << ans << '\n';
    
    return 0;
}
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07
[알고리즘] 문자열 TRIE  (0) 2021.02.07
[알고리즘] Topological Sort, 위상정렬  (0) 2021.02.07

문제 정의

  • A라는 문자열 안에, B 문자열이 어디에 몇번 속해있는지 확인

문제 접근 - KMP

  • B 문자열의 fail 배열를 먼저 구함
    • fail 배열 : 각각의 문자가 몇번 반복되었는지 확인
  • A 문자열과 fail 배열을 비교
  • KMP 개념이 다소 복잡해서, 잘 설명해주신 바킹독님 블로그를 참조하시면 좋을것 같습니다.
  • https://blog.encrypted.gg/857?category=773649

문제 접근 - Rabin-Karp

  • 문자열의 각각의 글자를 해시값으로 변환
  • 문자열의 각 위치에서 한글자씩 빼고, 더해주면서 해시값을 비교
    • 해시값 구할때 a = 302, p = 1e9+7 사용

시간복잡도

  • M : A 문자열의 길이
  • N : B 문자열의 길이
  • O(M+N)

대표예제 : 백준 1786 찾기

  • 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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<int> fail(string& s) {
    vector<int> f(s.size());
    int j=0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[j] != s[i]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    return f;
}
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    vector<int> f = fail(P);
    
    int j=0;
    vector<int> rs;
    for(int i=0; i<T.size(); i++) {
        while(j>0 && T[i] != P[j]) j = f[j-1];
        if(T[i] == P[j]) j++;
        if(j==P.size()) {
            rs.push_back(i+2-P.size());
            j = f[j-1];
        }
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    return 0;
}
 
 
cs

  • Rabin-Karp
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 <string>
 
using namespace std;
typedef long long ll;
 
ll a = 302;
ll p = 1e9+7;
ll powa[1000010];
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    int lenT = T.size();
    int lenP = P.size();
    if(lenT < lenP) {
        cout << 0 << '\n';
        return 0;
    }
    
    
    // a의 제곱값을 미리 구해놓음
    powa[0] = 1;
    for(int i=1; i<P.size(); i++) {
        powa[i] = powa[i-1] * a %p;
    }
    
    // 각각 P길이만큼 해시값 구함
    ll hashT = 0;
    ll hashP = 0;
    
    for(int i=0; i<P.size(); i++) {
        hashT = (hashT + T[i] * powa[P.size()-1-i]) %p;
        hashP = (hashP + P[i] * powa[P.size()-1-i]) %p;
    }
    
    vector<int> rs;
    if(hashT == hashP) rs.push_back(1);
    
    for(int i=1; i<=(T.size()-P.size()); i++) {
        // 앞글자 빼고, a만큼 곱해서 한자리씩 올리고, 새로 한글자 추가
        hashT = (hashT - T[i-1] * powa[P.size()-1])%p;
        // 음수인경우 확인
        if(hashT < 0) hashT += p;
        hashT = hashT * a % p;
        hashT = (hashT + T[i+P.size()-1] ) % p;
        if(hashT == hashP) rs.push_back(i+1);
        
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    
    return 0;
}
 
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 TRIE  (0) 2021.02.07
[알고리즘] Topological Sort, 위상정렬  (0) 2021.02.07

문제 정의

  • 접두사를 확인하는 문제
    • 접미사도 확인 가능 : 글자를 거꾸로 뒤집으면 됨

문제 접근

  • 각 문자열을 TRIE 배열에 저장하면서 문제 해결
    • TRIE 배열
      • 각 문자에 해당하는 노드가 저장되는 곳
      • 노드 포함해야하는 것
        • fin : 이 노드에서 문자열이 끝난적이 있음
        • child : 문자열중 이 노드의 다음 글자의 위치(TRIE 배열 중 인덱스)
  • TRIE 배열을 활용해서 문제 해결 가능
    • 접두사가 있는지 확인하는 문제
      • 이미 접두사가 있었는지 확인 : 각 노드의 fin 확인
      • 현재의 문자열이 접두사가 되는경우 : 문자열의 마지막 글자가 이미 있을떄

시간복잡도

  • 모든 문자열에 대해 순회 N
  • 문자열에 대해 한글자 한글자 순회 : M
  • O(NM)

대표예제 : 백준 5052 전화번호 목록

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
// 각 문자가 들어갈 node 정의
struct node {
    // 문자열이 끝날경우 fin = true;
    bool fin;
    // 다음 문자의 위치(TRIE 안에서의 인덱스)
    // 현재 문제는 숫자이므로 10개만, 알파벳이면 26개
    int child[10];
    
    // 초기화
    node() {
        fin = false;
        // child값이 -1일 경우, 다음 글자가 없음
        for(int i=0; i<10; i++) child[i] = -1;
    }
};
 
vector<node> trie;
bool sw;
 
// s : trie에 넣을 문자열
// idx : 문자열중 현재 글자의 위치 (인덱스)
// nodi : 삽입할 노드의 인덱스, 처음 시작은 0부터 시작
void insert(string& s, int idx, int nodi) {
    if(idx==s.size()) {
        // 마지막 글자일경우
        trie[nodi].fin = true;
        return;
    }
    
    // 현재 노드에서의 글자
    int cur = s[idx] -'0';
    
    // 이미 접두사가 있을경우
    if(trie[nodi].fin == true) sw = 1;
    // 내가 접두사가 될경우, 문자열의 마지막 글자인 동시에 trie에는 다음 글자가 있을때
    if(idx == s.size()-1 && trie[nodi].child[cur] != -1) sw = 1;
    
    // 문자열의 다음 글자가 없을경우 노드 추가
    if(trie[nodi].child[cur] == -1) {
        trie[nodi].child[cur] = trie.size();
        trie.push_back(node());
    }
    
    // 다음 글자를 TRIE에 삽입
    insert(s,idx+1,trie[nodi].child[cur]);
}
 
int main() {
    int t; cin >> t;
    while(t--) {
        sw =false;
        trie.clear();
        
        // TRIE 배열에 처음 시작하는 빈 노드를 넣어줘야함
        trie.push_back(node());
        int N; cin >> N;
        while(N--) {
            string s; cin >> s;
            // 각 문자열을 trie에 삽입
            insert(s,0,0);
        }
        
        if(sw) cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}
 
cs

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07
[알고리즘] Topological Sort, 위상정렬  (0) 2021.02.07

문제 정의

  • 일부 노드들의 순서가 주어졌을때, 전체 순서를 정하는 문제

문제 접근

  • 노드 순서를 인접 리스트(adj)로 저장
    • 인접 리스트로 저장하면서, 노드에 들어오는 간선의 개수(indeg)를 기록
    • 큐를 하나 생성해서, indeg가 0인 것들을 추가
      • indeg가 0이란 의미 : 들어오는 간선이 없으므로, 출발노드
    • 각 큐에 들어있는 노드에 대해서 다음을 반복
      • 결과 리스트에 추가
      • 각 노드에 인접한 노드들에 대해, indeg를 감소
      • 이떄, indeg가 0인 노드는 큐에 새로 추가
    • 결과 리스트 출력

시간복잡도

  • 모든 노드 : V
    • 모든 노드에 인접한 노드의 indeg 감소 : E
    • O(V + E)

인트 계산

  • 모든 입력 >> 10억 이하의정음수 >> INT 가능
  • dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용

대표예제 : 백준 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
45
46
47
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
// 각 노드의 인접 리스트
vector<int> adj[32010];
// 각 노드에 들어오는 간선 개수
int indeg[32010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        // 인접한 간선 추가
        adj[a].push_back(b);
        // 들어오는 간선의 개수 증가
        indeg[b]++;
        
    }
    
    queue<int> q;
    for(int i=1; i<=N; i++) {
        if(indeg[i]==0) q.push(i);
    }
    
    vector<int> rs;
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        rs.push_back(eq);
        
        for(int x : adj[eq]) {
            // 들어오는 간선의 개수 감소
            indeg[x]--;
            // 만약 들어오는 간선의 개수가 0일때 큐에 추가
            if(indeg[x] == 0) q.push(x);
        }
    }
    
    for(int ers : rs) cout << ers << ' ';
    
    return 0;
}
 
cs

비슷한 유형

  • 몇번째 순서인지 구하는 문제
    • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
      • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
      • 즉, 순서가 뒤틀리거나 틀리지만 않으면 됨
    • 내가 정확히 몇번째 순서를 구하는 문제는 플로이드를 통해서 확인 가능
    • https://www.acmicpc.net/problem/2458
    • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘  (0) 2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘  (0) 2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리  (0) 2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp  (0) 2021.02.07
[알고리즘] 문자열 TRIE  (0) 2021.02.07

+ Recent posts

티스토리툴바