https://leetcode.com/discuss/study-guide/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems
어떤 문제든지 풀기 쉽게 만들어진 binary search 템플릿을 정리한 좋은 글이 있어서 정리해봤다.
템플릿은 아래와 같다.
int binary_search(...) {
while (left < right) {
mid = left + (right - left) / 2;
if (condition(...)) {
right = mid;
} else {
left = mid + 1;
}
}
return left
}이는 다음을 보장한다.(중요)
- loop가 종료된 뒤
left는condition()을 만족하는 가장 작은 값이 된다.
문제별로 처리해야할 조건은 condition()에서 알고리즘을 구현하면 된다. left < right 조건으로 루프를 돌고 마지막에 left를 처리하면 된다.
704. Binary Search [E]
가령 가장 기본적인 이문제의 경우 아래와 같이 템플릿을 적용할 수 있다.
class Solution {
bool condition(vector<int> &nums, int idx, int tgt) {
if (nums[idx] >= tgt)
return true;
else
return false;
}
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (condition(nums, mid, target)) {
right = mid;
} else {
left = mid + 1;
}
}
if (nums[left] == target)
return left;
else
return -1;
}
};condition을 함수로 분리 안하고 간략하게 표현하면 아래와 같다.
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
if (nums[left] != target)
return -1;
return left;
}
};278. First Bad Version [E]
문제의 경우도 이전에 내가 풀었던 풀이는 조건이 복잡했는데, 이 템플릿을 적용하면 매우 간단명료하게 해결할 수 있다.
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (isBadVersion(mid) == true)
right = mid;
else
left = mid + 1;
}
return left;
}
};69. Sqrt(x) [E]
이 문제의 경우 condition이 mid*mid > x 인데, 예제 입력이 8인경우 이 조건을 만족하는 가장 작은 값은 3이 된다. 문제가 요구하는것이 이것보다 하나 작은 값이 므로(이때 정답은 2가 되어야한다). left - 1 이 최종 답이다.
right = x + 1인 이유는 x가 0이거나 1일때를 처리하기 위해서. C에서 overflow가 발생해 형변환 했음 주의.
class Solution {
public:
int mySqrt(int x) {
long left = 0;
long right = (long)x + 1;
long mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (mid * mid > x)
right = mid;
else
left = mid + 1;
}
return (int)left - 1;
}
};1011. Capacity To Ship Packages Within D Days [M]
문제
패키지의 무게 배열이 주어지고, 이것들을 나눠서 실을 수 있는 일 수가 주어진다. 최소가 되는 하루 총무게는 얼마인가? (순서는 뒤바뀔수 없고 연속된 패키지를 sub array로 묶어야한다)
가령 아래예시의 경우 5일에 나눠 싣는다고 하면, 모든 경우의 수중에서 15가 하루 최소 무게가 된다.
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10아이디어
- 이게 어떻게 binary search가 되는지 의아할수 있다. (해설을 보며 배운 문제다)
- Binary Search는 두 종류의 유형이 있다.
- 정렬된 배열 인덱스로 binary search 하는 경우 -> O(logn)
- 어떤 결과 값을 Up & Down 으로 맞추는 경우(주어진 배열을 이용해 계산) -> O(nlogn)
- 이 문제는 최종 답(하루 총 무게)을 Up & Down으로 binary search 하는 문제다. (하루 총 무게의 left/right는 가능한 범위는 미리 계산)
- binary search 템플릿 을 활용, condition() 에서 주어진 배열을 이용해 Up할지 Down할지 계산하면 되는것!
- 아주 훌륭한 문제인것 같다. 많이 배웠다.
- 거의 유사한 유형의 문제로는
해결
condition()에서 계산하는것은 capacity가 주어질때, 그 값을 기준으로 배열을 나누면 일수를 맞출수 있는지 아닌지를 계산한다.
[1,2,3,4,5,6,7,8,9,10]
^가령 이 경우 capacity가 (10,55의) mid값 32로 주어지면 5번 이하로 나눠서 담기에 충분한 무게치다. 따라서 정답은 32보다 더 작을 가능성이 있다. 따라서 right = 32로 만들고 다시 binary search 하는것이다.
class Solution {
bool condition(vector<int>& weights, int capa, int tgt_days) {
// check how many days is needed when using capa value for capacity
// if needed days are less than the target days, it can be a answer
// else if needed days is larger than tgt_days, it means that, it is too samll to be a capacity
int days = 1;
int sum = 0;
for (int i = 0; i < weights.size(); i++) {
sum += weights[i];
if (sum > capa) {
sum = weights[i];
days++;
}
}
if (days > tgt_days) // if needed days is larger than tgt_days
return false;
return true;
}
public:
int shipWithinDays(vector<int>& weights, int days) {
// <up & down game> for matching capacity value.
// <up & down game> will be O(nlogn), not O(logn), because, it is not binary search on the array
int left = *std::max_element(weights.begin(), weights.end()); // can be a minimum capacity value
int right = std::accumulate(weights.begin(), weights.end(), 0); // maximun capacity
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (condition(weights, mid, days)) // mid value can be a capacity but there could be more smaller capacity value
right = mid;
else // mid value is too small to be a capacity, so increasing it. and check condition again.
left = mid + 1;
}
return left;
}
};410. Split Array Largest Sum [H]
문제
주어진 배열을 m개로 나눌때(연속된 sub array로), m개의 sub array합중에 가장큰값이, 모든 경우의수에서 가장 최소가 되게하는 알고리즘을 작성해라.
(Write an algorithm to minimize the largest sum among these m subarrays.)
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.아이디어
- Up & Down 게임 binary search 유형의 문제. 풀이는 아래 문제와 거의 완전동일하다. 해설은 아래 글에 작성했음.
해결
class Solution {
bool check_mid_capable(vector<int> nums, int candidate, int tgt_split) {
// check how many split with candidate value
int split = 1;
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (sum > candidate) {
sum = nums[i];
split++;
}
}
if (split > tgt_split) // if candidate value sperate more than m, then false
return false;
return true;
}
public:
int splitArray(vector<int>& nums, int m) {
int left = *std::max_element(nums.begin(), nums.end());
int right = std::accumulate(nums.begin(), nums.end(), 0);
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (check_mid_capable(nums, mid, m)) // if mid can seperate m times. it means there could be more small value exist.
right = mid;
else // means mid value is too small,
left = mid + 1;
}
return left;
}
};875. Koko Eating Bananas [M]
문제
코코라는 동물(원숭이?)이 바나나더미를 먹는다. 사육사가 오기 전까지 제한시간이 주어지고 모든 더미를 먹어야한다. 시간당 최소한으로 먹을수 있는 갯수는?
(단, 만약 시간당23개를 먹을 수 있다면, 30은 두시간이 걸리고, 11은 1시간이 걸린다.)
Input: piles = [30,11,23,4,20], h = 6
Output: 23https://leetcode.com/problems/koko-eating-bananas/
해결 O(nlogn)
이 문제도 템플릿을 이용한 Binary search문제다. Up & Down으로 정답을 찾고 그것을 찾을때 배열값을 가지고 계산(O(n))한다.
class Solution {
bool condition(vector<int> piles, int speed, int limit_h) {
// check the speed is enough to finish all of banana piles
int tot_time = 0;
for (int i = 0; i < piles.size(); i++)
tot_time += (piles[i] / speed) + (piles[i] % speed != 0);
if (tot_time <= limit_h)
return true;
return false;
}
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1;
int right = *std::max_element(piles.begin(), piles.end());
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (condition(piles, mid, h)) // enough speed. much less speed could be enough as well.
right = mid;
else // too slow
left = mid + 1;
}
return left;
}
};맨처음에 condition계산을 아래와같이 했는데 TLE가 나왔다. 근데 그냥 단순계산으로 해결할수 있는거였다.
bool condition(vector<int> piles, int speed, int limit_h) {
int idx = 0;
while (idx < piles.size()) {
if (speed >= piles[idx]) {
piles[idx] = 0;
idx++;
} else {
piles[idx] = piles[idx] - speed;
}
hour--;
if (hour < 0)
break;
}
if (hour >= 0)
return true;
return false;
}1482. Minimum Number of Days to Make m Bouquets [M]
문제
몇일 뒤에 꽃이 피는지가 적힌 bloomDay[] 배열이 주어진다. 꽃이 피면 꽃다발을 만들수 있다. 하나의 꽃다발은 k개이어야하고, 반드시 인접한 꽃만 선택할 수 있다. 총 m개의 꽃다발을 만든다고 할때, 최소 몇일 뒤에 작업을 완수할수 있는가?
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.아이디어
- 이전 문제와 마찬가지로 템플릿을 이용한 이진탐색 문제, Up & Down 형식의 이진탐색 문제다.
해결
class Solution {
bool condition(vector<int> bloomDay, int remain_days, int m, int k) {
// check k's continous subarray are exist m times
int cont_cnt = 0;
for (int i = 0; i < bloomDay.size(); i++) {
cont_cnt++;
if (bloomDay[i] > remain_days) {
if (cont_cnt-1 >= k)
m--;
cont_cnt = 0;
} else if (cont_cnt >= k) {
m--;
cont_cnt = 0;
}
if (m <= 0)
return true;
}
if (cont_cnt >= k)
m--;
if (m <= 0)
return true;
return false;
}
public:
int minDays(vector<int>& bloomDay, int m, int k) {
if (m * k > bloomDay.size())
return -1;
int left = *std::min_element(bloomDay.begin(), bloomDay.end());
int right = *std::max_element(bloomDay.begin(), bloomDay.end());
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2; // the remain days what we have to find
if (condition(bloomDay, mid, m, k)) // check mid days is possible to make bouquet
right = mid;
else // it's not possible
left = mid + 1;
}
return left;
}
};162. Find Peak Element
문제
배열에서 peak 지점의 인덱스를 리턴하라. 만약 peak가 여러개면 아무지점이나 리턴해도 된다. 배열의 양 끝은 -∞ 라고 가정해라. (단 arr[i] != arr[i+1] 항상 성립한다)
아디이어
peak지점은 inc-dec 지점이다. 만약에 한 지점 i를 선택했는데
- 왼쪽값이 더 작다면 즉, arr[i-1] < arr[i] 라면, peak는 반드시 i이상 우측에 존재한다는 뜻.
- 오른쪽값이 더 작다면 arr[i] > arr[i+1], peak는 반드시 i이하 왼쪽에 존재한다는 뜻.
따라서 이렇게 탐색 범위를 1/2 씩 좁히는 바이너리 서치를 할 수 있다.
해결
binary search 템플릿 사용.
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.int findPeakElement(int* nums, int numsSize){
int left = 0, right = numsSize - 1, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] > nums[mid+1]) { // 답은 좌측(0 ~ mid) 중에 존재한다.
right = mid;
} else { // 답은 우측(mid+1 ~ size-1) 에 존재
left = mid + 1;
}
}
return left;
}이건 맨 처음 풀어봤던 조금 더 비효율적인 풀이.
int findPeakElement(int* nums, int numsSize){
int left = 0, right = numsSize - 1, mid = 0;
// check input valid range :
if (numsSize == 0) {
fprintf(stderr, "invalid input\n");
return 1;
}
while (left < right) {
mid = left + (right - left) / 2;
if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) {
right = mid - 1;
} else if (mid + 1 < numsSize && nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
return mid;
}
/* 처음에 나머지 조건을 모두 체크 했는데 이럴 필요가 없음
} else if (((mid - 1 >=0 && mid + 1 < numsSize) && (nums[mid - 1] < nums[mid] && nums[mid > nums[mid - 1]])) ||
mid == 0 && nums[mid + 1] < nums[mid] ||
mid == numsSize - 1 && nums[mid] > nums[mid - 1]) {
return mid;
}
*/
}
return left;
}153. Find Minimum in Rotated Sorted Array
문제
오름차순 정렬된 배열이 몇차례 회전한 상태로 주어진다. 가령 [3,4,5,1,2]는 [1,2,3,4,5] 가 3번 회전한 상태. 이때 배열에서 가장 작은 수를 찾아서 리턴하라. 단 시간복잡도는 O(logn)이하 이어야한다.
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.아이디어
아래 네가지 모든 경우의 수를 따져보면,
주어진 범위에서 nums[mid] < nums[right] 이라면 정답위치는 반드시 [left] ~ [mid] 사이에 있다.
[2,3,4,5,6,0,1]
^ ^
[6,0,1,2,3,4,5] answer must be in left part
^ < ^
[0,1,2,3,4,5,6] answer must be in left part
^ < ^
[1,2,3,4,5,6,0]
^ ^바이너리 서치에서 좌우 범위를 좁히는 조건을 찾는게 생각보다 오래걸렸다. 이럴땐 모든 경우의 수를 적어보고 패턴을 찾아보는게 더 빠를것같다. 결과적으로 그 조건이 대단히 간단해서 놀랐음(?)
해결
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1, mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] < nums[right])
right = mid;
else
left = mid + 1;
}
return nums[left];
}
};
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)