Doby's Lab

https://www.acmicpc.net/problem/11280 11280번: 2-SAT - 3 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 www.acmicpc.net Solved By: 2-SAT, SCC 처음으로 풀어본 2-SAT 문제였습니다. 2-SAT에 대해서는 주말에 간단하게 정리할 예정이며 직전 포스팅에 공부했던 포스팅들의 링크를 걸어두었습니다. 변수와 NOT 변수에 대해서 {2 * i, 2 * i + 1}로 각각 모델링하여 SCC를 Tarjan Algorithm을 통해 만들었습니다. 각..

https://www.acmicpc.net/problem/20504 20504번: I번은 쉬운 문제 2030년, Farmer John은 선린 인터넷 컴퍼니에서 소프트웨어 개발자이자 검색 팀장으로 근무하고 있다. John의 강한 의지에 따라 검색 팀에서는 모든 소프트웨어의 개발을 테스트 주도 개발(test-driven www.acmicpc.net Solved By: Tarjan Algorithm, Topological Sort in SCC Tarjan Algorithm을 이용하여 SCC를 구성하고, 각 SCC마다 indegree를 확인하여 0이 아닌 경우에는 다른 함수에 의해 호출될 수 있다는 뜻이므로 방문 배열을 하나 만들어 해당 SCC는 true값을 줍니다. 그리고, 테스트 케이스들을 통해 호출되는 함..

https://www.acmicpc.net/problem/12813 12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net Solved By: Implementation, Bitwise Operation 비트 연산(Bitwise Operation)을 이해하기 위해 풀어본 문제였습니다. #include using namespace std; string a, b; int main(){ cin >> a >> b; // AND for(int i = 0; i < a.length(); i++){ if(a[i] == '1' && b[i] == '1'){ c..

https://www.acmicpc.net/problem/11378 11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 www.acmicpc.net Solved By: Bipartite Matching, Edmonds Karp(Max Flow) 이번 문제는 network modeling이 까다로웠던 문제였습니다. 제가 처음 한 실수는 SOURCE node와 people node사이에 TEMP_SOURCE node를 만들고, SOURCE와 TEMP_SOURCE 사이의 capacity를 n + k로 할당하였습..

https://www.acmicpc.net/problem/18133 18133번: 가톨릭대학교에 워터 슬라이드를?? 두 정수 N (2 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100,000)이 주어진다. N 은 건물의 개수를, M 은 터널의 개수를 나타낸다. 건물 옥상들의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정 www.acmicpc.net Solved By: Tarjan Algorithm, Topological Sort in SCC 진입 차수가 0인 건물 옥상을 구하여 그만큼 카운트해주었습니다. #include #include #include #include #include #define MAX 100001 using namespace std; int n, m; vecto..

https://www.acmicpc.net/problem/1258 1258번: 문제 할당 첫째 줄에는 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄부터 N개의 줄에 걸쳐 각 학생이 N개의 문제를 푸는 데 걸리는 시간을 나타내는 N개의 정수가 순서대로 주어진다. 주어지는 모든 정수는 1,000을 넘 www.acmicpc.net Solved By: MCMF, Bipartite Matching 학생이 하나씩 문제를 맡아야 한다는 점에서 Bipartite Matching을 떠올렸습니다. 그리고, 학생에서 문제를 향해 network가 modeling 되어있다고 생각하면 MCMF를 이용해 풀 수 있습니다. #include #include #include #define MAX 203 #define SOURCE 1 ..

https://www.acmicpc.net/problem/11409 11409번: 열혈강호 6 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 www.acmicpc.net Solved By: MCMF, Bipartite Matching 열혈강호 5 문제와 같은 문제입니다. 하지만, 이 문제에서는 주어야 하는 월급의 최솟값이 아닌 월급의 최댓값을 구합니다. 이 경우 최단 경로 알고리즘에서도 쓰이던 트릭 같은 테크닉을 이용합니다. 비용(가중치)를 음수 값으로 주어서 그대로 MCMF를 구한 것에서 mincost의 음수 값을 구하게 되면 최댓값을 구할 수 있습..

https://www.acmicpc.net/problem/11408 11408번: 열혈강호 5 강호네 회사에는 직원이 N명이 있고, 해야 할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net Solved By: MCMF, Bipartite Matching {SOURCE -> people -> works -> SINK} 순서로 네트워크 모델링을 해주고, people과 works 사이의 edge에 가중치를 월급으로 두고, 모든 edge에 capacity는 1로 주어 Biparitie Matching을 하게 한 다음에 MCMF를 돌리면 풀리는 문제입니다. #include #in..