코딩뚠뚠

풀이일시 : 2020-08-23 ​ 문제 : 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다. 상어들은 김재홍의 말을 모두 듣는다. 능력치가 모두 같은 상어 A, B가 있다면 A가 B를, B가 A를 잡아먹을 수는 있지만 A, B가 서로 잡아먹을수는 없다. N마리 상어의 크기, 속도, 지능이 주어졌을 때, 살아남을 수 있는 상어 수의 최솟값을 구하시오. ​ 입력: 첫째 줄에 상어의 ..

풀이일시 : 2020-08-23 ​ 문제 : 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. ex) 5 5 2 1 2 2 1 2 2 1 2 2 4 5 ​ 출력: 첫째 줄에 ..

풀이일시 : 2020-08-23 ​ 문제 : 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. ex) 5 5 2 1 2 1 1 2 2 3 3 3 4 5 1 1 ​ 출력: 첫째 줄에..

풀이 일시 : 2020-08-21 ​ 이분매칭 : A집단이 B집단을 선택하는 방법에 대한 알고리즘 효과적으로 집단을 매칭해준다. (최대매칭) ​ 문제 : 연결될 수 있는 쌍을 나타내고 그 중 최대 매칭을 계산 후 매칭 된 것을 나타내자 ​ 풀이 : DFS로 풀이 가능 dbstndi6316.tistory.com/64?category=953968 [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 ​ DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http:// dbstndi6316.tistory.com #include #include #define MAX 101 ..