oVeron

1.쥐가 전부 구멍에 들어갈 수 있는지에 따라 답을 출력하는 문제이다. 일단  쥐를 최대한 많이 구멍에 들어가게 해야 하므로, 구멍에 들어가는 쥐의 수를 하나의 유량으로 생각하여 최대 유량 문제로 바꿔 풀어보자. 먼저 쥐들과 구멍들을 하나의 간선으로 연결한다. 간선의 용량은 당연히 \(1\)이 될 것이다.\(source\)와 쥐들을 간선으로 연결할 때도 간선의 용량은 당연히 \(1\)이 된다.구멍들과 \(sink\)를 간선으로 연결해 보자. 각 구멍에 들어갈 수 있는 쥐의 수는 \(k\)이므로, 간선의 용량은 \(k\)가 된다. 이 정보들을 종합해 그래프를 구현한 후, 최대 유량 알고리즘을 적용하면 문제를 풀 수 있다. 2.문제는 어떤 쥐들과 구멍들을 간선으로 연결할 지 정하는 것이다. 쥐와 구멍의 좌표..

알고리즘/baekjoon 2024. 6. 30. 10:17

해당 도서와 블로그의 내용을 공부해 정리한 것입니다. https://anz1217.tistory.com/105 CCW 세 점 \(A, B, C\)가 있습니다. 이 점들을 이용해 2개의 벡터 \(\overrightarrow{AB}, \overrightarrow{BC}\)를 만듭시다. 이 두 벡터의 외적값을 이용해 세 점에 대한 방향성을 알 수 있습니다. 1. \(\overrightarrow{AB} anz1217.tistory.com http://www.yes24.com/Product/Goods/8006522 알고리즘 문제 해결 전략 세트 - YES24 이 책은 프로그래밍 대회 문제를 풀면서 각종 알고리즘 설계 기법과 자료 구조에 대해 배우고, 나아가 문제 해결 능력까지 키울 수 있도록 구성되어 있다. 각 ..

알고리즘/algorithm 2023. 5. 12. 11:01

https://www.acmicpc.net/problem/3878 3878번: 점 분리평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹www.acmicpc.net 0. 특정 색깔의 점이 아무것도 없는지 확인한다.1. 검은색 점, 흰색 점, 모든 점에 대한 컨벡스 헐을 만든다.2. 선분 교차를 통해 검은색 점의 컨벡스 헐과 흰색 점의 컨벡스 헐이 교차하는지 확인한다. 교차한다면 점이 분리되지 않는다.3. 한 컨벡스 헐 내에 다른 컨벡스 헐이 포함되는지 확인한다.#define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS#include us..

알고리즘/baekjoon 2023. 3. 8. 18:54

https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net 컨벡스 헐을 만들기 전 ccw로 정렬된 점을 출력하면 되는데, 마지막 일직선에 대해서는 역순으로 좌표가 저장되어 있다. 이를 처리해주는 것이 까다로웠다. #define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS #define pi 3.14159265358979 #include using namespace std; typedef long lon..

알고리즘/baekjoon 2023. 3. 7. 23:47

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net 두 선분이 교차하는 지 알아낸 후 이를 유니온 파인드를 이용해 집합으로 표현하는 문제이다. #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; int N; int ..

알고리즘/baekjoon 2023. 1. 23. 22:34

https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; int main() { ios::sync_with_stdio(..

알고리즘/baekjoon 2023. 1. 23. 10:15