/* 백준 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 (..

/* 백준 11376번. 이분 매칭 이용. 각각의 직원이 최대 두개의 일을 할 수 있다는 점에서 두번씩 DFS를 수행해주면 됨. 어떤 것을 먼저 매칭하던지 최종 매칭 숫자가 동일하므로 단순히 DFS를 두번만 수행하면 됨. */ /* 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. */ #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; int c[MAX]; int n, m; bool dfs(int x) { for (int i = 0; i < a[x].size(..

/* 백준 11375번. 이분 매칭 이용. 기초적인 이분 매칭 문제. 축사배정과 입력받는 방식만 다를 뿐 동일하게 DFS를 이용하여 해결. */ /* 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. */ #include #include #define MAX 1001 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; int n, m; //직원 ,해야할 일. bool dfs(int x) { for (int i = 0; i < a[x].size(); i++) { int t = a[x][i]; if (c..

/* 백준 2188번. 이분 매칭 이용. 가장 기초적인 형태의 이분 매칭 문제. DFS를 이용해서 계속 매칭이 가능한 경우를 재귀적으로 매칭시켜 문제 해결. */ /* 첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200) 둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다. */ #include #include #define MAX 201 using namespace std; vector a[MAX]; int d[MAX]; bool c[MAX]; //현재 확인한 노드인지 정..

/* 대표적인 문자열 매칭 알고리즘. 기본적으로 문자열 매칭 알고리즘이란 특정한 글이 있을 때, 그 안에서 하나의 문자열을 찾는 알고리즘. 단순 비교 문자열 매칭 알고리즘은 말그대로 하나하나 모두 확인하는 알고리즘으로 가장 간단한 형태의 알고리즘. 하지만 최악의 경우 시간이 많이 소요됨으로 비효율적. KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 반복되는 연산을 얼마나 줄일 수 있는지 판별하여 매칭할 문자열을 빠르게 점프하는 기법. 접두사와 접미사를 구하게 됐을 때, 접두사와 접미사가 일치하는 경우에 한해서는 점프하여 수행. */ #include #include using namespace std; vector makeTable(string pattern) //접두사와 접미사의 최대길이를 포함하는 ..