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


문제 접근


시간복잡도 계산

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

인트 계산

  • 숫자범위 생각할 숫자 없음

코드

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

비슷한 문제

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

백준 1786 찾기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 14226 이모티콘  (0) 2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP)  (0) 2021.02.06

문제 정의

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

문제 접근

  • 노드 순서를 인접 리스트(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

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


문제 접근

  • 모든 높이를 기준으로, 전체 나무 순회 >> O(M*N) >> 2e9 * 1e6 >> 시간초과
  • 자르려는 높이 증가할수록 얻을수 있는 나무의 길이가 감소 >> 선형적이므로 이진탐색 사용 가능
    • 자르려는 높이를 이진탐색 O(lgM)
    • 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
    • O(N*lgM)
  • Lower vs Upper
    • 이진 탐색 하는것을 그래프로 그려봤을때
    • X축 : 자르려는 높이, Y축 : 얻게되는 나무의 수
    • 같은값이 없을때 더 낮은 높이를 설정해야함 > UpperBound
    • 더 높은 높이를 설정할 경우, 얻게 되는 나무의 수가 부족한 현상 발생

시간복잡도 계산

  • 자르려는 높이를 이진탐색 O(lgM)
  • 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
  • O(N*lgM)

인트 계산

  • 이진탐색 시 필요한 나무길이 : 나무길이 최대 1e6 * 2e9 >> 2e15 >> 인트 사용 불가, long long
    • 나무 높이 : 1e9 이하 >> 인트 사용 가능

코드

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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
 
int N,M;
 
ll chk(int mid) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        rs += max(tree[i]-mid, 0);
    }
    return rs;
}
 
int binsearch(int M, int st, int en) {
    if(st==en) return st;
    
    int mid = (st+en+1)/2;
    if(chk(mid) >= M) return binsearch(M, mid, en);
    else return binsearch(M, st, mid-1);
}
 
int main() {
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(M,0,1e9) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 케이스
    • 이진 탐색 문제 중 정답이 되는 값을 이진탐색 하는 문제
    • 이와 반대 유형으로 '이진탐색 - 모든 케이스'
      • 모든 케이스에 대해서, 연산을 이진탐색 해주는 유형

비슷한 문제

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

백준 5052 전화번호 목록 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP)  (0) 2021.02.07
백준 14226 이모티콘  (0) 2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP)  (0) 2021.02.06
백준 1963 소수 경로  (0) 2021.02.06

+ Recent posts

티스토리툴바