binary search5 [C/C++] 백준 #3079 입국심사(이분탐색) 백준 온라인 저지 #3079 문제인 “입국심사” 문제는 다음과 같습니다.문제 개요• N개의 입국심사대가 있으며, 각 심사대마다 사람을 심사하는 데 걸리는 시간이 다릅니다.• M명의 사람이 입국심사를 받으려고 기다리고 있습니다.• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 구하는 문제입니다.입력1. 첫째 줄에 N(심사대의 개수)와 M(심사를 받아야 할 사람 수)이 주어집니다.2. 둘째 줄부터 N개의 줄에 각 심사대에서 한 명을 심사하는 데 걸리는 시간이 주어집니다.출력• 모든 사람이 입국심사를 마치는 데 걸리는 최소 시간을 출력합니다.해결 방법• 이분 탐색을 활용하여 최소 시간을 구하는 것이 핵심입니다.• 특정 시간을 기준으로 모든 사람이 심사를 받을 수 있는지 판단하며, 조건을 만족하는 최소 .. 2024. 11. 12. [C/C++] 백준 #2805 나무 자르기(이분 탐색) 이분 탐색은 단순증가하는 형태의 함수에서 원하는 값을 빠르게 찾는데 사용을 합니다. 시간 복잡도는 O(logN)이 됩니다. 하지만, 어떤 지점을 기준으로 실패와 성공이 갈릴 때, 그 기준점을 찾을 때에도 유용합니다. 나무 자르기 문제 역시 이분 탐색을 이용하여 성공할 때 최적값을 찾을 수 있습니다. 문제의 링크는 다음과 같습니다.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(ϕ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 다음 728x90
