Binary Search
데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
-> 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾음
-> O(logN)
오름차순으로 정렬된 데이터에서의 반복 과정
- 현재 데이터에서 중앙값(median) 선택 -> 평균 X
- 중앙값 > 타겟 데이터 일때 중앙값을 기준으로 왼쪽 데이터셋 선택
- 중앙값 < 타겟 데이터일때 중앙값 기준으로 오른쪽 데이터셋 선택
- 위 1~3 과정을 반복하다가 중앙값 == 타겟 데이터일때 탐색 종료
문제 1(수 찾기) - 실버4
https://www.acmicpc.net/problem/1920
간단한 코드 예시
while(start <= end){
int mid = (start + end) / 2;
int midVal = arr[mid];
if(midVal > target){
end = mid-1;
}else if(midVal < target){
start = mid+1;
}else{
find = true;
break;
}
}문제2(기타 레슨) - 실버 1(핵심)
https://www.acmicpc.net/problem/2343
블루레이의 크기가 모두 같고, 녹화 순서가 바뀌지 않아야 함이라는 문제 조건
-> 이진 탐색 떠올릴 수 있어야
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
// 레슨의 최대값을 시작인덱스, 모든 레슨의 총합을 종료 인덱스로 지정
int start = 0; int end = 0;
for(int i = 0; i < N; i++){
arr[i] = Integer.parseInt(st.nextToken());
if(start < arr[i]) start = arr[i];
end += arr[i];
}
while(start <= end){
int middle = (start + end) / 2;
int sum = 0;
int count = 0;
// 만들어진 블루레이 갯수 확인
for(int i = 0; i < N; i++){
if(sum + arr[i] > middle){
count++;
sum = 0;
}
sum += arr[i];
}
if(sum != 0){
count++;
}
if(count > M){
start = middle+1;
}else{
// 현재 M개 이내이므로, 현재 중간값으로 블루레이를 만들 수 있다
// 하지만 더 작은 블루레이 길이로 만들기 위해 탐색 범위를 좁힘
end = middle-1;
}
}
System.out.println(start);
}
}문제3(K번쨰수) - 골드2(Hard)
N이 커서 2차원 배열을 다 만들고 정렬할 수 없음
-> 역으로 이분 탐색을 통해 x 이하의 수가 배열 전체에 몇개 있는지 묻는 질문을 반복적으로 던짐
-> 만약 x-1이하의 수는 K개 미만이지만, x이하의 수가 K개 이상이라면 x는 k번쨰 수가 됨
자세한 풀이 : https://st-lab.tistory.com/281
솔직히 아직 제대로 이해하지 못했다.. 꼭 한번 다시 풀어보자!
문제 4(나무 자르기) - 실버 2
https://www.acmicpc.net/problem/2805
어찌어찌 풀긴했으나 어렵다...(아직 틀에 맞춰 값을 끼워넣는..? 느낌인것 같다)
설정한 목재절단기의 높이가 커질수록 가져갈수 있는 벌목 양이 작다는것을 인지하고 다시 한번 풀어보자~
타겟과 미드의 값이 같을때 최솟값을 구하는 경우 right = mid-1을 하고 최대값을 구할때 left=mid+1을 함
최댓값 구하는 경우엔 right return
최솟값을 구하는 경우에는 left return
-> 위 로직은 조금만 생각해보면 알수 있다! 까먹었다면 그려서 이해해보자
최솟값을 구하는 경우엔 right를 떙겨오고, left return
최댓값을 구하는 경우엔 left를 떙겨오고, right return
문제 5(예산) - 실버 3
그나마 쉬운 문제
문제 6(랜선 자르기) - 실버 2
이 문제도 적당히 할만함
문제 7(공유기 설치) - 골드 4
https://www.acmicpc.net/problem/2110
못풀었다... 그리디 알고리즘이 사용되는것 같은데 이를 정복한 후 다시 풀어보자..ㅠㅠ
문제 8(드래곤 앤 던전) - 골드4
정말어려웠따 ㅠㅠ, 오버 플로우도 많이 발생하고 결투를 하는 상황을 while문으로 돌리다가 시간초과도 떴었다
import java.io.*;
import java.util.*;
public class Main {
static int N,ATK;
static long[][] rooms;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
ATK = Integer.parseInt(st.nextToken());
rooms = new long[N][3];
long maxATK = 0;
for(int i = 0; i < N; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j < 3; j++){
rooms[i][j] = Integer.parseInt(st.nextToken());
}
}
long start = 0; // 최소 maxHP(몬스터가 없는 경우)
long end = 1000000L * ((1000000L/ATK)+1) * N; // 여기서 1000000L로 안했다가 오버플로우 여러번 발생
System.out.println(binarySearch(start,end));
}
public static long binarySearch(long start, long end) {
while(start <= end){
long mid = (start+end) / 2;
long tempHP = mid;
long tempATK = ATK;
boolean isDead = false;
for(int i = 0; i < N; i++){
if(rooms[i][0] == 1){
// 몬스터 만난 경우 [1]은 공격력 [2]는 체력
long monsATK = rooms[i][1]; long monsHP = rooms[i][2];
long requiredHits = 0;
if(monsHP % tempATK == 0){// 원래 이렇게 안하고 반복문 돌리다 시간초과
requiredHits = (monsHP / tempATK);
}else{
requiredHits = (monsHP / tempATK) + 1;
}
tempHP -= monsATK * (requiredHits-1);
if(tempHP <= 0){
isDead = true;
break;
}
}else{
// 포션인 경우
tempATK += rooms[i][1];
tempHP = Math.min(tempHP + rooms[i][2], mid);
}
if(isDead){
break;
}
}
if(isDead){
// 죽은 경우 맥스 HP 늘려야
start = mid+1;
}else if(tempHP > 0){
// 클리어 한 경우, 살았다면 탐색 범위를 좁히기 위해 end = mid-1
end = mid-1;
}
}
return start;
}
}다음에 풀어 볼 문제
https://www.acmicpc.net/problem/15732
골드2문제!
