06_searching.cpp

Download
cpp 327 lines 9.3 KB 
  1/*
  2 * 탐색 μ•Œκ³ λ¦¬μ¦˜ (Searching Algorithms)
  3 * Binary Search, Lower/Upper Bound, Parametric Search
  4 *
  5 * 효율적인 탐색 κΈ°λ²•λ“€μž…λ‹ˆλ‹€.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11#include <cmath>
 12
 13using namespace std;
 14
 15// =============================================================================
 16// 1. 이뢄 탐색 κΈ°λ³Έ
 17// =============================================================================
 18
 19int binarySearch(const vector<int>& arr, int target) {
 20    int left = 0, right = arr.size() - 1;
 21
 22    while (left <= right) {
 23        int mid = left + (right - left) / 2;
 24
 25        if (arr[mid] == target)
 26            return mid;
 27        else if (arr[mid] < target)
 28            left = mid + 1;
 29        else
 30            right = mid - 1;
 31    }
 32
 33    return -1;
 34}
 35
 36// μž¬κ·€ 버전
 37int binarySearchRecursive(const vector<int>& arr, int target, int left, int right) {
 38    if (left > right) return -1;
 39
 40    int mid = left + (right - left) / 2;
 41
 42    if (arr[mid] == target)
 43        return mid;
 44    else if (arr[mid] < target)
 45        return binarySearchRecursive(arr, target, mid + 1, right);
 46    else
 47        return binarySearchRecursive(arr, target, left, mid - 1);
 48}
 49
 50// =============================================================================
 51// 2. Lower Bound / Upper Bound
 52// =============================================================================
 53
 54// target 이상인 첫 번째 μœ„μΉ˜
 55int lowerBound(const vector<int>& arr, int target) {
 56    int left = 0, right = arr.size();
 57
 58    while (left < right) {
 59        int mid = left + (right - left) / 2;
 60        if (arr[mid] < target)
 61            left = mid + 1;
 62        else
 63            right = mid;
 64    }
 65
 66    return left;
 67}
 68
 69// target 초과인 첫 번째 μœ„μΉ˜
 70int upperBound(const vector<int>& arr, int target) {
 71    int left = 0, right = arr.size();
 72
 73    while (left < right) {
 74        int mid = left + (right - left) / 2;
 75        if (arr[mid] <= target)
 76            left = mid + 1;
 77        else
 78            right = mid;
 79    }
 80
 81    return left;
 82}
 83
 84// target의 개수
 85int countOccurrences(const vector<int>& arr, int target) {
 86    return upperBound(arr, target) - lowerBound(arr, target);
 87}
 88
 89// =============================================================================
 90// 3. νšŒμ „ μ •λ ¬ λ°°μ—΄ 탐색
 91// =============================================================================
 92
 93int searchRotated(const vector<int>& arr, int target) {
 94    int left = 0, right = arr.size() - 1;
 95
 96    while (left <= right) {
 97        int mid = left + (right - left) / 2;
 98
 99        if (arr[mid] == target)
100            return mid;
101
102        // μ™Όμͺ½μ΄ 정렬됨
103        if (arr[left] <= arr[mid]) {
104            if (arr[left] <= target && target < arr[mid])
105                right = mid - 1;
106            else
107                left = mid + 1;
108        }
109        // 였λ₯Έμͺ½μ΄ 정렬됨
110        else {
111            if (arr[mid] < target && target <= arr[right])
112                left = mid + 1;
113            else
114                right = mid - 1;
115        }
116    }
117
118    return -1;
119}
120
121// νšŒμ „ λ°°μ—΄μ˜ μ΅œμ†Ÿκ°’
122int findMin(const vector<int>& arr) {
123    int left = 0, right = arr.size() - 1;
124
125    while (left < right) {
126        int mid = left + (right - left) / 2;
127        if (arr[mid] > arr[right])
128            left = mid + 1;
129        else
130            right = mid;
131    }
132
133    return arr[left];
134}
135
136// =============================================================================
137// 4. νŒŒλΌλ©”νŠΈλ¦­ μ„œμΉ˜
138// =============================================================================
139
140// λ‚˜λ¬΄ 자λ₯΄κΈ° (μ΅œλŒ€ 높이)
141long long cutWood(const vector<int>& trees, int h) {
142    long long total = 0;
143    for (int tree : trees) {
144        if (tree > h) {
145            total += tree - h;
146        }
147    }
148    return total;
149}
150
151int maxCuttingHeight(const vector<int>& trees, long long need) {
152    int left = 0;
153    int right = *max_element(trees.begin(), trees.end());
154    int result = 0;
155
156    while (left <= right) {
157        int mid = left + (right - left) / 2;
158        if (cutWood(trees, mid) >= need) {
159            result = mid;
160            left = mid + 1;
161        } else {
162            right = mid - 1;
163        }
164    }
165
166    return result;
167}
168
169// 배솑 μ΅œμ†Œ μš©λŸ‰
170bool canShip(const vector<int>& weights, int capacity, int days) {
171    int currentWeight = 0;
172    int dayCount = 1;
173
174    for (int w : weights) {
175        if (w > capacity) return false;
176        if (currentWeight + w > capacity) {
177            dayCount++;
178            currentWeight = w;
179        } else {
180            currentWeight += w;
181        }
182    }
183
184    return dayCount <= days;
185}
186
187int shipWithinDays(const vector<int>& weights, int days) {
188    int left = *max_element(weights.begin(), weights.end());
189    int right = 0;
190    for (int w : weights) right += w;
191
192    while (left < right) {
193        int mid = left + (right - left) / 2;
194        if (canShip(weights, mid, days))
195            right = mid;
196        else
197            left = mid + 1;
198    }
199
200    return left;
201}
202
203// =============================================================================
204// 5. μ‹€μˆ˜ 이뢄 탐색
205// =============================================================================
206
207// 제곱근 (μ†Œμˆ˜μ κΉŒμ§€)
208double sqrtBinary(double x, double precision = 1e-10) {
209    if (x < 0) return -1;
210    if (x < 1) {
211        double lo = x, hi = 1;
212        while (hi - lo > precision) {
213            double mid = (lo + hi) / 2;
214            if (mid * mid < x)
215                lo = mid;
216            else
217                hi = mid;
218        }
219        return (lo + hi) / 2;
220    }
221
222    double lo = 1, hi = x;
223    while (hi - lo > precision) {
224        double mid = (lo + hi) / 2;
225        if (mid * mid < x)
226            lo = mid;
227        else
228            hi = mid;
229    }
230    return (lo + hi) / 2;
231}
232
233// =============================================================================
234// 6. 2D λ°°μ—΄ 탐색
235// =============================================================================
236
237// ν–‰κ³Ό 열이 μ •λ ¬λœ 2D λ°°μ—΄ 탐색
238bool searchMatrix(const vector<vector<int>>& matrix, int target) {
239    if (matrix.empty()) return false;
240
241    int rows = matrix.size();
242    int cols = matrix[0].size();
243    int row = 0, col = cols - 1;
244
245    while (row < rows && col >= 0) {
246        if (matrix[row][col] == target)
247            return true;
248        else if (matrix[row][col] > target)
249            col--;
250        else
251            row++;
252    }
253
254    return false;
255}
256
257// =============================================================================
258// ν…ŒμŠ€νŠΈ
259// =============================================================================
260
261int main() {
262    cout << "============================================================" << endl;
263    cout << "탐색 μ•Œκ³ λ¦¬μ¦˜ 예제" << endl;
264    cout << "============================================================" << endl;
265
266    // 1. 이뢄 탐색
267    cout << "\n[1] 이뢄 탐색" << endl;
268    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
269    cout << "    λ°°μ—΄: [1,3,5,7,9,11,13,15]" << endl;
270    cout << "    7의 μœ„μΉ˜: " << binarySearch(arr, 7) << endl;
271    cout << "    6의 μœ„μΉ˜: " << binarySearch(arr, 6) << endl;
272
273    // 2. Lower/Upper Bound
274    cout << "\n[2] Lower/Upper Bound" << endl;
275    vector<int> arr2 = {1, 2, 2, 2, 3, 4, 5};
276    cout << "    λ°°μ—΄: [1,2,2,2,3,4,5]" << endl;
277    cout << "    lower_bound(2): " << lowerBound(arr2, 2) << endl;
278    cout << "    upper_bound(2): " << upperBound(arr2, 2) << endl;
279    cout << "    2의 개수: " << countOccurrences(arr2, 2) << endl;
280
281    // 3. νšŒμ „ μ •λ ¬ λ°°μ—΄
282    cout << "\n[3] νšŒμ „ μ •λ ¬ λ°°μ—΄" << endl;
283    vector<int> rotated = {4, 5, 6, 7, 0, 1, 2};
284    cout << "    λ°°μ—΄: [4,5,6,7,0,1,2]" << endl;
285    cout << "    0의 μœ„μΉ˜: " << searchRotated(rotated, 0) << endl;
286    cout << "    μ΅œμ†Ÿκ°’: " << findMin(rotated) << endl;
287
288    // 4. νŒŒλΌλ©”νŠΈλ¦­ μ„œμΉ˜
289    cout << "\n[4] νŒŒλΌλ©”νŠΈλ¦­ μ„œμΉ˜" << endl;
290    vector<int> trees = {20, 15, 10, 17};
291    cout << "    λ‚˜λ¬΄: [20,15,10,17], ν•„μš”λŸ‰: 7" << endl;
292    cout << "    μ΅œλŒ€ μ ˆλ‹¨ 높이: " << maxCuttingHeight(trees, 7) << endl;
293
294    vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
295    cout << "    물건: [1-10], 5일 배솑" << endl;
296    cout << "    μ΅œμ†Œ μš©λŸ‰: " << shipWithinDays(weights, 5) << endl;
297
298    // 5. μ‹€μˆ˜ 이뢄 탐색
299    cout << "\n[5] μ‹€μˆ˜ 이뢄 탐색" << endl;
300    cout << "    sqrt(2) = " << sqrtBinary(2) << endl;
301    cout << "    sqrt(10) = " << sqrtBinary(10) << endl;
302
303    // 6. 2D λ°°μ—΄ 탐색
304    cout << "\n[6] 2D λ°°μ—΄ 탐색" << endl;
305    vector<vector<int>> matrix = {
306        {1, 4, 7, 11},
307        {2, 5, 8, 12},
308        {3, 6, 9, 16},
309        {10, 13, 14, 17}
310    };
311    cout << "    5 μ°ΎκΈ°: " << (searchMatrix(matrix, 5) ? "있음" : "μ—†μŒ") << endl;
312    cout << "    15 μ°ΎκΈ°: " << (searchMatrix(matrix, 15) ? "있음" : "μ—†μŒ") << endl;
313
314    // 7. λ³΅μž‘λ„ μš”μ•½
315    cout << "\n[7] λ³΅μž‘λ„ μš”μ•½" << endl;
316    cout << "    | μ•Œκ³ λ¦¬μ¦˜          | μ‹œκ°„λ³΅μž‘λ„ |" << endl;
317    cout << "    |-------------------|------------|" << endl;
318    cout << "    | μ„ ν˜• 탐색         | O(n)       |" << endl;
319    cout << "    | 이뢄 탐색         | O(log n)   |" << endl;
320    cout << "    | νŒŒλΌλ©”νŠΈλ¦­ μ„œμΉ˜   | O(log M Γ— f(n)) |" << endl;
321    cout << "    | 2D ν–‰λ ¬ 탐색      | O(m + n)   |" << endl;
322
323    cout << "\n============================================================" << endl;
324
325    return 0;
326}