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


아이디어

  • 자료구조 map 사용
  • 각 나무를 맵에 넣은다음에 추가될때마다 카운트 증가
    • 나무의 키들을 뽑아 정렬
    • 전체 개수중에 각 나무의 카운트를 출력

시간복잡도 계산

  • 맵에 넣기 O(M)
  • 맵 키 정렬O(NlgN)
  • 각 나무의 카운트를 출력

인트 계산

  • 최대 나무개수 e6 가능

코드

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
#include <iostream>
#include <string>
#include <map>
#include <cmath>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    map<string, int> tree;
    int cnt=0;
    
    string s;
    while(getline(cin, s)) {
        cnt++;
        tree[s]++;
        
    }
    cout <<fixed;
    cout.precision(4);
    
    for(auto it = tree.begin(); it !=tree.end(); it++) {
        cout << it->first << ' ' << round(it->second/(double)cnt*1000000)/10000 << '\n';
    }
    return 0;
}
 
 
 
cs

문제유형

  • 자료구조 - map

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

백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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


문제 추상화

  • 기존의 순서가 주어지고
  • 바뀌어야할 순서 주어질떄
  • 새로운 순서 구하기

아이디어

  • topological sort 사용

  • 바뀐 순서 따라가면서 adj에 추가

  • 그럼 기존에 만들었던 adj는 어떻게하지?

    • 인접한건 뺼수 있는데
    • 인접하지 않은건?

  • adj추가할때 후순위를 모두 넣으면 가능?

    • 그럼 인접하지 않은것도 확인가능

  • 순위를 찾을수 없는 경우 : 큐에 한번에 두개 이상이 들어올떄

  • 데이터 일관성 없어서 순위 못정하는 경우 : 전체 사이즈가 N이 안될때


시간복잡도 계산

  • 테스트케이스 O(T)
  • 각 노드에서 adj, indeg 생성(O(N^2))
  • 바뀐쌍마다 adj수정 : O(M * N)
  • topo 수행 : O(V+E) : O(N^2)
  • 총합 : O(T * (N^2 + MN + N^2)) = O(T*MN) = 1e9 (약간 불안)

인트 계산

  • indeg밖에없는데, 최대 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
82
83
84
85
86
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool chk[510];
vector<int> adj[510];
int indeg[510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(chk, chk+510, 0);
        fill(indeg, indeg+510, 0);
        for(int i=0; i<510; i++) adj[i].clear();
        
        int N; cin >> N;
        for(int i=0; i<N; i++) {
            int e; cin >> e;
            chk[e]=1;
            for(int j=1; j<=N; j++) {
                if(chk[j] == false) {
                    adj[e].push_back(j);
                    indeg[j]++;
                }
            }
        }
        
        int M; cin >> M;
        for(int i=0; i<M; i++) {
            int a,b; cin >> a >> b;
            vector<int>::iterator it = find(adj[b].begin(), adj[b].end(), a);
            if(it != adj[b].end()) {
                adj[b].erase(it);
                indeg[a]--;
                adj[a].push_back(b);
                indeg[b]++;
            } else {
                it = find(adj[a].begin(), adj[a].end(), b);
                adj[a].erase(it);
                indeg[b]--;
                adj[b].push_back(a);
                indeg[a]++;
            }
        }
        
        vector<int> rs;
        queue<int> q;
        for(int i=1; i<=N; i++) {
            if(indeg[i] == 0) q.push(i);
        }
        
        // 확실한 순위를 찾을수 없을때가 언제지?
        // 서로 순서가 꼬이면
        // 예를들면 1,2,3 인데 1,3만 바뀌면 2,3 관계가 순서가 꼬임
        // 순서가 꼬이는경우 > 큐에 여러개 들어갈때
        bool sw = false;
        while(!q.empty()) {
            if(q.size() >1) {
                sw= true;
                break;
            }
            int eq = q.front(); q.pop();
            rs.push_back(eq);
            
            for(int x : adj[eq]) {
                indeg[x]--;
                if(indeg[x] == 0) q.push(x);
            }
            
        }
        if(sw == true) cout << '?' << '\n';
        else if(rs.size() != N) cout << "IMPOSSIBLE" << '\n';
        else {
            for(int x : rs) cout << x << ' ';
            cout << '\n';
        }
        
    }
    return 0;
}
 
cs

문제유형

  • 순위를 찾을 수 없는 경우
    • 큐에 한번에 여러개의 노드가 들어갈때
  • 일관성 없는 경우
    • 사이클이 발생한 것
    • 결과의 사이즈가 노드 개수랑 다를때

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


아이디어

  • 랜선의 길이를 정한다음, K개의 랜선에 각각 나눠보면서 N개 이상이 되는 최대의 개수를 구하면됨
    • 정답이 되는 랜선의 길이를 가지고 이진 탐색 수행
      • 구하려는 랜선길이 이분탐색
      • 이분탐색할때 K개에 대해서 나눠줌
      • N개 이상이 되는 최대 길이를 구함 > upper bound

시간복잡도 계산

  • 구하려는 랜선길이 이분탐색 : lg(2^31)
    • 이분탐색할때 K개에 대해서 나눠줌 : O(K)
    • O(lg(2^31) * K) = 31 * 1e4 = 3e5

인트 계산

  • 이미 가지고 있는 랜선길이 : 1~2^31 = int 가능
  • 자를수 있는 갯수 계산할때 :
    • 제일 작은 1로 자른다고 쳤을때
    • 최대값 : 2^31 * K >> long long 사용

코드

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 <algorithm>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int K,N;
int nums[10010];
 
//
ll cal(int mid) {
    ll rs=0;
    for(int i=0; i<K; i++) rs+=nums[i]/mid;
    
    return rs;
}
int binsearch(ll st, int en, int tar) {
    if(st==en) {
        return st;
    }
    
    int mid = (st+en+1)/2;
    if(cal(mid) >= tar) {
        return binsearch(mid, en, tar);
    }
    else return binsearch(st, mid-1, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> K >> N;
    for(int i=0; i<K; i++) cin >> nums[i];
    
    cout << binsearch(1,pow(2,31)-1, N) << '\n';
}
 
cs

문제유형

  • 이분탐새 - 케이스를 이분탐색

비슷한 문제

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

백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21

+ Recent posts

티스토리툴바