알고리즘25 [백준-실버3] 2805번 나무 자르기 (이분 탐색, 파이썬) https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net - 상근이는 적어도 나무 M미터가 필요함 - N개 나무의 높이가 주어짐 - 필요한만큼만 나무를 가져가기 위해 자를 높이 H를 정해야함. - 주어진 나무의 높이가 H보다 크면 (나무 높이 - H)만큼 길이를 자르게 되고, 작으면 잘린 나무가 없음 - 설정할 수 있는 나무 높이는 0이상 정수 - 절단기에 설정할 수 있는 높이 H의 최댓값을 출력 - start를 .. 2022. 4. 12. [백준-실버3] 2512번 예산 (이분 탐색, 파이썬) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net - N개의 지방에서 각각 예산을 요청함, 국가 예산의 총액은 정해져있음 - 예산의 상한선을 정해야하는데, 총액 안에 모든 요청이 배정 될 수 있으면 요청한 금액을 그대로 배정 - 예산이 부족하면 상한선을 초과하는 예산은 상한선만큼만 지급 - 배정된 예산 중 최댓값을 구하는 문제 - start = 1, end는 입력 예산 중 가장 큰 값으로함 - 여기서 mid가 예산의 상한액, check는 예.. 2022. 4. 12. [백준-실버4] 10815번 숫자 카드(이분 탐색, 파이썬) https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net - 문제에서 주어진 N이 10만이다. 따라서 시간 복잡도가 O(n*n)이면 시간초과가 발생한다. - 이를 해결하기 위해 이분 탐색을 이용했다. - N개의 숫자 리스트와 M개의 숫자 리스트가 주어지고, M의 원소가 N에 있는지 확인하는 문제 - 1920번 수 찾기와 출력 end = ' '빼고 똑같음 - binary_search(arr, target) 함수 ## arr .. 2022. 4. 12. [백준-실버4] 1920번 수 찾기 (이분 탐색, 파이썬) 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 - 문제에서 주어진 N이 10만이다. 따라서 시간 복잡도가 O(n*n)이면 시간초과가 발생한다. - 이를 해결하기 위해 이분 탐색을 이용했다. - N개의 숫자 리스트와 M개의 숫자 리스트가 주어지고, M의 원소가 N에 있는지 확인하는 문제 - binary_search(arr, target) 함수 ## arr 리스트가 정렬되어 있어야함 - arr : .. 2022. 4. 12. 이전 1 2 3 4 ··· 7 다음