이번 글은 이분 탐색을 사용하는 알고리즘 문제를 좀 더 쉽게 풀기 위해 작성한 것이다.
대부분의 이분 탐색을 사용하는 문제는 특정 값을 찾는 문제보다도 주어진 조건을 만족하는 수 중에서 최대값을 찾거나, 최소값을 찾는 문제가 자주 등장한다.
무엇을 구하는 문제이냐에 따라서 이분 탐색에서 최종 반환하는 인덱스가 약간씩 달라진다.
-
특정값을 찾는 문제
-
최대값을 찾는 문제
-
최소값을 찾는 문제
아래 글은 기본적인 이분 탐색에 대한 개념을 정리한 것이다.
이분 탐색(Binary Search) - 특정값 찾기
이분 탐색(Binary Search) 정렬된 배열에서 특정 값을 검색할 때 사용하는 알고리즘 탐색을 진행하기 전에 반드시 배열이 정렬된 상태이어야 한다. 이분탐색 알고리즘 문제를 풀 때, 주어진 배열에
lotuslee.tistory.com
[특정값 찾기]
public static int binSearch(int n, int left, int right) {
int pl = left;
int pr = right;
do {
int pc = (pl + pr) / 2;
if (arr[pc] == n)
return pc;
if (arr[pc] < n)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return -1;
}
[최대값 찾기]
최대값 찾는 문제에서는 이분 탐색에서 최종적으로 pr을 반환한다. -> return pr;
왜 pr을 반환해야 하는지는 문제를 직접 풀어보면서 pl, pr, pc의 변화를 추적해보면서 이해해보길 바란다.
아래는 백준에서 최대값을 요구하는 대표적인 문제들과 그 소스코드이다.
public static int binSearch(int left, int right) {
int pl = left;
int pr = right;
do {
int pc = (pl + pr) / 2;
long sum = 0;
for (int i = 0; i < N; i++) {
if (arr[i] > pc)
sum += arr[i] - pc;
}
if (sum >= M)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return pr;
}
public static long binSearch(int[] arr, int n) {
long pl = 1;
long pr = n - 1;
do {
long pc = (pl + pr) / 2;
long cnt = getCount(pc);
if (cnt < (long) N)
pr = pc - 1;
else
pl = pc + 1;
} while (pl <= pr);
return pr;
}
public static int binSearch(int left, int right) {
int pl = left;
int pr = right - 1;
int pc;
do {
pc = (pl + pr) / 2;
if (setWifi(pc))
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return pr;
}
public static int binSearch(int left, int right) {
int pl = left;
int pr = right;
do {
int pc = (pl + pr) / 2;
if (bfs(pc))
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return pr;
}
public static int binSearch(int s, int e) {
int pl = s;
int pr = e;
int pc = 0;
do {
pc = (pl + pr) / 2;
int sum = 0;
for (int i = 0; i < N; i++)
sum += Math.min(arr[i], pc);
if (sum <= M) {
pl = pc + 1;
} else
pr = pc - 1;
} while (pl <= pr);
return pr;
}
[최소값 찾기]
최소값 찾는 문제에서는 이분 탐색에서 최종적으로 pl을 반환한다. -> return pl;
아래는 백준에서 최대값을 요구하는 대표적인 문제들과 그 소스코드이다.
public static long binSearch(long left, long right) {
long pl = left;
long pr = right;
long res;
do {
long pc = (pl + pr) / 2;
res = (Y + pc) * 100 / (X + pc);
if (res == Z)
pl = pc + 1;
else if (res > Z)
pr = pc - 1;
} while (pl <= pr);
return pl;
}
public static int binSearch(int left, int right) {
int pl = left;
int pr = right;
do {
int pc = (pl + pr) / 2;
int cnt = 1;
int sum = 0;
for (int i = 0; i < N; i++) {
sum += lesson[i];
if (sum > pc) {
sum = lesson[i];
cnt++;
}
}
if (cnt > M)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return pl;
}
public static int binSearch(int left, int right) {
int pl = left;
int pr = right;
do {
int pc = (pl + pr) / 2;
int cnt = 1;
int money = pc;
for (int i = 0; i < N; i++) {
if (arr[i] > money) {
money = pc;
cnt++;
}
money = money - arr[i];
}
if (cnt > M)
pl = pc + 1;
else
pr = pc - 1;
} while (pl <= pr);
return pl;
}'Algorithm & DS > 이분탐색' 카테고리의 다른 글
| 이분 탐색(Binary Search) (0) | 2021.03.01 |
|---|