oVeron

문제의 형태는 기본적은 컨벡스 헐 트릭이다. 선분들을 입력받아 기울기 순으로 정렬하고, 컨벡스 헐 트릭을 사용해 필요없는 선분들을 걸러낸다. 그 후 y좌표들을 입력받아 이분 탐색을 통해 가장 왼쪽에 있는 선분의 번호를 출력하면 된다. 단, 구현에 주의해야 할 부분들이 몇 가지 있다.1. 부동 소수점 : 기울기, 입력받은 y좌표 등 실수로 표현되는 값들이 많다. 오차를 조정하지 않으면 틀리게 되므로, 본인은 오차 범위를 표현하는 상수 \(TOLE\)을 이용해 오차를 조정하였다. 부등호를 표현할 때 오차 범위를 보정하도록 하자. 이 문제의 정답률이 낮은 가장 큰 이유이다.2. 필요없는 선분을 걸러낼 때 컨벡스 헐 트릭에서는 현재 교점의 x좌표와 이전 교점의 x좌표의 대소를 비교했지만, 이 문제에서는 선분의 ..

알고리즘/baekjoon 2024. 7. 13. 10:37

열의 합을 그룹 \(A\)에 속하는 정점으로, 행의 합을 그룹 \(B\)에 속하는 정점으로 생각해 보자. \(N\)번째 열의 정점과 \(M\)번째 행을 잇는 간선의 가중치는 격자 \((N, M)\)에 들어갈 수 있는 값이 될 것이다.  이때 전체  격자에 들어갈 수 있는 값의 최댓값을 용량으로, 실제 격자에 들어갈 수 있는 값을 유량이라 생각하면, 간선의 용량을 1부터 10000까지 설정해 가면서 유량을 흘릴 수 있다. 최대 유량이 열의 합 또는 행의 합과 같으면 설정한 간선의 용량으로 숫자판을 만들 수 있다. 이때 우리는 간선의 용량의 최솟값을 구하고자 한다. 간선의 용량을 1부터 10000까지 차례대로 설정하면 시간이 오래 걸리므로, 이분 탐색을 통해 용량을 설정해 가면서 값을 구하면 된다. 숫자판에..

알고리즘/baekjoon 2024. 7. 4. 21:56

1.모든 점에 대해서 완전 탐색을 돌릴 수는 없으므로, 다른 방법을 생각해 보자. 우선 y좌표가 작은 순으로, y좌표가 같다면 x좌표가 큰 순으로 점들을 정렬한다.  ex) (5, 3), (5, 2), (3, 1), (3, 2), (1, 7), (1, 5) -> (1, 7), (1, 5), (3, 2), (3, 1), (5, 3), (5, 2) 여기서 문제 조건을 생각해 보자. 한 점에서 다른 점으로 북서풍을 타고 이동할 수 있으려면, 그 다른 점이 한 점보다 y좌표는 큰 대신 x좌표는 작아야 한다. 위의 예시에서 (5, 3)이 이동할 수 있는 점은 (1, 7), (1, 5) 둘 뿐이다. 그런데 현재 y좌표가 작은 순대로, y좌표가 같다면 x좌표가 큰 순으로 정렬되어 있으므로, 우리는 (3, 1)의 왼편..

알고리즘/baekjoon 2024. 6. 17. 12:08

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1654번 랜선 자르기와 동일한 문제. https://www.acmicpc.net/problem/1654 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tii; ll N, M; vector tree; int main() { ..

알고리즘/baekjoon 2023. 5. 26. 16:42

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 관찰 N = 3, M = 6이라 하고, 주어진 \(T_{k}\)를 (1, 2, 4)라 하자. 이때 시간에 따른 심사받은 인원을 나열하면 다음과 같다. 시간 1 2 3 4 5 6 ... 심사받은 수 1 3 4 7 8 10 ... 심사받은 수를 배열이라 생각하면, 이 배열 내에서 M = 6보다 크거나 같은 최소의 심사받은 수를 찾아 그 시간을 알아내면 된다. 따라서 답은 4이다. 알고리..

알고리즘/baekjoon 2023. 4. 30. 11:21

이분 탐색(Binary Search) : 정렬된 원소들에 특정 원소가 존재하는지를 O(log N) 시간에 확인하는 알고리즘 아래 코드는 배열 arr에서 찾고자 하는 값의 index를 확인하는 알고리즘이다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tiii; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int arr[10] = {1, 2, 4, 7, 10, 20, 20, 20, 99, 1010}; int x{99}; //찾고자 하는 값 int left{0}, right{10}; while (left ..

알고리즘/algorithm 2023. 4. 24. 14:43

https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 1. 식 도출 - 도형의 닮음을 이용해 식을 구한다. 2. 이분 탐색을 이용한 근삿값 도출 #define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; double x, y, c; double ans; int main() { ios::sync_wit..

알고리즘/baekjoon 2023. 3. 15. 13:28

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net lis[i] : 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막 값, 수열 A에서 이 값이 존재하는 index O(nlogn) LIS에서 부분 수열에 존재하는 원소를 알아내기 위해, 부분 수열에서 A[i]의 이전 값을 의미하는 befIdx로 부분 수열 원소의 역추적이 가능하도록 하였다. #include #include #include #i..

알고리즘/baekjoon 2023. 1. 24. 19:00