이분 탐색

[BOJ/JAVA] 6209번: 제자리 멀리뛰기

6209번: 제자리 멀리뛰기https://www.acmicpc.net/problem/6209키워드돌섬에서 탈출구 사이에는 총 n개의 작은 돌섬선생님은 이 n개의 작은 돌섬들 중 m개를 제거하여 학생들이 최대한 멀리뛰기 연습의 효율을 높이기 위해서 학생들이 각 돌섬을 점프한 거리의 최솟값을 최대한 크게 하려고 한다.구현매개변수 탐색을 이용하여 구현한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 돌섬으로부터 탈출구 까지의 최대 거리(1_000_000_000) 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;m개를 제거했을 때, 거리가 mid 이상이 되도록 할 수 있는가? mid 길이로 나눠줄 수 있다면low = mid + 1 ..

[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자https://www.acmicpc.net/problem/20551키워드먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.그 다음 M개의 질문을 한다.제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력단, D가 B에 존재하지 않는 경우에는 -1를 출력구현정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다. 템플릿low, high 모두 범위 안에 들어오도록 한다.반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)해당 숫자를 찾은 경우가장 앞에 있는 원..

[BOJ/JAVA] 15810번: 풍선 공장

15810번: 풍선 공장https://www.acmicpc.net/problem/15810키워드풍선을 담당하는 N명의 스태프대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰각 스태프가 풍선 하나를 만드는 시간(분) A_i를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?구현매개변수 탐색을 이용하여 구현한다.범위가 int 범위를 초과하므로 long 자료형을 이용한다.템플릿low, high 값은 항상 범위 내로 설정한다.low = 1high = 가장 빨리 만들 수 있는 직원이 걸리는 시간 * M 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2;mid 시간내로 만들 수 있는지 체크한다. mid 시간 내로 만들 수 있다면high = ..

[BOJ/JAVA] 16401번: 과자 나눠주기

16401번: 과자 나눠주기https://www.acmicpc.net/problem/16401키워드반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.구현나누는것 여러개로 나눌 수 있지만, 하나로 합칠 수 없음에 주의하자. 매개변수 탐색을 이용하여 구현한다. 템플릿low, high 값은 항상 범위 내로 설정한다.low = 0high = 길이가 가장 긴 과자 반복문의 속행 조건은 low≤high 이다. long mid = (low + high) / 2..

[BOJ/JAVA] 2110번: 공유기 설치

2110번: 공유기 설치도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.https://www.acmicpc.net/problem/2110키워드집에 공유기 C개를 설치가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치구현huses[] 각 집의 좌표를 오름차순으로 정렬한다.solution()인접한 두 공유기 사이의 거리를 매개변수로 이분탐색을 진행한다.초기 low는 1초기 high는 마지막원소 - 첫번째 원소 (이 때가 차이가 가장 크므로..)[low, high]에 속하면서, mid = (lo..

[BOJ/JAVA] 2343번: 기타 레슨

키워드블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.M개의 블루레이에 모든 기타 강의 동영상을 녹화하블루레이의 크기(녹화 가능한 길이)를 최소M개의 블루레이는 모두 같은 크기구현블루레이 크기를 매개변수로하여 이분 탐색을 진행한다.lectures[]강의의 누적합low = 가장 긴 길이의 강의high = 모든 강의 길이의 합canMake()mid = (low+high)/2 의 블루레이 크기로 녹화할 수 있는지 체크0부터 누적합을 계산하며 진행한다. mid보다 커지는 순간 → 현재 인덱스의 강의를 제외한 이전 강의를 현재 블루레이에 담는다.마지막 인덱스가 아닌데, 블루레이의 수가 M이상이라면 .. false 반환반복문이 끝난 경우 → 디스크가 남는 경우디스크의 크기는 항상 한 개의 강의를 넣을만큼 충분..

[BOJ/JAVA] 23631번: 진심 좌우 반복뛰기

키워드위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.정확히 (N - 1)m만 뛸 것구현다음을 정의하자. 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.n전부 뛴 횟수전부 뛸 수 있는 n값을 구한다.low = 0high = 5000(5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.n을 매개변수로 하여, 이분 탐색으로 진행한다.숫자가 매우 크므로, java에서는 BigInteger를 활용한다.n번째에서 전부 뛰었을 때 위치는 다음과 같다.이동 횟수좌표1K2-K32K4-2K53K6-4K위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 ..