[Binary Search] 백준 - 2805
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 우선 해당 문제는 이분 탐색의 종류중에서, 약간 응용 버전인, Parameter Search이다. 어떤 배열의 값들은 알수없으나, 정렬이 되어있는 경우 사용할수 있고, 특정 조건들을 만족하는 답중에서, 최대 or 최소를 구할때 사용한다. 아래와 같은 구조로 해당 문제의 기준을 세웠다. 1. 정답 범위, int 자료형은 2억까지이므로, 20억의 연산과정값이 발..
[Binary Search] 개념 + 7795번
이분탐색 ? 정렬이 보장되어있는 배열에서, 이분을 하면서 탐색하는기법 이분탐색은 전형적인 변수 세팅을 사용한다. 왼쪽, 오른쪽의 포인터 두개를 가지고 시작한다. 항상 가운데의 인덱스를 보고, 해당 인덱스와 , 타겟을 비교하고, 해당 비교를 통해 포인터 L 혹은 R을 비교하면서 포인터를 이동시킨다. https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분탐색에 대한 예제이다. 쉽게말하면, 한 집합을..
