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

문제 접근

시간복잡도 계산

  • 최소스패닝트리 Kruscal : O(ElgE)

코드

  • 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

문제유형

  • 최소 스패닝 트리

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

백준 11779 최소비용 구하기 2 쉬운 풀이(C++/CPP)  (0) 2021.02.14
백준 11780 플로이드2 풀이(C++/CPP)  (0) 2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP)  (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

문제링크 : 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

프로토타입

  • 객체의 부모역할을 하는 객체
  • 자식 객체에게 프로퍼티와 메서드를 상속

프로토타입 사용이유

  • 생성자 함수로 인스턴스 생성할 때, 중복 프로퍼티, 메서드 생성해서 자원이 낭비됨
  • 만약 10개의 인스턴스 생성하면 동일한 메서드가 10개 생성되는 셈
  • 프로토타입을 활용해 상속하여 불필요한 중복 제거 가능
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
// 생성자 함수로 사용한 경우 >> 메서드 중복되어 자원낭비
function Circler(radius) {
    this.area = radius;
    this.getArea = function() {
        return Math.PI * this.radius ** 2;
    }
}
 
// 인스턴스 2개 생성
const circle1 = new Circle(1);
const circle2 = new Circle(2);
 
// 동일한 역할을 하는 메소드지만, 각각 인스턴스가 소유해서 자원이 낭비
console.log(circle1.getArea === circle2.getArea); // false
 
 
// prototype 사용할 경우 >> 상속통해 중복제거 가능
function Circle(radius) {
    this.area = radius;
}
Circle.prototype.getArea = function() {
    return Math.PI * this.radius ** 2;
}
 
// 인스턴스 2개 생성
const circle1 = new Circle(1);
const circle2 = new Circle(2);
 
// 하나의 메서드를 공유
console.log(circle1.getArea === circle2.getArea); // true
cs

프로토타입 체인

  • 프로토타입이 한 방향으로 연결되어있는 상속구조
  • 정확히 말하면 단방향 링크드 리스트
  • 객체의 프로퍼티, 메서드에 접근할때 없으면, 프로토타입 체인 따라서 부모 프로퍼티 확인
  • 프로토타입 체인의 최상위 객체 : Object.prototype
  • 모든 객체는 Object.prototype의 프로퍼티와 메서드 사용 가능

프로토타입, 생성자 함수 관계

  • 프로토타입
    • 객체의 __proto__로 접근 가능
      • __proto__ : 프로토타입에 접근하는 내부 접근자, __proto__ 참조
    • constructor 메서드를 가짐 : 생성자 함수
    • __proto__ 프로퍼티 : Object.prototype
  • 생성자 함수
    • prototype 프로퍼티 : Prototype 객체
    • __proto__ 프로퍼티 : Function.prototype
    • 프로토타입 생성 시점 : 생성자 함수 생성될때 생성

오버라이딩, 프로퍼티 섀도잉

  • 오버라이딩 : 프로토타입에 정의된 프로퍼티, 메서드를 객체에서 새롭게 추가
    • 객체에 추가된 프로퍼티 호출됨
    • 프로토타입 프로퍼티를 덮어쓰는것이 아닌, 객체에 새로운 프로퍼티가 추가
  • 프로퍼티 섀도잉 : 객체에 새로운 프로퍼티, 메서드 추가할때, 프로토타입의 것이 가려지는 현상

출처

  • 모던 자바스크립트 Deep Dive, Ch 19

'자바스크립트' 카테고리의 다른 글

[자바스크립트] __proto__  (0) 2021.02.07
[자바스크립트] 직접상속 Object.create  (0) 2021.02.07
[자바스크립트] 정적 프로퍼티, 메서드  (0) 2021.02.07
[자바스크립트] 생성자 함수  (0) 2021.02.05
[자바스크립트] this  (0) 2021.02.05

__proto__ 란?

  • 객체에서 __proto__를 통해 프로토타입에 접근 가능
  • 프로토타입은 내부슬롯 [[Prototype]]으로 존재
  • __proto__ : 접근자 프로퍼티로 [[Prototype]]에 접근
    • 접근자 프로퍼티 : 다른 프로퍼티나 내부슬롯을 읽거나 저장할때 사용
  • 사용하는 이유
    • 서로 프로토타입을 참조해서 프로토타입 체인이 꼬여버리는 현상을 방지하기 위해
    • 프로토타입 검색할때 무한 루프에 빠져버리게됨
    • 접근자 프로퍼티 내에서 서로를 참조하는지 체크
  • 직접 사용하는 것은 권장되지 않음
    • Object.getPrototypeOf 사용 : 프로토타입 가져올때
    • Object.setPrototypeOf 사용 : 프로토타입 지정할때
    • 이유 : 모든 객체가 __proto__를 가지고 있지 않음
      • __proto__는 Object.prototype의 접근자 프로퍼티
      • Object.prototype을 상속받지 않을경우 사용 불가능
      • 예시 : null을 상속받아 생성한 객체는 사용 불가

출처

  • 모던 자바스크립트 Deep Dive, Ch 19

'자바스크립트' 카테고리의 다른 글

[자바스크립트] 프로토타입  (0) 2021.02.07
[자바스크립트] 직접상속 Object.create  (0) 2021.02.07
[자바스크립트] 정적 프로퍼티, 메서드  (0) 2021.02.07
[자바스크립트] 생성자 함수  (0) 2021.02.05
[자바스크립트] this  (0) 2021.02.05

직접상속

  • 프로토타입을 지정해서, 프로토타입을 상속한 객체를 생성
  • Object.create
    • 첫번째 매개변수 : 프로토타입
    • 두번째 매개변수 : 생성할 객체의 프로퍼티 키와 디스크립터 객체 전달
  • 프로퍼티 정의가 번거로움
  • 객체 내부에서 proto 설정
    • 프로퍼티 쉽게 설정 가능
1
2
3
4
5
6
7
8
9
10
11
12
// 직접상속 : Object.create
const obj = Object.create(Object.prototype, {
    x : {value:1, writable: true, enumerable : true, configurable: true}
})
 
// 직접상속 : 객체 내부 __proto__
const myProto = { x : 10 };
const obj = {
    y: 20,
    __proto__ : myProto
};
 
cs

출처

  • 모던 자바스크립트 Deep Dive, Ch 19

'자바스크립트' 카테고리의 다른 글

[자바스크립트] 프로토타입  (0) 2021.02.07
[자바스크립트] __proto__  (0) 2021.02.07
[자바스크립트] 정적 프로퍼티, 메서드  (0) 2021.02.07
[자바스크립트] 생성자 함수  (0) 2021.02.05
[자바스크립트] this  (0) 2021.02.05

정적 프로퍼티, 메서드

  • 정적은 static을 의미, 자바에서 클래스에서 static으로 정의할 경우 인스턴스 생성하지 않아도 사용 가능한 개념과 유사
  • 생성자 함수로 인스턴스 생성하지 않아도 사용할수 있는 프로퍼티, 메서드
  • 생성자 함수도 객체이므로, 프로퍼티, 메서드 소유 가능
  • 단, 생성자 함수로 생성한 인스턴스로는 사용 불가
  • 예시 : Object
    • Object.create : Object 생성자 함수의 정적 메서드
    • Object 상속받은 객체에서는 호출 불가능
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
예시
// 생성자 함수
function Person(name) {
    this.name = name;
}
 
// 정적 프로퍼티, 메서드 추가
Person.staticProp = ‘static prop’;
Person.staticMethod = function() {
    console.log(‘static method’);
}
 
Person.staticProp(); // static prop
Person.staticMethod(); // static method
 
// 인스턴스에서 호출
const me = new Person(‘Han’);
me.staticProp(); // Error
 
 
cs

출처

  • 모던 자바스크립트 Deep Dive, Ch 19

'자바스크립트' 카테고리의 다른 글

[자바스크립트] __proto__  (0) 2021.02.07
[자바스크립트] 직접상속 Object.create  (0) 2021.02.07
[자바스크립트] 생성자 함수  (0) 2021.02.05
[자바스크립트] this  (0) 2021.02.05
[자바스크립트] 내부 슬롯, 내부 메서드  (0) 2021.02.05

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

문제 접근

시간복잡도 계산

  • 모든 문자열에 대해 순회 N
    • 문자열에 대해 한글자 한글자 순회 : M
    • O(NM) : 50 * 1e4 : 5e5

코드

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

문제유형

  • TRIE

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

백준 1197 최소 스패닝 트리 쉬운 풀이(C++/CPP)  (0) 2021.02.08
백준 1786 찾기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 14226 이모티콘  (0) 2021.02.06

문제 정의

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

문제 접근

  • 각 문자열을 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

+ Recent posts

티스토리툴바