Doby's Lab

https://www.acmicpc.net/problem/11407 11407번: 책 구매하기 3 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net Solved By: MCMF 바로 직전의 포스팅이었던 BOJ 11405번 문제보다 이 문제가 MCMF의 근본(?)같이 느껴졌습니다. 11405번을 풀었다면 쉽게 풀 수 있는 문제였습니다. #include #include #include #include #define MAX 203 #define SOURCE 1 #define SINK 2 #define INF 1e9 usi..

https://www.acmicpc.net/problem/11405 11405번: 책 구매하기 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net Solved By: MCMF 처음으로 Min Cost Max Flow알고리즘을 사용해본 문제였습니다. MCMF를 이해하고 나니 확실 유량 관련 문제는 네트워크 모델링이 차지하는 지분이 많은 것을 깨닫게 됩니다. #include #include #include #include #include #define MAX 203 // 100 + 100 + 1 + 1 + 1(idx ==..

오랜만에 회고록입니다. 제일 최근에 쓴 회고록이 언제인지 모르겠네요. 4월 11일에 격리가 끝나고 복귀를 해서 일과를 받기 시작하니 늘 바쁘고 피로가 쌓여있었습니다. 오랜만에 여유로운 주말이라 잘 보내고 있습니다. 최근에는 Convex Hull, SCC 등을 공부했었습니다. 두 알고리즘 중에 Monotone Chain 기법이나 Tarjan Algorithm 같은 주관적으로 느끼기에 어려웠던 테크닉들은 연구일지를 작성하며 공부를 했었습니다. 오랜만에 알아가는 재미를 느꼈습니다. 그리고, 계속 PS를 하다 보니 티어가 올라가고 있다거나 순위가 많이 변동된 것에 성취감을 느끼지만 예전만큼은 아닌 것 같습니다. 좋은 현상인 것 같습니다. 반년 전에 한창 PS를 시작할 때쯤 (9월), 2-SAT이라는 알고리즘의 ..

https://www.acmicpc.net/problem/2244 2244번: 민코프스키 합 첫째 줄에 두 다각형 A와 B의 꼭짓점 개수 N과 M이 주어진다. (3 ≤ N, M ≤ 1,000) 다음 N개의 줄에는 다각형 A를 이루는 꼭짓점의 좌표가, 그 다음 M개의 줄에는 다각형 B를 이루는 꼭짓점의 좌표가 주 www.acmicpc.net Solved By: Convex Hull(Graham Scan) A와 B의 점들을 {A.x + B.x, A.y + B.y}의 형태로 민코프스키 합을 구해주고, convex hull을 사용하여 만들어진 다각형의 좌표를 반시계 방향으로 출력합니다. 문제의 우선순위 조건에서 '2. 면적이 가장 작은 것'의 의미는 문제를 풀어도 이해하지 못했습니다. #include #incl..

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net Solved By: SCC(Tarjan Algorithm) 무너뜨릴 도미노의 최소 개수를 구하는 문제입니다. 도미노들끼리 사이클을 이루고 있을 수도 있습니다. 그러므로 SCC로 묶어서 indegree가 0인 도미노 SCC 그룹들을 개수를 파악하면 풀리는 문제입니다. +SCC관련 문제라는 것을 몰랐다면 꽤 오래 걸렸을 문제입니다. ++DFS를 시키는 범위를 항상 꼭 체크하기. #include #include #in..

SCC 알고리즘에는 Kosaraju Algorithm, Tarjan Algorithm이 있습니다. Kosaraju 알고리즘이 구현에는 편하지만 타잔 알고리즘이 SCC 노드끼리의 위상 정렬을 알 수 있기 때문에 공부하였습니다. 제일 최신화된 연구일지는 22.04.23 연구일지입니다. 이를 참고하여 읽어주시길 바랍니다. 22.04.22 연구일지 Time Complexity >> O(|V| + |E|) 동작 원리 +DFS와 Stack에 대한 사전 지식이 있어야 합니다. 1. 인접 배열을 이용한 DFS를 돌립니다. 2. DFS를 돌리면서 스택에 해당 노드를 담습니다. 2.1 next 노드의 sccOrder가 정해져 있지 않다면 next 노드를 가지고서 DFS를 돌리고, 제일 작은 minOrder 갱신합니다. 2..

https://www.acmicpc.net/problem/17403 17403번: 가장 높고 넓은 성 첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다. www.acmicpc.net Solved By: Convex Hull (Monotone Chain) Convex Hull의 기법 문제인 줄 알았던 문제였습니다. 그 덕에 Monotone Chain기법을 공부할 수 있었습니다. 공부를 하고 나서 알았지만 이건 기법의 문제가 아니었습니다. (https://draw-code-boy.tistory.com/269) 조건만 잘 따져주면 풀리는 문제였습니다. 그리고 index까지 신경 써줘야 하다 ..

말 그대로 사이즈를 다시 선언하는 메서드입니다. 간단한 메서드이지만 이런 경우에는 어떻게 되는지 궁금하여 글을 적게 되었습니다. size가 10인 배열에 1~10까지 담겨있다고 할 때, resize를 이용하여 크기를 5로 지정하면 배열에는 어떤 값들이 담겨있는지 궁금해졌습니다. #include #include using namespace std; int main(){ vector v(10); for(int i = 0; i < 10; i++) v[i] = i + 1; for(int i = 0; i < v.size(); i++){ cout