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