정수형 배열 nums 와 정수 m 이 주어졌다. nums 에는 양의 정수 값들이 들어 있고, m 은 배열을 부분 배열로 분리할 수 있는 수이다. nums 배열을 m 개의 부분 배열로 분리할 때, 각 부분 배열의 합중 가장 큰 값이 최소가 되도록 분리했을 때의 합을 출력하세요. 입출력 예시 nums: 7, 2, 5, 10, 8 m: 2 출력: 18 nums: 1, 2, 3, 4, 5 m: 2 출력: 9 public class Main { public static int solution(int[] nums, int m) { int left = 0; int right = 0; for (int n : nums) { left = Math.max(n, ..
코딩 테스트/이진 탐색 문제
정수형 배열 weights 와 정수 days 가 주어졌다. weights 에는 각 상품의 무게들의 정보가 들어있고, days 는 운송 납기일이다. 상품들은 weights 에 적혀있는 순서대로 실어서 운송해야 하는데, days 이내에 운송을 하기 위한 차량의 운송일 당 최대 적재량 중에서 최소가 되는 경우의 적재량을 계산하는 프로그램을 작성하세요. 입출력 예시 weights: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 days: 5 출력: 15 weights: 3, 2, 2, 4, 1, 4 days: 3 출력: 6 /** * 주어진 배열의 값 자체가 아닌, 문제가 요구하는 **도메인에 해당하는 값의 범위**로 이진탐색하는 문제 !! */public class Main { public sta..
2차원 행렬에서 이진 탐색으로 데이터 찾기row x col 행렬 데이터가 주어졌을 때, target 을 이진 탐색으로 찾는 프로그램을 작성하세요.각 행의 데이터는 오름차순으로 정렬 상태입출력 예시행렬: {{1, 3, 7, 8}, {10, 11, 15, 20}, {21, 30, 35, 60}}target: 3출력: truetarget: 13출력: false public class Main { public static boolean solution(int[][] matrix, int target) { int rows = matrix.length; int cols = matrix[0].length; int result = binarySearch(matrix, targ..
원형 정렬 상태 배열에서의 이진 탐색nums 배열에 원형 상태로 데이터가 정렬되어 있을 때, 이진 탐색으로 데이터를 찾는 프로그램을 작성하세요.O(log n) 유지배열을 재 정렬하지 않고 풀기입출력 예시arr: 4, 5, 6, 7, 8, 0, 1, 2target: 0출력: 5arr: 8, 0, 1, 2, 4, 5, 6, 7,target: 3출력: -1public class Main { public static int solution(int[] arr, int target) { return binarySearch(arr, target, 0, arr.length - 1); } public static int binarySearch(int[] arr, int target, int..
target 값이 arr 내에 있으면 해당 인덱스 반환없으면 해당 값이 있을 경우의 위치에 -1을 곱하고 1을 뺀 값을 반환입출력 예시입력 arr: 1, 2, 5, 10, 20, 30, 40, 50, 60target: 30출력: 5target: 3출력: -3public class Practice { public static int binarySearch(int[] arr, int target, int left, int right) { if (left > right) { //항상 left가 대상인 이유 -> 재귀 끝나는 순간 -> right, left가 되고 사이에 값이 들어가야하므로 left자리가 대상값의 위치가 된다! return (left * ..
