Byeo

설명은 나중에...  #include #include #include #include #define CORE_NODE 2500#define SOURCE_NODE (CORE_NODE + 1)#define SINK_NODE (SOURCE_NODE + 1)#define MAX_NODE (SINK_NODE + 1)#define INF 999999using namespace std;vector graph[MAX_NODE];int flow[MAX_NODE][MAX_NODE];int n, m;int arr[50][50];int bfs(int src, int dst){ int parent[MAX_NODE], cur; queue q; memset(parent, -1, sizeof(parent)); q.push(src);..

설명은 나중에... 굉장히 난이도가 높은 문제인 듯 싶다. 특히 dfs()를 최대한 잘 추려내지 않으면 대부분 timeout난다. #include #include #include #include using namespace std; #define MAX_FLOW 2147483646 #define NODE 500 #define SOURCE (NODE + 1) #define SINK (SOURCE + 1) #define MAX_NODE (SINK + 1) vector adj[MAX_NODE]; int flow[MAX_NODE][MAX_NODE]; int N; bool bfs(int start, int end, int* level_graph) { queue q; q.push(start); level_graph..

설명은 나중에... #include #include #include #include using namespace std; #define MAX_NODE (50 * 2 + 1) #define START (MAX_NODE + 1) #define END (START + 1) #define MAX_SIZE (END + 1) #define INFINITY_FLOW 99999 #define MIN(a, b) a < b? a: b int N; int SUM; vector adj[MAX_SIZE]; int flow[MAX_SIZE][MAX_SIZE]; int tmp_flow[MAX_SIZE][MAX_SIZE]; int max_val = 0; int bfs(int start, int end) { queue q; int ..

설명은 나중에... #include #include #include #include using namespace std; class Pos; int ccw(const Pos& a, const Pos& b, const Pos& c); bool straight_check(const Pos& a, const Pos& b, const Pos& c, const Pos& d); class Pos { public: int x, y; Pos(){}; Pos(int x_, int y_): x(x_), y(y_){}; bool operator

개요 2개의 DP가 엮여있는 문제입니다. 1. 부분 문자열 str[a:b]가 팰린드롬인지 판단하고 저장하는 배열을 생성하는 과정 2. 부분 문자열 str[0:c]의 팰린드롬 분할 최소 값을 파악하고 저장하는 배열을 생성하는 과정 예제 백준 예제를 예시로 들겠습니다. ABACABA 1. 부분 문자열 str[a:b]가 팰린드롬인지 판단하는 과정 해당 과정은 2차원 배열을 통해서 이뤄집니다. dp[i][j]가 갖는 값은 str[i:j]가 팰린드롬이라면 true를, 그렇지 않으면 false를 갖는 boolean 배열입니다. 1) 가장 먼저, dp[i][i]는 모두 true입니다. 1글자의 문자열은 모두 팰린드롬이라고 볼 수 있기 때문이죠. dp[0][0]의 값은 'A'가 팰린드롬인가? 를 의미하며 true입니다..

개요 이분매칭 문제가 아닌 것 같은데 이분매칭 알고리즘입니다. 사실 알고리즘 종류를 모르고 시작한다면 시간이 꽤나 소요될 것 같은 유형의 문제였습니다. 상어의 크기, 속도, 지능이 주어질 때 상어 A의 세 가지 값이 상어 B의 세 가지 값보다 모두 크거나 같다면 A는 B를 먹을 수 있습니다. 여기서 잡아먹는 상어를 $V_L$에 두고 잡아먹히는 상어를 $V_R$에 두면 됩니다. 한 가지 예외는 상어 A의 모든 값이 상어 B와 동일한 경우입니다. 이 때는 단순하게 index를 기준으로 누가 누구를 잡아먹을 수 있을지 마음대로 정하면 됩니다. 왜냐하면 우리는 누가 살아남는지 관심이 있는 것이 아니라 최소로 생존할 수 있는 상어의 수에 관심이 있기 때문이죠. 마찬가지로 이런 의문이 들 수도 합니다. "상어 A ..

