문제 정의

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

문제 접근

  • 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

문제링크 : https://www.acmicpc.net/problem/1786


문제 접근

시간복잡도 계산

  • KMP, Rabin-Karp : O(M+N)
    • M : 첫번째 문자열 길이
    • N : 두번쨰 문자열 길이

인트 계산

  • 최대 숫자 : 최대 문자열 길이 : 1e6

코드(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

문제유형

  • KMP
  • Rabin Karp

'알고리즘 > 백준' 카테고리의 다른 글

백준 11780 플로이드2 풀이(C++/CPP)  (0) 2021.02.08
백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)  (0) 2021.02.08
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP)  (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

+ Recent posts

티스토리툴바