07_divide_conquer.cpp

Download
cpp 291 lines 8.8 KB 
  1/*
  2 * ๋ถ„ํ•  ์ •๋ณต (Divide and Conquer)
  3 * Merge Sort, Quick Sort, Binary Search, Power
  4 *
  5 * ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋ˆ„์–ด ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11#include <cmath>
 12#include <climits>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ
 18// =============================================================================
 19
 20long long power(long long base, long long exp, long long mod = LLONG_MAX) {
 21    long long result = 1;
 22    base %= mod;
 23
 24    while (exp > 0) {
 25        if (exp & 1) {
 26            result = (result * base) % mod;
 27        }
 28        base = (base * base) % mod;
 29        exp >>= 1;
 30    }
 31
 32    return result;
 33}
 34
 35// =============================================================================
 36// 2. ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ
 37// =============================================================================
 38
 39using Matrix = vector<vector<long long>>;
 40
 41Matrix matrixMultiply(const Matrix& A, const Matrix& B, long long mod) {
 42    int n = A.size();
 43    Matrix C(n, vector<long long>(n, 0));
 44
 45    for (int i = 0; i < n; i++) {
 46        for (int j = 0; j < n; j++) {
 47            for (int k = 0; k < n; k++) {
 48                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
 49            }
 50        }
 51    }
 52
 53    return C;
 54}
 55
 56Matrix matrixPower(Matrix A, long long exp, long long mod) {
 57    int n = A.size();
 58    Matrix result(n, vector<long long>(n, 0));
 59
 60    // ๋‹จ์œ„ ํ–‰๋ ฌ
 61    for (int i = 0; i < n; i++) result[i][i] = 1;
 62
 63    while (exp > 0) {
 64        if (exp & 1) {
 65            result = matrixMultiply(result, A, mod);
 66        }
 67        A = matrixMultiply(A, A, mod);
 68        exp >>= 1;
 69    }
 70
 71    return result;
 72}
 73
 74// ํ”ผ๋ณด๋‚˜์น˜ (ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ)
 75long long fibonacciMatrix(long long n, long long mod = 1e9 + 7) {
 76    if (n <= 1) return n;
 77
 78    Matrix M = {{1, 1}, {1, 0}};
 79    Matrix result = matrixPower(M, n - 1, mod);
 80    return result[0][0];
 81}
 82
 83// =============================================================================
 84// 3. ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ (Closest Pair)
 85// =============================================================================
 86
 87struct Point {
 88    double x, y;
 89};
 90
 91double dist(const Point& p1, const Point& p2) {
 92    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
 93}
 94
 95double bruteForce(vector<Point>& points, int left, int right) {
 96    double minDist = DBL_MAX;
 97    for (int i = left; i < right; i++) {
 98        for (int j = i + 1; j <= right; j++) {
 99            minDist = min(minDist, dist(points[i], points[j]));
100        }
101    }
102    return minDist;
103}
104
105double stripClosest(vector<Point>& strip, double d) {
106    double minDist = d;
107    sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) {
108        return a.y < b.y;
109    });
110
111    for (size_t i = 0; i < strip.size(); i++) {
112        for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist; j++) {
113            minDist = min(minDist, dist(strip[i], strip[j]));
114        }
115    }
116
117    return minDist;
118}
119
120double closestPairHelper(vector<Point>& points, int left, int right) {
121    if (right - left <= 3) {
122        return bruteForce(points, left, right);
123    }
124
125    int mid = (left + right) / 2;
126    Point midPoint = points[mid];
127
128    double dl = closestPairHelper(points, left, mid);
129    double dr = closestPairHelper(points, mid + 1, right);
130    double d = min(dl, dr);
131
132    vector<Point> strip;
133    for (int i = left; i <= right; i++) {
134        if (abs(points[i].x - midPoint.x) < d) {
135            strip.push_back(points[i]);
136        }
137    }
138
139    return min(d, stripClosest(strip, d));
140}
141
142double closestPair(vector<Point>& points) {
143    sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
144        return a.x < b.x;
145    });
146    return closestPairHelper(points, 0, points.size() - 1);
147}
148
149// =============================================================================
150// 4. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ (Inversion Count)
151// =============================================================================
152
153long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
154    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
155    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
156
157    size_t i = 0, j = 0;
158    int k = left;
159    long long inversions = 0;
160
161    while (i < L.size() && j < R.size()) {
162        if (L[i] <= R[j]) {
163            arr[k++] = L[i++];
164        } else {
165            arr[k++] = R[j++];
166            inversions += (L.size() - i);  // ์—ญ์ˆœ ์Œ
167        }
168    }
169
170    while (i < L.size()) arr[k++] = L[i++];
171    while (j < R.size()) arr[k++] = R[j++];
172
173    return inversions;
174}
175
176long long countInversions(vector<int>& arr, int left, int right) {
177    long long inversions = 0;
178    if (left < right) {
179        int mid = (left + right) / 2;
180        inversions += countInversions(arr, left, mid);
181        inversions += countInversions(arr, mid + 1, right);
182        inversions += mergeAndCount(arr, left, mid, right);
183    }
184    return inversions;
185}
186
187// =============================================================================
188// 5. ์นด๋ผ์ธ ๋ฐ” ๊ณฑ์…ˆ (Karatsuba Multiplication)
189// =============================================================================
190
191string addStrings(const string& a, const string& b) {
192    string result;
193    int carry = 0;
194    int i = a.size() - 1, j = b.size() - 1;
195
196    while (i >= 0 || j >= 0 || carry) {
197        int sum = carry;
198        if (i >= 0) sum += a[i--] - '0';
199        if (j >= 0) sum += b[j--] - '0';
200        result = char(sum % 10 + '0') + result;
201        carry = sum / 10;
202    }
203
204    return result.empty() ? "0" : result;
205}
206
207// =============================================================================
208// 6. ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (๋ถ„ํ• ์ •๋ณต)
209// =============================================================================
210
211int maxCrossingSum(const vector<int>& arr, int left, int mid, int right) {
212    int leftSum = INT_MIN;
213    int sum = 0;
214    for (int i = mid; i >= left; i--) {
215        sum += arr[i];
216        leftSum = max(leftSum, sum);
217    }
218
219    int rightSum = INT_MIN;
220    sum = 0;
221    for (int i = mid + 1; i <= right; i++) {
222        sum += arr[i];
223        rightSum = max(rightSum, sum);
224    }
225
226    return leftSum + rightSum;
227}
228
229int maxSubArrayDC(const vector<int>& arr, int left, int right) {
230    if (left == right) return arr[left];
231
232    int mid = (left + right) / 2;
233    return max({
234        maxSubArrayDC(arr, left, mid),
235        maxSubArrayDC(arr, mid + 1, right),
236        maxCrossingSum(arr, left, mid, right)
237    });
238}
239
240// =============================================================================
241// ํ…Œ์ŠคํŠธ
242// =============================================================================
243
244int main() {
245    cout << "============================================================" << endl;
246    cout << "๋ถ„ํ•  ์ •๋ณต ์˜ˆ์ œ" << endl;
247    cout << "============================================================" << endl;
248
249    // 1. ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ
250    cout << "\n[1] ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ" << endl;
251    cout << "    2^10 = " << power(2, 10) << endl;
252    cout << "    3^20 mod 1000 = " << power(3, 20, 1000) << endl;
253
254    // 2. ํ”ผ๋ณด๋‚˜์น˜ (ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ)
255    cout << "\n[2] ํ”ผ๋ณด๋‚˜์น˜ (ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ)" << endl;
256    cout << "    F(10) = " << fibonacciMatrix(10) << endl;
257    cout << "    F(50) mod 10^9+7 = " << fibonacciMatrix(50) << endl;
258
259    // 3. ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ
260    cout << "\n[3] ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ" << endl;
261    vector<Point> points = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
262    cout << "    ์  6๊ฐœ" << endl;
263    cout << "    ์ตœ์†Œ ๊ฑฐ๋ฆฌ: " << closestPair(points) << endl;
264
265    // 4. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜
266    cout << "\n[4] ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜" << endl;
267    vector<int> inv = {8, 4, 2, 1};
268    cout << "    ๋ฐฐ์—ด: [8, 4, 2, 1]" << endl;
269    cout << "    ์—ญ์ˆœ ์Œ: " << countInversions(inv, 0, inv.size() - 1) << endl;
270
271    // 5. ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ
272    cout << "\n[5] ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (๋ถ„ํ• ์ •๋ณต)" << endl;
273    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
274    cout << "    ๋ฐฐ์—ด: [-2,1,-3,4,-1,2,1,-5,4]" << endl;
275    cout << "    ์ตœ๋Œ€ ํ•ฉ: " << maxSubArrayDC(arr, 0, arr.size() - 1) << endl;
276
277    // 6. ๋ณต์žก๋„ ์š”์•ฝ
278    cout << "\n[6] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
279    cout << "    | ์•Œ๊ณ ๋ฆฌ์ฆ˜           | ์‹œ๊ฐ„๋ณต์žก๋„     |" << endl;
280    cout << "    |--------------------|----------------|" << endl;
281    cout << "    | ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ      | O(log n)       |" << endl;
282    cout << "    | ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ      | O(kยณ log n)    |" << endl;
283    cout << "    | ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ  | O(n log n)     |" << endl;
284    cout << "    | ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜       | O(n log n)     |" << endl;
285    cout << "    | ๋ณ‘ํ•ฉ/ํ€ต ์ •๋ ฌ       | O(n log n)     |" << endl;
286
287    cout << "\n============================================================" << endl;
288
289    return 0;
290}