반응형 이분탐색3 [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 다음 728x90
