BinarySearch를 사용하면 검색 범위를 logN으로 엄청나게 단축시킬 수 있다.
만약 탐색할 범위가 너무 크다면 고려해봐야 한다.
특히 응용이라고 할 수 있는 최댓값, 최솟값을 찾아야 하는 이분 탐색을 이용하는
매개 변수 탐색 Parametric Search는 굉장히 유용하다.
주의할 점은 이분 탐색을 사용하기 이전에 탐색할 배열은 무조건 정렬되어있어야 한다.
이분 탐색은 기준 값과 가변 값을 통해 Start와 End를 결정한다.
package Search.BinarySearch;
public class BinarySearchTest {
static int[] arr;
public static void main(String[] args) {
arr = new int[]{1,3,5,7,9,11,13};
int idx = BinarySearchCode(9);
System.out.println(idx);
}
public static int BinarySearchCode(int findNumber){
int s = 0;
int e = arr.length - 1;
int mid;
int returnNumber = 0;
while(s <= e){
mid = (s+e) / 2;
if(findNumber == arr[mid]) {
returnNumber = mid;
break;
}
else if(findNumber > arr[mid])
s = mid + 1;
else if(findNumber < arr[mid])
e = mid - 1;
}
return returnNumber;
}
}
이분 탐색의 코드 자체는 간단하다.
left에서 시작하는 s, right에서 시작하는 e가 서로 교차하게 되면 종료한다.
(s+e)/2를 이용한 중간 값 mid를 계속 조건에 맞게 변화시키며 탐색범위를 이분한다.
찾지 못하였다면 그냥 종료될 것이고, 찾았다면 idx를 리턴한다.
이분 탐색에서 가장 중요하다고 생각하는 점은
변하는 가변 값과 변하지 않는 기준 값이다.
기준 값과 가변 값과의 비교를 통해 s, e 범위를 결정한다.
현재 코드에서는 찾을 숫자(기준 값)를 기준으로
mid를 이용해서 가변 값과의 비교를 통해 s, e를 결정하고 있지만
Prametric Search를 하게 되면 기준 값은 문제를 보고 결정을 해주어야 한다.
public static long binarySearch(int need){
long s = 0;
long e = 2_000_000_000;
long returnHeight = 0;
while(s <= e){
long mid = (s + e) / 2;
// 기준값 설정
// 자른 값들의 총합을 이용
long sum = 0;
for(int i = 0; i<arr.length; i++){
int ele = arr[i];
if(ele > mid)
sum += ele - mid;
}
if(sum >= need) { // 조건을 만족하므로 범위를 더 엄밀하게 줄임
s = mid + 1;
returnHeight = mid; // 조건을 충족한다면 일단 저장
}else if(sum < need)
e = mid - 1;
}
return returnHeight;
}
백준 2805 나무자르기 문제의 코드 일부다.
해당 문제에서 기준 값은 need 이다. (함수의 매개변수로 받고 있음)
가변 값은 mid를 이용해 구한 sum이다.
mid를 기준으로 자른 값들의 총합(sum)이 need 이상이면,
더 엄밀하게 자르기 위해 s를 더 올려서 mid를 높인다.
만족하지 않는다면 e를 낮춰서 mid를 낮춘다.
탐색 범위를 마지막에 만족하는 것까지 좁힐 수 있으므로 최대값을 구할 수 있다.
이분 탐색, 매개 변수 탐색을 구현할 땐 기준 값, 가변 값을 무엇으로 할 지 항상 생각하자.
Prametric Search 문제
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
'CS > 알고리즘' 카테고리의 다른 글
| 코딩테스트 자료구조, 알고리즘 정리 (0) | 2022.06.16 |
|---|---|
| [알고리즘] 다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm) (0) | 2022.04.20 |
| [알고리즘] 플로이드 워셜 알고리즘 (Floyd Warshall Algorithm) (0) | 2022.04.17 |
| [JAVA] 알고리즘 DFS[Depth-First Search] 깊이 우선 탐색 (0) | 2022.03.16 |
| [JAVA] 알고리즘 BFS[Breadth-First Search] 너비 우선 탐색 (1) | 2022.03.16 |
