/* 백준 1931번. 그리디 알고리즘 이용. 그리디 알고리즘 문제이기 때문에, 어떻게 하면 최대한 많이 우겨넣을 수 있을 지 생각 해봄. 반례가 없어야함. 공책에 예를 들어서 써보기로 함. 회의가 일찍 시작하는 순으로 정렬해도 늦게 끝나는 회의 때문에 안됨. 회의가 짧은 순으로 정렬하더라도 겹치는 경우엔 해당시키지 못함. 일찍 끝나는 순으로 정렬하면 될 것 같아서 해봄. 시간복잡도가 O(n^2)이므로 일반적으로 반복문을 돌리게 되면 시간 초과가 나올 수 있음. */ /* 한개의 회의실에서 이를 사용하고자 하는 N개의 회의에 대하여 사용표를 만들고자 함. 각 회의 I에 대해 시작시간과 종료시간이 주어져 있고, 각 회의가 겹치지 않으면서 회의실을 이용할 수 있는 최대 개수를 찾는 것. 회의가 끝나는 동시에..

/* 백준 1948번. 위상정렬이용. 모든임계경로를 다 구해야 하므로 역추적을 수행해야함. */ /* 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다. 모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다. */ #incl..

/* 백준 1516번. 위상정렬이용. 모든 정점이 수행될 수 있는 최소 시간을 출력하는것이므로, 단순히 임계경로를 각각 출력하면 됨. 간선이 연결되는 순간을 기준으로 현재보다 더 시간이 오래걸리는 경우가 발생한다면 계속해서 갱신하는 방식으로 답을 구할 수 있음. */ /* 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부터 N까지로 하고, 각 줄은 -1로 끝난다고 하자. 각 건물을 짓는데 걸리는 시간은 100,000보다 작거나 같은 자연수이다. */ #include #include #include #define MAX 501 using namespac..

/* 백준 2252번. 위상정렬을 이용한 가장 기본적인 문제. */ /* 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. */ #include #include #include #define MAX 32001 using namespace std; int n, inDegree[MAX], result[MAX]; //노드갯수, 진입차수갯수, 결과값갯수 vector a[MAX]; //정점마다 자신과 연결되어있는 간선 void topologySort() { queue q; //진입 차수..

/* 백준 1671번. 이분 매칭 이용. 단순히 2번씩 매칭을 수행하면 됨. 상어들의 능력에 따라 매칭을 시키는 것이므로 능력 수치 비교부분을 수정. 상어가 상어를 잡아먹으므로 상어가 상어에게 매칭이 되는것이라 생각. */ /* 첫째 줄에 상어의 마리 수 N이 주어진다. 이 값은 50보다 작거나 같은 자연수이다. 둘째 줄부터 각 상어의 크기, 속도, 지능의 정보가 주어진다. 이 값은 2,000,000,000보다 작거나 같은 자연수이다. */ #include #include #define MAX 1001 using namespace std; vector a[MAX]; int state[MAX][3]; int d[MAX]; int c[MAX]; int n; bool dfs(int x) { for (int i..

/* 백준 11377번. 이분 매칭 이용. 특정한 직원에 한해서만 2번씩 일을 할 수 있도록 매칭. 모든직원에 대해 1번씩 매칭해준 후, 특정한 직원의 숫자 만큼만 추가적으로 한번더 매칭을 수행. */ /* 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. */ #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m, k, s; bool dfs(int x) { for (..