29_practice.cpp

Download
cpp 395 lines 11.7 KB 
  1/*
  2 * ์‹ค์ „ ๋ฌธ์ œ ํ’€์ด (Practice Problems)
  3 * ์ข…ํ•ฉ ๋ฌธ์ œ (๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์กฐํ•ฉ)
  4 *
  5 * ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ ์ž์ฃผ ๋‚˜์˜ค๋Š” ์œ ํ˜•๋“ค์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <string>
 11#include <algorithm>
 12#include <queue>
 13#include <unordered_map>
 14#include <unordered_set>
 15#include <numeric>
 16#include <climits>
 17
 18using namespace std;
 19
 20// =============================================================================
 21// 1. ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (ํˆฌ ํฌ์ธํ„ฐ)
 22// =============================================================================
 23
 24// ํ•ฉ์ด target ์ด์ƒ์ธ ์ตœ์†Œ ๊ธธ์ด ๋ถ€๋ถ„ ๋ฐฐ์—ด
 25int minSubarrayLen(int target, const vector<int>& nums) {
 26    int n = nums.size();
 27    int left = 0, sum = 0;
 28    int minLen = INT_MAX;
 29
 30    for (int right = 0; right < n; right++) {
 31        sum += nums[right];
 32
 33        while (sum >= target) {
 34            minLen = min(minLen, right - left + 1);
 35            sum -= nums[left++];
 36        }
 37    }
 38
 39    return minLen == INT_MAX ? 0 : minLen;
 40}
 41
 42// =============================================================================
 43// 2. ์ž‘์—… ์Šค์ผ€์ค„๋ง (Greedy)
 44// =============================================================================
 45
 46struct Job {
 47    int deadline, profit;
 48};
 49
 50int jobScheduling(vector<Job>& jobs) {
 51    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b) {
 52        return a.profit > b.profit;
 53    });
 54
 55    int maxDeadline = 0;
 56    for (const auto& job : jobs) {
 57        maxDeadline = max(maxDeadline, job.deadline);
 58    }
 59
 60    vector<bool> slots(maxDeadline + 1, false);
 61    int totalProfit = 0;
 62
 63    for (const auto& job : jobs) {
 64        for (int t = job.deadline; t >= 1; t--) {
 65            if (!slots[t]) {
 66                slots[t] = true;
 67                totalProfit += job.profit;
 68                break;
 69            }
 70        }
 71    }
 72
 73    return totalProfit;
 74}
 75
 76// =============================================================================
 77// 3. ์ตœ์†Œ ํšŒ์˜์‹ค ์ˆ˜ (์ด๋ฒคํŠธ ์ •๋ ฌ)
 78// =============================================================================
 79
 80int minMeetingRooms(vector<pair<int, int>>& intervals) {
 81    vector<pair<int, int>> events;
 82
 83    for (const auto& [start, end] : intervals) {
 84        events.push_back({start, 1});
 85        events.push_back({end, -1});
 86    }
 87
 88    sort(events.begin(), events.end());
 89
 90    int rooms = 0, maxRooms = 0;
 91    for (const auto& [time, type] : events) {
 92        rooms += type;
 93        maxRooms = max(maxRooms, rooms);
 94    }
 95
 96    return maxRooms;
 97}
 98
 99// =============================================================================
100// 4. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜ (DP)
101// =============================================================================
102
103int minPalindromeInsertions(const string& s) {
104    int n = s.length();
105    vector<vector<int>> dp(n, vector<int>(n, 0));
106
107    for (int len = 2; len <= n; len++) {
108        for (int i = 0; i + len - 1 < n; i++) {
109            int j = i + len - 1;
110            if (s[i] == s[j]) {
111                dp[i][j] = dp[i + 1][j - 1];
112            } else {
113                dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);
114            }
115        }
116    }
117
118    return dp[0][n - 1];
119}
120
121// =============================================================================
122// 5. ์„ฌ์˜ ๊ฐœ์ˆ˜ (DFS/BFS)
123// =============================================================================
124
125void dfsIsland(vector<vector<int>>& grid, int i, int j,
126               vector<vector<bool>>& visited) {
127    int rows = grid.size(), cols = grid[0].size();
128    if (i < 0 || i >= rows || j < 0 || j >= cols) return;
129    if (visited[i][j] || grid[i][j] == 0) return;
130
131    visited[i][j] = true;
132    int dx[] = {-1, 1, 0, 0};
133    int dy[] = {0, 0, -1, 1};
134
135    for (int d = 0; d < 4; d++) {
136        dfsIsland(grid, i + dx[d], j + dy[d], visited);
137    }
138}
139
140int numIslands(vector<vector<int>>& grid) {
141    if (grid.empty()) return 0;
142
143    int rows = grid.size(), cols = grid[0].size();
144    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
145    int count = 0;
146
147    for (int i = 0; i < rows; i++) {
148        for (int j = 0; j < cols; j++) {
149            if (grid[i][j] == 1 && !visited[i][j]) {
150                dfsIsland(grid, i, j, visited);
151                count++;
152            }
153        }
154    }
155
156    return count;
157}
158
159// =============================================================================
160// 6. Union-Find ์‘์šฉ
161// =============================================================================
162
163class UnionFind {
164private:
165    vector<int> parent, rank_;
166
167public:
168    UnionFind(int n) : parent(n), rank_(n, 0) {
169        iota(parent.begin(), parent.end(), 0);
170    }
171
172    int find(int x) {
173        if (parent[x] != x) {
174            parent[x] = find(parent[x]);
175        }
176        return parent[x];
177    }
178
179    bool unite(int x, int y) {
180        int px = find(x), py = find(y);
181        if (px == py) return false;
182
183        if (rank_[px] < rank_[py]) swap(px, py);
184        parent[py] = px;
185        if (rank_[px] == rank_[py]) rank_[px]++;
186
187        return true;
188    }
189};
190
191// ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ
192vector<int> findRedundantConnection(vector<vector<int>>& edges) {
193    int n = edges.size();
194    UnionFind uf(n + 1);
195
196    for (const auto& edge : edges) {
197        if (!uf.unite(edge[0], edge[1])) {
198            return edge;
199        }
200    }
201
202    return {};
203}
204
205// =============================================================================
206// 7. LIS (Longest Increasing Subsequence)
207// =============================================================================
208
209int lengthOfLIS(const vector<int>& nums) {
210    vector<int> tails;
211
212    for (int num : nums) {
213        auto it = lower_bound(tails.begin(), tails.end(), num);
214        if (it == tails.end()) {
215            tails.push_back(num);
216        } else {
217            *it = num;
218        }
219    }
220
221    return tails.size();
222}
223
224// =============================================================================
225// 8. ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ (ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜)
226// =============================================================================
227
228bool canShip(const vector<int>& weights, int capacity, int days) {
229    int current = 0;
230    int dayCount = 1;
231
232    for (int w : weights) {
233        if (w > capacity) return false;
234        if (current + w > capacity) {
235            dayCount++;
236            current = w;
237        } else {
238            current += w;
239        }
240    }
241
242    return dayCount <= days;
243}
244
245int shipWithinDays(const vector<int>& weights, int days) {
246    int lo = *max_element(weights.begin(), weights.end());
247    int hi = accumulate(weights.begin(), weights.end(), 0);
248
249    while (lo < hi) {
250        int mid = (lo + hi) / 2;
251        if (canShip(weights, mid, days)) {
252            hi = mid;
253        } else {
254            lo = mid + 1;
255        }
256    }
257
258    return lo;
259}
260
261// =============================================================================
262// 9. ๋‹จ์–ด ์‚ฌ๋‹ค๋ฆฌ (BFS)
263// =============================================================================
264
265int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
266    unordered_set<string> wordSet(wordList.begin(), wordList.end());
267    if (wordSet.find(endWord) == wordSet.end()) return 0;
268
269    queue<pair<string, int>> q;
270    q.push({beginWord, 1});
271
272    while (!q.empty()) {
273        auto [word, dist] = q.front();
274        q.pop();
275
276        if (word == endWord) return dist;
277
278        for (int i = 0; i < (int)word.length(); i++) {
279            char original = word[i];
280            for (char c = 'a'; c <= 'z'; c++) {
281                word[i] = c;
282                if (wordSet.find(word) != wordSet.end()) {
283                    q.push({word, dist + 1});
284                    wordSet.erase(word);
285                }
286            }
287            word[i] = original;
288        }
289    }
290
291    return 0;
292}
293
294// =============================================================================
295// 10. ๋ฌธ์ œ ํ’€์ด ์ „๋žต
296// =============================================================================
297
298void printStrategy() {
299    cout << "\n[10] ๋ฌธ์ œ ํ’€์ด ์ „๋žต" << endl;
300    cout << "    1. ๋ฌธ์ œ ์ดํ•ด: ์ž…๋ ฅ/์ถœ๋ ฅ, ์ œ์•ฝ ์กฐ๊ฑด ํ™•์ธ" << endl;
301    cout << "    2. ์˜ˆ์ œ ๋ถ„์„: ์†์œผ๋กœ ํ’€์–ด๋ณด๊ธฐ" << endl;
302    cout << "    3. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ ํƒ:" << endl;
303    cout << "       - N <= 20: ์™„์ „ ํƒ์ƒ‰, ๋น„ํŠธ๋งˆ์Šคํฌ" << endl;
304    cout << "       - N <= 10^3: O(N^2) DP, ๋ธŒ๋ฃจํŠธํฌ์Šค" << endl;
305    cout << "       - N <= 10^5: O(N log N) ์ •๋ ฌ, ์ด๋ถ„ํƒ์ƒ‰" << endl;
306    cout << "       - N <= 10^7: O(N) ํˆฌ ํฌ์ธํ„ฐ, ํ•ด์‹œ" << endl;
307    cout << "    4. ๊ตฌํ˜„ ๋ฐ ํ…Œ์ŠคํŠธ" << endl;
308    cout << "    5. ์—ฃ์ง€ ์ผ€์ด์Šค ํ™•์ธ" << endl;
309}
310
311// =============================================================================
312// ํ…Œ์ŠคํŠธ
313// =============================================================================
314
315void printVector(const vector<int>& v) {
316    cout << "[";
317    for (size_t i = 0; i < v.size(); i++) {
318        cout << v[i];
319        if (i < v.size() - 1) cout << ", ";
320    }
321    cout << "]";
322}
323
324int main() {
325    cout << "============================================================" << endl;
326    cout << "์‹ค์ „ ๋ฌธ์ œ ํ’€์ด ์˜ˆ์ œ" << endl;
327    cout << "============================================================" << endl;
328
329    // 1. ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ
330    cout << "\n[1] ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (ํˆฌ ํฌ์ธํ„ฐ)" << endl;
331    vector<int> arr1 = {2, 3, 1, 2, 4, 3};
332    cout << "    ๋ฐฐ์—ด: [2, 3, 1, 2, 4, 3], target = 7" << endl;
333    cout << "    ์ตœ์†Œ ๊ธธ์ด: " << minSubarrayLen(7, arr1) << endl;
334
335    // 2. ์ž‘์—… ์Šค์ผ€์ค„๋ง
336    cout << "\n[2] ์ž‘์—… ์Šค์ผ€์ค„๋ง (Greedy)" << endl;
337    vector<Job> jobs = {{4, 20}, {1, 10}, {1, 40}, {1, 30}};
338    cout << "    ์ž‘์—…: {๋งˆ๊ฐ:4,์ด์ต:20}, {1,10}, {1,40}, {1,30}" << endl;
339    cout << "    ์ตœ๋Œ€ ์ด์ต: " << jobScheduling(jobs) << endl;
340
341    // 3. ์ตœ์†Œ ํšŒ์˜์‹ค
342    cout << "\n[3] ์ตœ์†Œ ํšŒ์˜์‹ค ์ˆ˜" << endl;
343    vector<pair<int, int>> meetings = {{0, 30}, {5, 10}, {15, 20}};
344    cout << "    ํšŒ์˜: [0-30], [5-10], [15-20]" << endl;
345    cout << "    ์ตœ์†Œ ํšŒ์˜์‹ค: " << minMeetingRooms(meetings) << endl;
346
347    // 4. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜
348    cout << "\n[4] ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜" << endl;
349    cout << "    ๋ฌธ์ž์—ด: \"abcde\"" << endl;
350    cout << "    ์ตœ์†Œ ์‚ฝ์ž…: " << minPalindromeInsertions("abcde") << endl;
351
352    // 5. ์„ฌ์˜ ๊ฐœ์ˆ˜
353    cout << "\n[5] ์„ฌ์˜ ๊ฐœ์ˆ˜" << endl;
354    vector<vector<int>> grid = {
355        {1, 1, 0, 0},
356        {1, 0, 0, 0},
357        {0, 0, 1, 0},
358        {0, 0, 0, 1}
359    };
360    cout << "    ๊ทธ๋ฆฌ๋“œ: 4x4" << endl;
361    cout << "    ์„ฌ์˜ ๊ฐœ์ˆ˜: " << numIslands(grid) << endl;
362
363    // 6. ์ค‘๋ณต ์—ฐ๊ฒฐ
364    cout << "\n[6] ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ (Union-Find)" << endl;
365    vector<vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}};
366    auto redundant = findRedundantConnection(edges);
367    cout << "    ๊ฐ„์„ : (1,2), (1,3), (2,3)" << endl;
368    cout << "    ์ค‘๋ณต: (" << redundant[0] << ", " << redundant[1] << ")" << endl;
369
370    // 7. LIS
371    cout << "\n[7] ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„์ˆ˜์—ด (LIS)" << endl;
372    vector<int> arr2 = {10, 9, 2, 5, 3, 7, 101, 18};
373    cout << "    ๋ฐฐ์—ด: [10, 9, 2, 5, 3, 7, 101, 18]" << endl;
374    cout << "    LIS ๊ธธ์ด: " << lengthOfLIS(arr2) << endl;
375
376    // 8. ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ
377    cout << "\n[8] ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ (๋ฐฐ์†ก)" << endl;
378    vector<int> weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
379    cout << "    ๋ฌผ๊ฑด ๋ฌด๊ฒŒ: [1-10]" << endl;
380    cout << "    5์ผ ๋‚ด ๋ฐฐ์†ก ์ตœ์†Œ ์šฉ๋Ÿ‰: " << shipWithinDays(weights, 5) << endl;
381
382    // 9. ๋‹จ์–ด ์‚ฌ๋‹ค๋ฆฌ
383    cout << "\n[9] ๋‹จ์–ด ์‚ฌ๋‹ค๋ฆฌ (BFS)" << endl;
384    vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
385    cout << "    hit -> cog" << endl;
386    cout << "    ์ตœ์†Œ ๋ณ€ํ™˜: " << ladderLength("hit", "cog", wordList) << endl;
387
388    // 10. ๋ฌธ์ œ ํ’€์ด ์ „๋žต
389    printStrategy();
390
391    cout << "\n============================================================" << endl;
392
393    return 0;
394}