19_greedy.cpp

Download
cpp 430 lines 12.3 KB 
  1/*
  2 * ํƒ์š• ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Greedy Algorithm)
  3 * Activity Selection, Huffman, Interval Scheduling, Fractional Knapsack
  4 *
  5 * ๋งค ์ˆœ๊ฐ„ ์ตœ์„ ์˜ ์„ ํƒ์„ ํ•˜์—ฌ ์ตœ์ ํ•ด๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <algorithm>
 12#include <string>
 13#include <unordered_map>
 14
 15using namespace std;
 16
 17// =============================================================================
 18// 1. ํ™œ๋™ ์„ ํƒ ๋ฌธ์ œ
 19// =============================================================================
 20
 21struct Activity {
 22    int start, end, idx;
 23};
 24
 25vector<int> activitySelection(vector<Activity>& activities) {
 26    // ์ข…๋ฃŒ ์‹œ๊ฐ„ ๊ธฐ์ค€ ์ •๋ ฌ
 27    sort(activities.begin(), activities.end(),
 28         [](const Activity& a, const Activity& b) {
 29             return a.end < b.end;
 30         });
 31
 32    vector<int> selected;
 33    int lastEnd = 0;
 34
 35    for (const auto& act : activities) {
 36        if (act.start >= lastEnd) {
 37            selected.push_back(act.idx);
 38            lastEnd = act.end;
 39        }
 40    }
 41
 42    return selected;
 43}
 44
 45// =============================================================================
 46// 2. ํšŒ์˜์‹ค ๋ฐฐ์ • (์ตœ์†Œ ํšŒ์˜์‹ค ์ˆ˜)
 47// =============================================================================
 48
 49int minMeetingRooms(vector<pair<int, int>>& intervals) {
 50    vector<pair<int, int>> events;
 51
 52    for (const auto& [start, end] : intervals) {
 53        events.push_back({start, 1});   // ์‹œ์ž‘
 54        events.push_back({end, -1});    // ์ข…๋ฃŒ
 55    }
 56
 57    sort(events.begin(), events.end());
 58
 59    int rooms = 0, maxRooms = 0;
 60    for (const auto& [time, type] : events) {
 61        rooms += type;
 62        maxRooms = max(maxRooms, rooms);
 63    }
 64
 65    return maxRooms;
 66}
 67
 68// =============================================================================
 69// 3. ๋ถ„ํ•  ๊ฐ€๋Šฅ ๋ฐฐ๋‚ญ (Fractional Knapsack)
 70// =============================================================================
 71
 72struct Item {
 73    int weight, value;
 74    double ratio() const { return (double)value / weight; }
 75};
 76
 77double fractionalKnapsack(int W, vector<Item>& items) {
 78    // ๊ฐ€์น˜/๋ฌด๊ฒŒ ๋น„์œจ๋กœ ์ •๋ ฌ
 79    sort(items.begin(), items.end(),
 80         [](const Item& a, const Item& b) {
 81             return a.ratio() > b.ratio();
 82         });
 83
 84    double totalValue = 0;
 85    int remaining = W;
 86
 87    for (const auto& item : items) {
 88        if (remaining >= item.weight) {
 89            totalValue += item.value;
 90            remaining -= item.weight;
 91        } else {
 92            totalValue += item.ratio() * remaining;
 93            break;
 94        }
 95    }
 96
 97    return totalValue;
 98}
 99
100// =============================================================================
101// 4. ํ—ˆํ”„๋งŒ ์ฝ”๋”ฉ
102// =============================================================================
103
104struct HuffmanNode {
105    char ch;
106    int freq;
107    HuffmanNode *left, *right;
108
109    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
110};
111
112struct Compare {
113    bool operator()(HuffmanNode* a, HuffmanNode* b) {
114        return a->freq > b->freq;
115    }
116};
117
118void generateCodes(HuffmanNode* root, string code,
119                   unordered_map<char, string>& codes) {
120    if (!root) return;
121
122    if (!root->left && !root->right) {
123        codes[root->ch] = code.empty() ? "0" : code;
124        return;
125    }
126
127    generateCodes(root->left, code + "0", codes);
128    generateCodes(root->right, code + "1", codes);
129}
130
131unordered_map<char, string> huffmanCoding(const string& text) {
132    // ๋นˆ๋„ ๊ณ„์‚ฐ
133    unordered_map<char, int> freq;
134    for (char c : text) freq[c]++;
135
136    // ์šฐ์„ ์ˆœ์œ„ ํ (์ตœ์†Œ ํž™)
137    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
138    for (auto& [c, f] : freq) {
139        pq.push(new HuffmanNode(c, f));
140    }
141
142    // ํŠธ๋ฆฌ ๊ตฌ์ถ•
143    while (pq.size() > 1) {
144        HuffmanNode* left = pq.top(); pq.pop();
145        HuffmanNode* right = pq.top(); pq.pop();
146
147        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
148        parent->left = left;
149        parent->right = right;
150        pq.push(parent);
151    }
152
153    // ์ฝ”๋“œ ์ƒ์„ฑ
154    unordered_map<char, string> codes;
155    if (!pq.empty()) {
156        generateCodes(pq.top(), "", codes);
157    }
158
159    return codes;
160}
161
162// =============================================================================
163// 5. ์ž‘์—… ์Šค์ผ€์ค„๋ง (Job Scheduling with Deadlines)
164// =============================================================================
165
166struct Job {
167    int id, deadline, profit;
168};
169
170int jobScheduling(vector<Job>& jobs) {
171    // ์ด์ต ๊ธฐ์ค€ ๋‚ด๋ฆผ์ฐจ์ˆœ
172    sort(jobs.begin(), jobs.end(),
173         [](const Job& a, const Job& b) {
174             return a.profit > b.profit;
175         });
176
177    int maxDeadline = 0;
178    for (const auto& job : jobs) {
179        maxDeadline = max(maxDeadline, job.deadline);
180    }
181
182    vector<int> slots(maxDeadline + 1, -1);  // ๊ฐ ์‹œ๊ฐ„๋Œ€ ์‚ฌ์šฉ ์—ฌ๋ถ€
183    int totalProfit = 0;
184
185    for (const auto& job : jobs) {
186        // ๋งˆ๊ฐ ์ง์ „๋ถ€ํ„ฐ ๋นˆ ์Šฌ๋กฏ ์ฐพ๊ธฐ
187        for (int t = job.deadline; t >= 1; t--) {
188            if (slots[t] == -1) {
189                slots[t] = job.id;
190                totalProfit += job.profit;
191                break;
192            }
193        }
194    }
195
196    return totalProfit;
197}
198
199// =============================================================================
200// 6. ์ตœ์†Œ ๋™์ „ ๊ฑฐ์Šค๋ฆ„๋ˆ
201// =============================================================================
202
203int minCoins(vector<int>& coins, int amount) {
204    // ํฐ ๋™์ „๋ถ€ํ„ฐ ์‚ฌ์šฉ (ํƒ์š•์  ์ ‘๊ทผ - ํŠน์ • ํ™”ํ์—์„œ๋งŒ ์ตœ์ )
205    sort(coins.rbegin(), coins.rend());
206
207    int count = 0;
208    for (int coin : coins) {
209        count += amount / coin;
210        amount %= coin;
211    }
212
213    return amount == 0 ? count : -1;
214}
215
216// =============================================================================
217// 7. ๊ตฌ๊ฐ„ ์ปค๋ฒ„ ๋ฌธ์ œ
218// =============================================================================
219
220int intervalCover(vector<pair<int, int>>& intervals, int target) {
221    // ์‹œ์ž‘์  ๊ธฐ์ค€ ์ •๋ ฌ
222    sort(intervals.begin(), intervals.end());
223
224    int count = 0;
225    int current = 0;
226    int i = 0;
227    int n = intervals.size();
228
229    while (current < target) {
230        int maxEnd = current;
231
232        // ํ˜„์žฌ ์œ„์น˜๋ฅผ ํฌํ•จํ•˜๋Š” ๊ตฌ๊ฐ„ ์ค‘ ๊ฐ€์žฅ ๋ฉ€๋ฆฌ ๊ฐ€๋Š” ๊ฒƒ ์„ ํƒ
233        while (i < n && intervals[i].first <= current) {
234            maxEnd = max(maxEnd, intervals[i].second);
235            i++;
236        }
237
238        if (maxEnd == current) {
239            return -1;  // ์ปค๋ฒ„ ๋ถˆ๊ฐ€
240        }
241
242        current = maxEnd;
243        count++;
244    }
245
246    return count;
247}
248
249// =============================================================================
250// 8. ์ ํ”„ ๊ฒŒ์ž„
251// =============================================================================
252
253bool canJump(const vector<int>& nums) {
254    int maxReach = 0;
255
256    for (int i = 0; i < (int)nums.size(); i++) {
257        if (i > maxReach) return false;
258        maxReach = max(maxReach, i + nums[i]);
259    }
260
261    return true;
262}
263
264int minJumps(const vector<int>& nums) {
265    int n = nums.size();
266    if (n <= 1) return 0;
267
268    int jumps = 0;
269    int currentEnd = 0;
270    int farthest = 0;
271
272    for (int i = 0; i < n - 1; i++) {
273        farthest = max(farthest, i + nums[i]);
274
275        if (i == currentEnd) {
276            jumps++;
277            currentEnd = farthest;
278
279            if (currentEnd >= n - 1) break;
280        }
281    }
282
283    return jumps;
284}
285
286// =============================================================================
287// 9. ์ฃผ์œ ์†Œ (Gas Station)
288// =============================================================================
289
290int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
291    int n = gas.size();
292    int totalTank = 0;
293    int currTank = 0;
294    int startStation = 0;
295
296    for (int i = 0; i < n; i++) {
297        int diff = gas[i] - cost[i];
298        totalTank += diff;
299        currTank += diff;
300
301        if (currTank < 0) {
302            startStation = i + 1;
303            currTank = 0;
304        }
305    }
306
307    return totalTank >= 0 ? startStation : -1;
308}
309
310// =============================================================================
311// 10. ๋ฌธ์ž์—ด ๋ถ„ํ• 
312// =============================================================================
313
314vector<int> partitionLabels(const string& s) {
315    // ๊ฐ ๋ฌธ์ž์˜ ๋งˆ์ง€๋ง‰ ๋“ฑ์žฅ ์œ„์น˜
316    vector<int> last(26, 0);
317    for (int i = 0; i < (int)s.length(); i++) {
318        last[s[i] - 'a'] = i;
319    }
320
321    vector<int> result;
322    int start = 0, end = 0;
323
324    for (int i = 0; i < (int)s.length(); i++) {
325        end = max(end, last[s[i] - 'a']);
326
327        if (i == end) {
328            result.push_back(end - start + 1);
329            start = i + 1;
330        }
331    }
332
333    return result;
334}
335
336// =============================================================================
337// ํ…Œ์ŠคํŠธ
338// =============================================================================
339
340void printVector(const vector<int>& v) {
341    cout << "[";
342    for (size_t i = 0; i < v.size(); i++) {
343        cout << v[i];
344        if (i < v.size() - 1) cout << ", ";
345    }
346    cout << "]";
347}
348
349int main() {
350    cout << "============================================================" << endl;
351    cout << "ํƒ์š• ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์˜ˆ์ œ" << endl;
352    cout << "============================================================" << endl;
353
354    // 1. ํ™œ๋™ ์„ ํƒ
355    cout << "\n[1] ํ™œ๋™ ์„ ํƒ" << endl;
356    vector<Activity> activities = {
357        {1, 4, 0}, {3, 5, 1}, {0, 6, 2}, {5, 7, 3},
358        {3, 9, 4}, {5, 9, 5}, {6, 10, 6}, {8, 11, 7}
359    };
360    auto selected = activitySelection(activities);
361    cout << "    ์„ ํƒ๋œ ํ™œ๋™: ";
362    printVector(selected);
363    cout << endl;
364
365    // 2. ์ตœ์†Œ ํšŒ์˜์‹ค
366    cout << "\n[2] ์ตœ์†Œ ํšŒ์˜์‹ค" << endl;
367    vector<pair<int, int>> meetings = {{0, 30}, {5, 10}, {15, 20}};
368    cout << "    ํšŒ์˜: [(0,30), (5,10), (15,20)]" << endl;
369    cout << "    ์ตœ์†Œ ํšŒ์˜์‹ค: " << minMeetingRooms(meetings) << endl;
370
371    // 3. ๋ถ„ํ•  ๊ฐ€๋Šฅ ๋ฐฐ๋‚ญ
372    cout << "\n[3] ๋ถ„ํ•  ๊ฐ€๋Šฅ ๋ฐฐ๋‚ญ" << endl;
373    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
374    cout << "    ๋ฌผ๊ฑด: (๋ฌด๊ฒŒ, ๊ฐ€์น˜) = (10,60), (20,100), (30,120)" << endl;
375    cout << "    ์šฉ๋Ÿ‰ 50, ์ตœ๋Œ€ ๊ฐ€์น˜: " << fractionalKnapsack(50, items) << endl;
376
377    // 4. ํ—ˆํ”„๋งŒ ์ฝ”๋”ฉ
378    cout << "\n[4] ํ—ˆํ”„๋งŒ ์ฝ”๋”ฉ" << endl;
379    string text = "aabbbcccc";
380    auto codes = huffmanCoding(text);
381    cout << "    ํ…์ŠคํŠธ: \"" << text << "\"" << endl;
382    cout << "    ์ฝ”๋“œ:" << endl;
383    for (auto& [ch, code] : codes) {
384        cout << "      '" << ch << "': " << code << endl;
385    }
386
387    // 5. ์ž‘์—… ์Šค์ผ€์ค„๋ง
388    cout << "\n[5] ์ž‘์—… ์Šค์ผ€์ค„๋ง" << endl;
389    vector<Job> jobs = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
390    cout << "    ์ž‘์—…: (id, ๋งˆ๊ฐ, ์ด์ต)" << endl;
391    cout << "    ์ตœ๋Œ€ ์ด์ต: " << jobScheduling(jobs) << endl;
392
393    // 6. ์ ํ”„ ๊ฒŒ์ž„
394    cout << "\n[6] ์ ํ”„ ๊ฒŒ์ž„" << endl;
395    vector<int> nums1 = {2, 3, 1, 1, 4};
396    vector<int> nums2 = {3, 2, 1, 0, 4};
397    cout << "    [2,3,1,1,4] ๋„๋‹ฌ ๊ฐ€๋Šฅ: " << (canJump(nums1) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
398    cout << "    [2,3,1,1,4] ์ตœ์†Œ ์ ํ”„: " << minJumps(nums1) << endl;
399    cout << "    [3,2,1,0,4] ๋„๋‹ฌ ๊ฐ€๋Šฅ: " << (canJump(nums2) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
400
401    // 7. ์ฃผ์œ ์†Œ
402    cout << "\n[7] ์ฃผ์œ ์†Œ" << endl;
403    vector<int> gas = {1, 2, 3, 4, 5};
404    vector<int> cost = {3, 4, 5, 1, 2};
405    cout << "    gas: [1,2,3,4,5], cost: [3,4,5,1,2]" << endl;
406    cout << "    ์‹œ์ž‘ ์œ„์น˜: " << canCompleteCircuit(gas, cost) << endl;
407
408    // 8. ๋ฌธ์ž์—ด ๋ถ„ํ• 
409    cout << "\n[8] ๋ฌธ์ž์—ด ๋ถ„ํ• " << endl;
410    string s = "ababcbacadefegdehijhklij";
411    auto parts = partitionLabels(s);
412    cout << "    ๋ฌธ์ž์—ด: \"" << s << "\"" << endl;
413    cout << "    ๋ถ„ํ•  ํฌ๊ธฐ: ";
414    printVector(parts);
415    cout << endl;
416
417    // 9. ํƒ์š• vs DP
418    cout << "\n[9] ํƒ์š• vs DP" << endl;
419    cout << "    | ๊ธฐ์ค€           | ํƒ์š•          | DP              |" << endl;
420    cout << "    |----------------|---------------|-----------------|" << endl;
421    cout << "    | ์ ‘๊ทผ ๋ฐฉ์‹      | ์ง€์—ญ ์ตœ์      | ์ „์—ญ ์ตœ์        |" << endl;
422    cout << "    | ๊ฒฐ์ • ๋ณ€๊ฒฝ      | X             | O               |" << endl;
423    cout << "    | ์‹œ๊ฐ„ ๋ณต์žก๋„    | ๋ณดํ†ต ๋‚ฎ์Œ     | ๋ณดํ†ต ๋†’์Œ       |" << endl;
424    cout << "    | ์ตœ์  ๋ณด์žฅ      | ํŠน์ • ๋ฌธ์ œ๋งŒ   | ํ•ญ์ƒ ๋ณด์žฅ       |" << endl;
425
426    cout << "\n============================================================" << endl;
427
428    return 0;
429}