binary search4 [Python] 백준 2512번 : 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이 이진 탐색 문제이다. 최대 경우의 수가 10,000에 시간제한 1초로 이진 탐색을 쓰지 않으면 무조건 시간 초과가 난다. 오른쪽 값은 문제에서 원하는 상한액을 의미한다. 보통 이진 탐색 알고리즘은 정렬된 값 중에서 원하는 값을 찾는데 쓰인다. 하지만 여기선 이진 탐색으로 상한액을 조정해 예산을 계산한다. 예산이 크면 기준값을 줄이고 예산이 작으면 기준값을 올려주면 된다. 느낀 점 .. 2022. 7. 5. [C++] 백준 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 문제 풀이 이전 문제(BOJ 1654 : 나무 자르기)와 비슷한 문제이다. 다른 점은 딱 맞아떨어지지 않는다는 것이다. 적어도 M미터의 높이의 나무를 가져가야 한다. 즉, 1미터의 나무가 필요할 때 {1, 2, 2} 높이의 나무들이 주어진다면 1미터의 높이에서 잘라야 한다. 느낀 점 삼항 연산자를 사용해서 중간의 번거로운 계산을 줄였다! 이전과 코드가 똑같아.. 2021. 8. 5. [C++] 백준 1654번 : 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 N개의 랜선을 만드는데 그 길이를 최대로 만들어야 한다. 브루트 포스로 풀 수 있지만 무조건 시간 초과가 발생한다. 이진 탐색으로 탐색 횟수를 줄여야 한다. 가장 긴 길이와 가장 짧은 길이(1) 사이에 답이 존재한다. 이분 탐색을 통해서 그 중간 값과 비교할 텐데 잘랐을 경우 N개가 되는 값이 여러 개 존재한다. 그중에서 최댓값을 찾아야 해서 잘랐을 때 N개.. 2021. 8. 5. [C++] 백준 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 문제 풀이 이분 탐색의 쉬운 문제이다. 이분 탐색 시에는 정렬이 되어야 한다는 점만 기억하면 된다! 느낀 점 qsort로 정렬할 때는 틀렸다고 나와서 그냥 sort를 사용했는데 맞았다. 어떤 것이 잘못됐는지 모르겠다. 코드 #include #include using namespace std; int n, m; long long tmp; long lo.. 2021. 8. 3. 이전 1 다음