binarysearch 4

백준(BOJ) 2512 : 예산 (실버2) / 자바(Java) 풀이

문제https://www.acmicpc.net/problem/25123줄 요약지방의 수 N, 각 지방의 예산요청 A, 총 예산 M을 입력받습니다. 이분 탐색의 범위를 설정하기 위해 예산요청 중 최댓값에 1을 더해 상한값으로 사용합니다. 이는 모든 예산요청이 상한액과 같은 경우를 포함하기 위함입니다.이분 탐색을 사용하여 상한액을 조정해가며 총 예산이 M 이하가 되는 최대 상한액을 찾습니다. 이는 Upper Bound를 찾는 과정으로, 조건을 만족하는 최댓값을 찾습니다.Upper Bound로 찾은 값은 조건을 만족하는 최솟값보다 1 큰 값이므로, 최종 결과에서 1을 빼줍니다. 이렇게 얻은 값이 실제로 배정 가능한 최대 예산이 됩니다.코드// package boj2512;import java.io.*;impo..

Problem_Solving 2024.05.03

백준(BOJ) 1654 : 랜선 자르기 (실버2) / 자바(Java) 풀이

문제https://www.acmicpc.net/problem/16543줄 요약K개의 랜선과 필요한 랜선의 개수 N을 입력받아, 각 랜선의 길이를 배열 A에 저장합니다. 랜선 길이의 최댓값이 2^31-1일 수 있으므로, s, e, mid를 비롯한 관련 변수들을 long 타입으로 선언하여 오버플로우를 방지합니다.이분 탐색을 사용하여 랜선을 자를 수 있는 최대 길이를 찾습니다. 중간 길이 mid로 랜선을 잘랐을 때 나오는 랜선의 개수를 long 타입의 result에 누적하여 N과 비교합니다. 이는 upper bound를 찾는 과정으로, 조건을 만족하는 최대 길이를 탐색합니다.최종적으로 이분 탐색이 종료되었을 때의 끝 길이 e가 최대 랜선 길이가 되며, 이를 출력합니다. Upper bound 탐색 결과로 얻은 ..

Problem_Solving 2024.05.02

백준(BOJ) 2805 : 나무 자르기 (실버2) / 자바(Java) 풀이

문제https://www.acmicpc.net/problem/28053줄 요약이분 탐색을 사용하여 시작 높이와 끝 높이를 조정해가며 최적의 높이를 찾습니다.Upper bound는 조건을 만족하는 가장 큰 값을 찾는 것으로, 이 문제에서는 적어도 M미터의 나무를 집에 가져갈 수 있는 절단기의 최대 높이를 의미합니다.잘린 나무의 길이를 누적하여 필요한 길이와 비교하며, 조건에 따라 탐색 범위를 좁혀나갑니다. 잘린 나무의 길이가 필요한 길이보다 크거나 같을 때 시작 높이를 증가시키고, 작을 때는 끝 높이를 감소시키는 방식으로 upper bound를 찾아갑니다.코드// package boj2805;import java.io.*;import java.util.stream.Stream;public class Mai..

Problem_Solving 2024.05.02

백준(BOJ) 1920 : 수 찾기 (실버4) / 자바(Java) 풀이

문제https://www.acmicpc.net/problem/19203줄 요약입력받은 배열 A를 정렬하고, 배열 B의 각 원소에 대해 이분 탐색을 수행합니다.이분 탐색이란 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 배열의 중간 위치를 기준으로 찾고자 하는 값과 비교하여 왼쪽 또는 오른쪽 부분 배열을 선택하여 탐색 범위를 반씩 줄여나가는 방식으로 동작합니다.이분 탐색은 시간 복잡도 O(log N)으로, 선형 탐색의 O(N)보다 훨씬 빠르게 탐색을 수행할 수 있습니다.코드// package boj1920;import java.io.*;import java.util.Arrays;import java.util.stream.Stream;public class Main { public static void..

Problem_Solving 2024.05.02