public class Practice3 {
public static boolean solution(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0){
return false;
}
int left = 0;
int rows = matrix.length;
int cols = matrix[0].length; // 1차원 배열과는 다르게 col, row 초기값 설정 필요
int right = rows * cols -1; // right를 행렬 개념이용하여 설정(가장 끝)
while (left <= right){ // 반복문을 통한 Binary Search 구현
int mid = (left + right) / 2;
if (matrix[mid /cols][mid % cols] == target){ // [몫][나머지](인덱스는 0부터 시작이기에 딱 맞음)
return true;
} else if (matrix[mid / cols][mid % cols] < target){
left = mid +1;
} else{
right = mid -1;
}
}
return false;연습문제1. 기본적인 이진 탐색 코드 구현 + 데이터가 존재하지 않을 경우에는 음의 부호와 함께 반환
(자바에서 기본적으로 내재되어있는 BinarySearch의 패키지 구현)
public class Practice1 {
public static int solution(int[] arr, int target) {
if (arr == null || arr.length == 0){
return -1;
}
int left = 0;
int right = arr.length -1;
while (left < right){ // 여기는 기본적인 Binary Search code
int mid = left + (right + left) / 2;
if (target == arr[mid]){
return mid;
} else if (target <arr[mid]){
right = mid -1;
} else {
left = mid + 1;
}
}
return -left - 1; // 삽입했을 경우에 넣는 것(데이터가 존재하지 않을 때에는 new 최솟값에서 음의 부호로 변환)
}
cf. arr의 길이가 너무 길고 찾으려는 target도 right에 가까워있을 때 overflow가 발생할 수 있음
overflow를 대비하기 위한 코드
// overflow를 방지하기 위한 mid
// int mid = left + (right - left) /2;
//
// int a = Integer.MAX_VALUE;
// int b = Integer.MIN_VALUE -10;
//
// int midAB = (a + b)/2;
// int midAB2 = a + (b - a) / 2;
연습문제2. 원형 정렬 배열에서의 이진탐색
문제 설명
배열에서의 Binary Search 접근 방식과 다르지 않으나, 원형 정렬 상태임을 숙지하고 new 최댓값과 new 최솟값에 대한 설정에 대하여 다르게 접근하기
public class Practice2 {
public static int solution(int[] arr, int target) {
if (arr == null || arr.length == 0) { // 예외처리 코드
return -1;
}
// 반복문을 통한 기본적인 Binary Search 코드
// 기본 배열과의 차이점 : 케이스만 나누면 됨
int left = 0;
int right = arr.length -1;
while (left <= right){
int mid = (left + right) / 2;
if (target == arr[mid]) {
return mid;
}
// 원형 정렬 배열 예시 (시작과 끝의 개념이 모호)
if (arr[left] <= arr[mid]) { // 원형 정렬 같은 경우에는 시작과 끝이 애매하므로 케이스를 분리
// 4, 5, 6, 7, 8, 1, 2
if (target >= arr[left] && target < arr[mid]){
right = mid -1; // 새로운 최댓값
} else {
left = mid + 1; // 새로운 최솟값
}
} else { // 원형 배열 같은 경우에는 정렬이어도 다음과 같은 케이스가 존재
// 11, 5, 6, 7, 8, 9, 10
if (target > arr[mid] && target <= arr[right]) {
left = mid +1;
} else {
right = mid -1;
}
}
}
return -1;
}
연습문제3. 이진 탐색(Binary Search) in 행렬
문제 설명
row * col 의 구조에서 target 탐색하는 코드
public class Practice3 {
public static boolean solution(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0){
return false;
}
int left = 0;
int rows = matrix.length;
int cols = matrix[0].length; // 1차원 배열과는 다르게 col, row 초기값 설정 필요
int right = rows * cols -1; // right를 행렬 개념이용하여 설정(가장 끝)
while (left <= right){ // 반복문을 통한 Binary Search 구현
int mid = (left + right) / 2;
if (matrix[mid /cols][mid % cols] == target){ // [몫][나머지](인덱스는 0부터 시작이기에 딱 맞음)
return true;
} else if (matrix[mid / cols][mid % cols] < target){
left = mid +1;
} else{
right = mid -1;
}
}
return false;인덱스 접근 방법이 matrix 구조인 것이 차이점이지
접근하는 방법은 동일
연습문제4. 배열을 균형있게 분할
문제 설명
weigth : 각각의 무게들이 적힌 배열 ex. {3, 2, 2, 4, 1, 4} : 3kg, 2kg, 2kg, 4kg, 1kg, 4kg
days : 모든 무게들을 며칠에 걸쳐 운송할 것인지(파티션, 분할의 개념)
적재량 : 적정량으로 나눔
이진 탐색을 이용하여 최소한의 적재량을 구해야함
= 계속 누적합을 이용하여 누적합끼리를 비교해보면서 이진 탐색을 실시
public class Practice4 {
public static int solution(int[] weights, int days) {
int left = 0;
int right = 0;
for (int w : weights){
left = Math.max(left, w); // 일단 배열의 가장 최댓값을 left로 설정
right += w; // 누적합의 개념을 이용하기
}
while (left <= right) {
int mid = (left + right) /2; // 총합 중에서 중앙값
int cnt = 1;
int cur = 0; // current 초기화
for (int w: weights){
if (cur + w > mid){
cnt += 1;
cur = 0;
}
cur += w;
}
if (cnt > days){ // 여태까지의 cnt가 운송 납기일보다 클 때
left = mid + 1;
} else { // 여태까지의 cnt가 운송 납기일보다 작을 때
right = mid -1;
}
}
return left;
}
연습문제5. 배열을 분리하였을때 가장 큰 값이 최소가 되도록 분리했을 때의 합
문제설명
public class Practice5 {
public static int solution(int[] nums, int m) {
int left = 0;
int right = 0;
for (int num: nums){
left = Math.max(num, left);
right += num;
}
if (m == 1){
return right;
}
while (left <= right){
int mid = (left + right)/2;
int cnt =1;
int total = 0;
for (int num : nums){
total += num;
if (total > mid){
total = num;
cnt++;
}
}
if (cnt <= m){
right = mid -1;
} else{
left = mid +1;
}
}
return left;
}