본문 바로가기
반응형

이진탐색4

BOJ 10816 - 숫자 카드 2 / C++ 문제 링크 : https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 이전의 숫자 카드 문제는 아래와 같이 풀이하였다. https://appdevorsec.tistory.com/42 하지만, 숫자 카드 2는 시간 제한이 더 줄어들었으므로 이진 탐색을 통해 풀어야한다. lower_bound는 찾으려는 값보다 같거나 큰 값이 존재하는 인덱스, upper_bound는 찾으려는 값을 초과하는 첫 인덱스이다. 예를 들어,.. 2022. 4. 13.
BOJ 1654 - 랜선 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 이미 갖고 있는 랜선들 k개를 잘라 n개의 랜선을 만들 때, 랜선 하나의 최대 길이를 구하면 된다. 그러기 위해서는 랜선의 길이를 x라 했을 때, 원소들에 대해 (LANlines[i] / x)를 구하여 몇 개의 랜선을 만들 수 있는지 구한 뒤 모두 더해 n개 이상 만들 수 있다면 정답이 될 수 있다. 따라서 0부터 랜선의 최대 길이를 이분 탐색.. 2022. 3. 4.
BOJ 2805 - 나무 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 나무들의 높이가 주어지고 절단기의 길이가 x일 때 (trees[i] - x)만큼 집에 나무를 가져갈 수 있다. 적어도 m미터의 나무를 가져가기 위한 절단기의 최대 길이를 구하면 된다. 이를 구하기 위해 이분 탐색을 이용한다. 일반적인 이분 탐색은 원소 값들을 탐색하지만 해당 문제에서는 원소 값들을 탐색해서는 답을 찾을 수 없다. 따라.. 2022. 3. 4.
이진 탐색(Binary Search) 배열이 정렬되어 있을 때, 가운데 값과 비교하여 찾고자하는 값이 더 크면 오른쪽을 작다면 왼쪽을 탐색하는 방식 예시 [2, 5, 7, 9, 14, 19, 20, 24]가 있을 때 만약 2를 찾고 싶다면 가운데 값인 14와 비교를 하면 더 작기 때문에 다시 왼쪽 부분인 [2, 5, 7, 9]에서 같은 방식으로 반복한다. 최종적으로 2를 찾아 인덱스를 리턴하게 된다. 장점 시간복잡도가 log n으로 상당히 빠르다. 완전 탐색을 수행했을 때 시간 초과가 나는 여러 문제에서 활용될 수 있다. 구현 재귀로 구현 int recursive_binarySearch(vector arr, int start, int end, int target){ if(start > end) return -1; int mid = (star.. 2022. 3. 3.
반응형

티스토리툴바