개요 Vertex Cover 문제입니다. 단, bipartite matching에서의 minimum vertex cover는 쾨닉의 정리에 의해서 maximum bipartite matching과 그 수가 같습니다. 결과적으로 이분매칭 알고리즘 응용입니다. 쾨닉의 정리는 다음 블로그 포스트를 참고하면서 공부했습니다. https://gazelle-and-cs.tistory.com/12 https://m.blog.naver.com/kks227/220967185015 그런데 이분매칭 알고리즘이라고 하더라도, 문제를 처음보면 이게 어떻게 이분매칭으로 변환될 수 있지? 라는 생각이 들긴 합니다. 시간을 약간 쓰면 퍼즐 풀 듯이 이분 매칭으로 치환하는 방법이 눈에 보였었습니다. 예제 백준 예제는 그대로 차용하기에 ..

개요 이분매칭 알고리즘의 응용버전입니다. 모든 수끼리 매칭을 시켰을 때, 모든 수의 쌍의 합이 소수가 될 수 있는 경우를 알아내는 문제죠. 핵심은 다음과 같이 3가지로 볼 수 있습니다. 1. 소수 판별 알고리즘은 에라토스테네스의 체로 구현한다. (설명은 위키로 대체: 위키 링크) 2. 모든 수가 매칭을 이뤄야 하므로 이분 매칭 알고리즘에서 매칭의 개수가 $n/2$ 인 케이스를 찾아내면 된다. 3. 2를 제외한 소수는 모두 홀수이다. 따라서 좌측 노드는 짝수, 우측 노드는 홀수로 나누어서 매칭을 실행하면 된다. (중복되는 수가 주어지지 않으므로 1 + 1 과 같은 케이스는 없다.) 예제 백준 예제 입력 1번을 살펴보겠습니다. 6 1 4 7 10 11 12 1. 소수 배열 만들기 가장 먼저 에라토스테네스의 ..

문과 감성 이분 매칭 알고리즘은 사랑과 전쟁 이다. - 관심 있는 이성이 솔로라면 바로 커플을 맺는다. - 하지만 관심 있는 이성이 이미 커플이라면, 그 커플을 깨부순 뒤에 원하던 사랑을 쟁취한다. 다만, 지금 당장 행복한 커플을 내가 강제로 헤어지게 할 수는 없으므로 그 커플 중에서 동성이 새로운 이성과 바람나게 해야 한다. 내가 남자라면, 관심가는 여자를 쟁탈하기 위하여 그녀의 남자친구에게 새로운 여자를 소개시켜주는 것과 같다. 이분 그래프 (Bipartite Graph) 이분 그래프: 어느 그래프 $G$에 속해있는 모든 vertex를 두 그룹 $V_L$과 $V_R$으로 나누었을 때, 그래프 내의 모든 edge $e$의 양 끝이 $v_l \in V_L$ 과 $v_r \in V_R$ 인 그래프를 의미한..

이전에 풀었던 이분 매칭 - 열혈강호의 다음 응용 문제입니다. 해당 문제는 한 사람 당 일을 두 개까지 할 수 있다는 추가 조건이 존재합니다. 이는 좌측의 회사 사람 노드를 두 배로 늘려주면 됩니다. 예시 백준 11376에서 주어진 예제를 사용해보겠습니다. 5 5 2 1 2 2 1 2 2 1 2 2 4 5 0 위 입력을 단순하게 그래프를 그려보면 다음과 같습니다. 하지만 이 그래프는 노드 사람 1명마다 최대 1개의 일을 할 수 밖에 없습니다. 4번 사람을 예로 들어보죠. 사람 $v_{l4}$이 일 $v_{r4}$과 매칭시키면, 최대 일을 2개 할 수 있는 $v_{l4}$가 더이상 매칭을 만들 수 없게 되죠. $v_{r5}$의 일을 처리할 수 있는데도 불구하고 말이죠. 변형 그래서 그래프에 약간의 변형을 ..