Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net ##### 문제 ##### # 사대의 위치와 동물들의 위치가 주어졌을 때, # 잡을 수 있는 동물의 수를 출력하는 프로그램을 작성하시오. ##### 입력 ##### # 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), # 동물의 수 N (1 ≤ N ≤ 100,000), # 사정거리 L (1 ≤ L ≤ 1,000,..

▶ 문제 : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ##### 문제 ##### # 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, # 이 중 두 개의 서로 다른 용액을 혼합하여 # 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 전체 용액의 수 N이 입력된다. # N은 2 이상 100,000 이하이다. # 둘째 줄에는 용..

▶ 문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ##### 문제 ##### # 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. # 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) #..

▶ 문제 : 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과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. # 둘째 줄에는 나무의 높이가 주어진다. # 나무의 높이의 합은 항상 M보다 크..

▶ 문제 : https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ##### 문제 ##### # C개의 공유기를 N개의 집에 적당히 설치해서, # 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 #공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. # ..

▶ 문제 : 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과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. # 둘째 줄에는 나무의 높이가 주어진다. # 나무의 높이의 합은 항상 M보다 크..

이분 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값(X)을 찾는 알고리즘을 의미한다. X를 찾는 과정은 다음과 같다. 우선, 배열의 중간 값을 X와 비교한다. X가 해당 중간 값보다 작으면 탐색의 대상이 되는 배열을 중간 값 기준 좌측의 데이터로, 중간 값보다 크면 우측의 데이터로 조정한다. X를 찾을 때까지 이 과정을 반복한다. 이분 탐색의 시간 복잡도는 O(logN)이다. ### 직접 구현 ### def binary_search(target, A, left, right): if left > right: return False mid = (left + right) // 2 if target == A[mid]: return True elif target < A[mid]: return binary_s..