이진탐색

2467 용액 - 골드5 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전에 비슷한(같은) 문제를 푼 적이 있는데, 그 때는 포인터 2개를 이용하여 문제를 풀었다 이번에는 이진탐색으로 풀어보려고 한다 산성과 알칼리 용액 모두 합쳐 오름차순 정렬한다 알칼리 용액들을 하나씩 빼면서 배열에서 내 절댓값과 가장 가까운 값을 찾는다 [작음, 작음, (같거나)큼, 큼, 큼, ...] 이런 꼴로 나올 것이기 때문에 lowerbound를 구해준다 l..

어느정도 이진탐색 기본기를 다진 것 같으니 활용을 열심히 해보자! 2512 예산 - 실버2 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 처음부터 배정이 가능한 경우 -> 예산의 최댓값 출력 배정 불가능 경우 -> 상한액 출력 그냥 상한액을 이진탐색으로 찾는다고 생각하면 되겠다 배정이 가능하면 오른쪽을 탐색, 배정이 불가능하면 왼쪽 탐색 [가능, 가능, 가능, 불가능, 불가능, ...] 이런식으로 나올 것이니 upperbound값을 구하..

Lower bound, Upper bound란? 그림을 보면 쉽게 이해할 수 있다. lower bound: 찾고자 하는 값이 처음 나타나는 위치 upper bound: 찾고자 하는 값 바로 뒤 위치 원래 이진탐색 코드 //오름차순 정렬된 arr에서 target값을 찾아 인덱스를 반환하는 함수 private int findIdx(int[] arr, int target) { int start = 0; int end = arr.length; while (start target end ..

이진탐색 관련 문제를 풀던 중, Arrays에 binarySearch 메서드가 있는 걸 발견하였다! 원래는 직접 이진탐색을 구현하여 사용하였지만 컬렉션에서 지원된다면 사용하는 게 더 효율적일 것 같다. 그래서 이번엔 binarySearch 메서드를 알아보려고 한다. 정의 binarySearch 메서드를 타고 들어가보면 이렇게 긴 설명이 있다. Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the r..

실버문제를 어느정도 풀어봤으니 이제 sorting 관련 골드 문제를 풀려고한다! https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 10억까지 정수로 나타내지고, 합은 최대 20억정도가 될 수 있으니 int값에 저장할 수 있음 처음 생각한 풀이(시간초과) 음수값을 저장하는 배열과 양수값을 저장하는 배열을 만들어 정렬한다 인덱스로 비교비교하면서 차이가 0에 가까운 애를 result에 저장한다 양수값이 하나도 없다면 ..