이분탐색6 [백준] 2512번 : 예산 – JAVA [자바] https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 문제 풀이 백준 2512번 예산은 실버 2 난이도의 이분 탐색 및 매개변수 탐색 문제이다. 이 문제에서는 N개의 예산 요청과 총 예산이 주어진다. 이때, 다음과 같은 조건을 만족하도록 예산을 배정하면 된다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한.. 2023. 8. 7. [백준] 1654번 : 랜선 자르기 – JAVA [자바] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 문제 풀이 백준 1654번 랜선 자르기는 실버 2 난이도의 이분 탐색 및 매개변수 탐색 문제이다. 이 문제에서는 랜선 K개와 랜선의 길이, 그리고 필요한 랜선의 개수 N이 주어진다. 이때, N개를 만들 수 있는 랜선의 최대 길이를 구하면 된다. 이 문제는 이분 탐색을 이용해서 풀 수 있다. 만약 이분 탐색에 대해 더 알고 싶으면 밑에 있는 링크를 참고하면 되겠다... 2023. 8. 7. [알고리즘] 이분 탐색 (Binary Search) 목차 이분 탐색이란? 이분 탐색 혹은 이진 탐색 (Binary Search)는 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이 알고리즘은 자료가 순서에 따라 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 따라서, 탐색할 때마다 검사 범위가 절반으로 줄어든다. 이분 탐색 의 진행 단계 이분 탐색에서는 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외하고, 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 .. 2023. 8. 7. [백준] 1920번 : 수 찾기 – JAVA [자바] https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 문제 풀이 백준 1920번 수 찾기는 실버 4 난이도의 정렬 및 이분 탐색 문제이다. 이 문제에서는 N개의 정수들이 주어지고 그다음에 M개의 정수들이 주어진다. 이 M개의 정수들 중에서 전에 주어진 수면 1을 출력하고 이전에 주어진 수가 아니면 0을 출력하면 된다. 이 문제는 HashSet을 이용해서 풀 수도 있겠지만 이 풀이에서는 정렬과 이분.. 2023. 8. 3. 이전 1 2 다음 반응형
