BOJ111 [알고리즘 정리] 위상 정렬 위상 정렬 시간 복잡도 : O(|V|+|E|) indegree : 한 정점에 들어오는 간선 수ex ) a -> c, b -> c 라면 c의 indegree는 2, a,b의 indegree는 0이 된다. 기본 코드 // 해당 노드에 향하는 간선(indegree)이 0인경우 q에 추가한다. for (int i = 1; i 2018. 9. 30. 백준(BOJ) 11585 속타는 저녘 메뉴 ** # KMP kmp를 알고 있다면 크게 어렵지 않은 문제!..물론 kmp가 어렵지만 ㅎㅎ;; # 실수 했던 점 #include #include #include #include #include #include #include #include #include #define MAX 5005 #define INF 987654321 #define MOD 31991 #pragma warning(disable:4996) using namespace std; int n; char a[1000001], b[2000001]; int kmp[1000000]; int ans; void make_pi() { int j = 0; for (int i = 1; i 0 && a[i] != a[j.. 2018. 9. 30. 백준(BOJ) 1298 노트북 주인을 찾아서 ** # 이분매칭 # 네트워크 플로우 네트워크 플로우를 이용하여 풀수도 있지만,네트워크 플로우 보다는 이분매칭을 이용하면 보다 쉽게 풀 수 있다. #include #include #include #include #include #include #include #include #include #define MAX 5005 #define INF 987654321 #define MOD 31991 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; int n, m, bs[MAX]; bool visite[MAX]; vector node; bool dfs(int cur) { if (visite[cur]) retu.. 2018. 9. 30. [알고리즘 정리] 이분 매칭 이분 매칭 시간 복잡도 : O(E*sqrt(V)) visit : 방문 여부 확인bs : 현재 노드가 연결된 노드 ex) bs[a]=b; 라면, a와 b가 연결된 상태이다. 기본 코드 bool dfs(int cur) { if (visite[cur]) return 0; visite[cur] = 1; for (int i = 0; i < node[cur].size(); i++) { int next = node[cur][i]; if (!bs[next] || dfs(bs[next])) { bs[next] = cur; return 1; } } return 0; } int binary_match() { int ret = 0; for (int i = 1; i 2018. 9. 30. 이전 1 2 3 4 5 6 7 8 ··· 28 다음