binary search5 [C/C++] 백준 #3079 입국심사(이분탐색) 백준 온라인 저지 #3079 문제인 “입국심사” 문제는 다음과 같습니다.문제 개요• N개의 입국심사대가 있으며, 각 심사대마다 사람을 심사하는 데 걸리는 시간이 다릅니다.• M명의 사람이 입국심사를 받으려고 기다리고 있습니다.• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 구하는 문제입니다.입력1. 첫째 줄에 N(심사대의 개수)와 M(심사를 받아야 할 사람 수)이 주어집니다.2. 둘째 줄부터 N개의 줄에 각 심사대에서 한 명을 심사하는 데 걸리는 시간이 주어집니다.출력• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 출력합니다.해결 방법• 이분 탐색을 활용하여 최소 시간을 구하는 것이 핵심입니다.• 특정 시간을 기준으로 모든 사람이 심사를 받을 수 있는지 판단하며, 조건을 만족하는 최소 .. 2024. 11. 12. [C/C++] 백준 #2805 나무 자르기(이분 탐색) 이분 탐색은 단순증가하는 형태의 함수에서 원하는 값을 빠르게 찾는데 사용을 합니다. 시간 복잡도는 \(O( \log N )\)이 됩니다. 하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다. 나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다. 문제의 링크는 다음과 같습니다.https://www.acmicpc.net/problem/2805 코드 설명1. `readint()` 함수int readint() { int s=0,c; for(;;){ c=getchar(); if(c'9') break; s=s*10+c-'0'; } return s;}- 이 함수는 표준 입력으로부터 정.. 2024. 8. 16. [C/C++] 백준 #2749 피보나치 수 3(분할정복) 피보나치 수에 대한 알고리즘은 점화식에서 출발해서 재귀함수(recursion)를 배울 때 자주 인용되는 것이죠. 재귀함수를 사용하는 방법이 매우 많은 중복이 발생한다는 문제를 거론하면서 동적계획법(Dynamic Programming)을 사용해야 하는 이유를 설명할 때에도 많이 쓰입니다. 재귀함수를 단순하게 이용하면, 시간 복잡도가 \(O(\phi^N)\)으로 기하급수로 늘어나지만, 이를 동적 계획법 또는 포워드 프로그래밍(Forward Programming)을 사용하면, 시간 복잡도가 \(O(N)\)으로 급격하게 줄어들 수 있습니다. 하지만 이번 문제는 N 자체가 \(O(N)\) 알고리즘으로 해결하기 어려운 문제입니다. 그래서 분할 정복을 사용해야 하고, 이를 이용하면 시간 복잡도를 \(O(\log.. 2024. 8. 12. [C/C++] 백준 #2512 예산(이분 탐색) 이번 문제는 예산이 요청되었을 때, 정해진 예산에 맞추어 최대 허용 예산값을 구하는 문제입니다. https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이 문제는 최대 허용 예산값에 대해서 전체 예산 요청들을 만족하는지 아닌지를 판단할 수 있습니다. 최대 허용 예산값이 커질 수록 당연히 예산 초과가 될 수 있고, 최대 허용 예산값이 작아질수록 예산이 만족하기 때문에 어떤 값 이하에서는 항상 조건을 만족하고 그것을 초과하는 경우에는 항상 조건을 만.. 2023. 6. 12. [C/C++] 백준 #2110 공유기 설치(이분 탐색) N개의 집에 C개의 공유기를 적절하게 설치해서 두 공유기 사이의 거리를 최대한으로 하고자 할 때, 가장 인접한 두 공유기의 거리를 구하는 문제입니다. 이 문제는 이분 탐색을 이용해서 풀 수 있습니다. https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분탐색을 사용하기 위해서는 다음과 같은 조건을 만족해야 합니다. (또는 그 반대이거나) 1. \(n\)에서 조건을 만족했다면, \(k \le n\.. 2023. 3. 31. 이전 1 다음
