Byeo

설명은 나중에... 굉장히 난이도가 높은 문제인 듯 싶다. 특히 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. 소수 배열 만들기 가장 먼저 에라토스테네스의 ..

이전에 풀었던 이분 매칭 - 열혈강호의 다음 응용 문제입니다. 해당 문제는 한 사람 당 일을 두 개까지 할 수 있다는 추가 조건이 존재합니다. 이는 좌측의 회사 사람 노드를 두 배로 늘려주면 됩니다. 예시 백준 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}$의 일을 처리할 수 있는데도 불구하고 말이죠. 변형 그래서 그래프에 약간의 변형을 ..

설명은 나중에... RUST use std::io::{stdin, Read}; const DR: [i32; 6] = [-1, -1, 0, 1, 1, 0]; const DC: [i32; 6] = [-1, 1, 1, 1, -1, -1]; fn dfs(i: usize, graph: &Vec, visited: &mut Vec, parent: &mut Vec) -> usize{ for _r in graph[i].iter(){ if visited[*_r] == true{ continue; } visited[*_r] = true; if parent[*_r] == -1 || dfs(parent[*_r] as usize, graph, visited, parent) == 1{ parent[*_r] = i as i32; r..

개요 Boj 17435 - 합성함수와 쿼리는 중첩함수를 미리 계산해놓은 테이블을 갖고 얼마나 빨리 찾도록 구현할 수 있냐의 문제입니다. $f_n(x) = f(f(f(f(...f(x)...))))$ 를 구하는데 최적화하기 위해서 어떻게 사전에 계산해놓을 수 있을까요? 그 비결은 $f_{(a+b)}(x) = f_a(f_b(x))$ 에 있습니다. 그리고 몇몇 포인트들만 사전에 계산해두는 것이지요. 설명 $f_{(a+b)}(x)$ 는 풀어쓰면 $f$가 $a$번 중첩된 $f(f(....(f_b(x))))$로 풀어쓸 수 있습니다. 즉, $f_b(x)$의 값 $B$을 미리 계산해놓는다면 그 값에 단순히 $f_a(B)$를 구하면 최종 함수 값을 알 수 있지요. 이 문제는 그래서 $f_n(x)$에서 $n$의 2의 거듭제..