이분탐색6 [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++] 백준 #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. [C/C++] 백준 #1981 배열에서 이동(이분탐색) 이번 문제는 보통의 그래프 문제와 다르게 경로상의 최저값과 최고값의 차이가 가장 적게 나오는 경로에서의 그 차이를 출력하는 문제입니다. 최저값과 최고값의 차이를 가지고 다루는 문제이기 때문에 다익스트라 알고리즘과 같은 탐욕 알고리즘 기반을 사용할 수가 없습니다. 제가 접근한 방법은 최고값과 최저값의 차이를 주어지고, 깊이우선 탐색(DFS)을 통해서, 시작점과 끝점까지 가는데, 그 차이를 가지는 경로가 있는지 확인하도록 했습니다. 최고값과 최저값의 차이는 이분탐색을 이용했습니다. 제일 먼저 모든 간선값들의 최저값과 최고값을 찾아서 그 차이값을 상한값으로 하였습니다. 이 값은 반드시 경로가 존재하게 되겠죠. 그리고 경로가 존재할 수 없는 값은 -1이 되겠죠. 모든 간선값이 같은 경우에는 0이 나와야 하니까요.. 2023. 1. 2. [C/C++] 백준 #1965 상자넣기(가장 긴 증가하는 부분수열) 이번 문제는 가장 긴 증가하는 부분수열을 찾는 문제입니다. 문제의 알고리즘 힌트에는 동적 프로그래밍을 이용하라고 되어 있지만, 동적 계획법을 이용하는 경우에는 \(O(N^2)\) 알고리즘으로 풀어야 합니다. 그에 비해 약간의 정책을 이용해서 풀면 \(O(N \log N)\) 알고리즘으로 풀 수 있습니다. 가장 긴 증가하는 부분수열이라는 것은, 부분수열중에 단순 증가하는 수열을 찾는 것입니다. 예를 들어서, 1 6 2 5 7 3 5 6 이란 수열이 있습니다. 부분수열은 순서를 지키면서, 이 수열에서 몇개의 수를 뽑아내는 것을 말합니다. 예를 들어서 1 6 2 5 도 이 수열의 부분수열이고, 1 2 7 6도 이 수열의 부분수열이 됩니다. 그런데, 증가하는 부분수열은 앞의 숫자보다 뒤의 숫자가 큰 경우를 의미.. 2022. 12. 10. 이전 1 다음
