20_bitmask_dp.cpp

Download
cpp 390 lines 11.9 KB 
  1/*
  2 * ๋น„ํŠธ๋งˆ์Šคํฌ DP (Bitmask DP)
  3 * TSP, Subset Enumeration, Assignment Problem
  4 *
  5 * ์ง‘ํ•ฉ์˜ ์ƒํƒœ๋ฅผ ๋น„ํŠธ๋กœ ํ‘œํ˜„ํ•˜์—ฌ DP๋ฅผ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <algorithm>
 11#include <climits>
 12#include <bitset>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. ๋น„ํŠธ ์—ฐ์‚ฐ ๊ธฐ์ดˆ
 18// =============================================================================
 19
 20void bitOperations() {
 21    int n = 4;  // ์ง‘ํ•ฉ ํฌ๊ธฐ
 22    int fullSet = (1 << n) - 1;  // {0, 1, 2, 3}
 23
 24    cout << "[1] ๋น„ํŠธ ์—ฐ์‚ฐ ๊ธฐ์ดˆ" << endl;
 25
 26    // ์›์†Œ i ํฌํ•จ ์—ฌ๋ถ€
 27    int set = 0b1010;  // {1, 3}
 28    cout << "    ์ง‘ํ•ฉ 1010 (10์ง„์ˆ˜: " << set << ")" << endl;
 29    cout << "    ์›์†Œ 1 ํฌํ•จ: " << ((set & (1 << 1)) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
 30    cout << "    ์›์†Œ 2 ํฌํ•จ: " << ((set & (1 << 2)) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
 31
 32    // ์›์†Œ ์ถ”๊ฐ€/์ œ๊ฑฐ
 33    set |= (1 << 2);   // 2 ์ถ”๊ฐ€
 34    cout << "    2 ์ถ”๊ฐ€ ํ›„: " << bitset<4>(set) << endl;
 35    set &= ~(1 << 1);  // 1 ์ œ๊ฑฐ
 36    cout << "    1 ์ œ๊ฑฐ ํ›„: " << bitset<4>(set) << endl;
 37
 38    // ์›์†Œ ํ† ๊ธ€
 39    set ^= (1 << 3);  // 3 ํ† ๊ธ€
 40    cout << "    3 ํ† ๊ธ€ ํ›„: " << bitset<4>(set) << endl;
 41
 42    // ์ง‘ํ•ฉ ํฌ๊ธฐ (1์˜ ๊ฐœ์ˆ˜)
 43    cout << "    ์ง‘ํ•ฉ ํฌ๊ธฐ: " << __builtin_popcount(set) << endl;
 44
 45    // ์ตœํ•˜์œ„ ๋น„ํŠธ
 46    cout << "    ์ตœํ•˜์œ„ 1๋น„ํŠธ: " << (set & -set) << endl;
 47}
 48
 49// =============================================================================
 50// 2. ๋ถ€๋ถ„์ง‘ํ•ฉ ์ˆœํšŒ
 51// =============================================================================
 52
 53void enumerateSubsets(int n) {
 54    cout << "\n[2] ๋ถ€๋ถ„์ง‘ํ•ฉ ์ˆœํšŒ" << endl;
 55    cout << "    n = " << n << "์ธ ์ง‘ํ•ฉ์˜ ๋ชจ๋“  ๋ถ€๋ถ„์ง‘ํ•ฉ:" << endl;
 56
 57    // ๋ชจ๋“  ๋ถ€๋ถ„์ง‘ํ•ฉ
 58    cout << "    ์ „์ฒด: ";
 59    for (int mask = 0; mask < (1 << n); mask++) {
 60        cout << bitset<3>(mask) << " ";
 61    }
 62    cout << endl;
 63
 64    // ํŠน์ • ์ง‘ํ•ฉ์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ
 65    int set = 0b101;  // {0, 2}
 66    cout << "    " << bitset<3>(set) << "์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ: ";
 67    for (int sub = set; ; sub = (sub - 1) & set) {
 68        cout << bitset<3>(sub) << " ";
 69        if (sub == 0) break;
 70    }
 71    cout << endl;
 72}
 73
 74// =============================================================================
 75// 3. ์™ธํŒ์› ๋ฌธ์ œ (TSP)
 76// =============================================================================
 77
 78const int INF = INT_MAX / 2;
 79
 80int tsp(int n, const vector<vector<int>>& dist) {
 81    // dp[mask][i]: mask ์ง‘ํ•ฉ์„ ๋ฐฉ๋ฌธํ•˜๊ณ  ํ˜„์žฌ i์— ์žˆ์„ ๋•Œ ์ตœ์†Œ ๋น„์šฉ
 82    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
 83
 84    dp[1][0] = 0;  // ์‹œ์ž‘์  0์—์„œ ์ถœ๋ฐœ
 85
 86    for (int mask = 1; mask < (1 << n); mask++) {
 87        for (int u = 0; u < n; u++) {
 88            if (!(mask & (1 << u))) continue;
 89            if (dp[mask][u] == INF) continue;
 90
 91            for (int v = 0; v < n; v++) {
 92                if (mask & (1 << v)) continue;  // ์ด๋ฏธ ๋ฐฉ๋ฌธ
 93                if (dist[u][v] == INF) continue;
 94
 95                int newMask = mask | (1 << v);
 96                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
 97            }
 98        }
 99    }
100
101    // ๋ชจ๋“  ๋„์‹œ ๋ฐฉ๋ฌธ ํ›„ ์‹œ์ž‘์ ์œผ๋กœ ๋ณต๊ท€
102    int fullMask = (1 << n) - 1;
103    int result = INF;
104    for (int i = 0; i < n; i++) {
105        if (dp[fullMask][i] != INF && dist[i][0] != INF) {
106            result = min(result, dp[fullMask][i] + dist[i][0]);
107        }
108    }
109
110    return result;
111}
112
113// TSP ๊ฒฝ๋กœ ๋ณต์›
114pair<int, vector<int>> tspWithPath(int n, const vector<vector<int>>& dist) {
115    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
116    vector<vector<int>> parent(1 << n, vector<int>(n, -1));
117
118    dp[1][0] = 0;
119
120    for (int mask = 1; mask < (1 << n); mask++) {
121        for (int u = 0; u < n; u++) {
122            if (!(mask & (1 << u))) continue;
123            if (dp[mask][u] == INF) continue;
124
125            for (int v = 0; v < n; v++) {
126                if (mask & (1 << v)) continue;
127                if (dist[u][v] == INF) continue;
128
129                int newMask = mask | (1 << v);
130                if (dp[mask][u] + dist[u][v] < dp[newMask][v]) {
131                    dp[newMask][v] = dp[mask][u] + dist[u][v];
132                    parent[newMask][v] = u;
133                }
134            }
135        }
136    }
137
138    // ์ตœ์ข… ๊ฒฐ๊ณผ
139    int fullMask = (1 << n) - 1;
140    int result = INF;
141    int lastCity = -1;
142
143    for (int i = 0; i < n; i++) {
144        if (dp[fullMask][i] != INF && dist[i][0] != INF) {
145            if (dp[fullMask][i] + dist[i][0] < result) {
146                result = dp[fullMask][i] + dist[i][0];
147                lastCity = i;
148            }
149        }
150    }
151
152    // ๊ฒฝ๋กœ ๋ณต์›
153    vector<int> path;
154    int mask = fullMask;
155    int curr = lastCity;
156
157    while (curr != -1) {
158        path.push_back(curr);
159        int prev = parent[mask][curr];
160        mask ^= (1 << curr);
161        curr = prev;
162    }
163
164    reverse(path.begin(), path.end());
165    path.push_back(0);  // ์‹œ์ž‘์ ์œผ๋กœ ๋ณต๊ท€
166
167    return {result, path};
168}
169
170// =============================================================================
171// 4. ์ž‘์—… ํ• ๋‹น ๋ฌธ์ œ (Assignment Problem)
172// =============================================================================
173
174int minCostAssignment(int n, const vector<vector<int>>& cost) {
175    // dp[mask]: mask์— ํ•ด๋‹นํ•˜๋Š” ์ž‘์—…๋“ค์ด ํ• ๋‹น๋˜์—ˆ์„ ๋•Œ ์ตœ์†Œ ๋น„์šฉ
176    vector<int> dp(1 << n, INF);
177    dp[0] = 0;
178
179    for (int mask = 0; mask < (1 << n); mask++) {
180        int person = __builtin_popcount(mask);  // ํ˜„์žฌ ํ• ๋‹นํ•  ์‚ฌ๋žŒ
181        if (person >= n) continue;
182
183        for (int job = 0; job < n; job++) {
184            if (mask & (1 << job)) continue;  // ์ด๋ฏธ ํ• ๋‹น๋œ ์ž‘์—…
185
186            int newMask = mask | (1 << job);
187            dp[newMask] = min(dp[newMask], dp[mask] + cost[person][job]);
188        }
189    }
190
191    return dp[(1 << n) - 1];
192}
193
194// =============================================================================
195// 5. ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ (Subset Sum)
196// =============================================================================
197
198bool subsetSum(const vector<int>& nums, int target) {
199    int n = nums.size();
200
201    for (int mask = 0; mask < (1 << n); mask++) {
202        int sum = 0;
203        for (int i = 0; i < n; i++) {
204            if (mask & (1 << i)) {
205                sum += nums[i];
206            }
207        }
208        if (sum == target) return true;
209    }
210
211    return false;
212}
213
214// ์ตœ์ ํ™”: Meet in the Middle
215bool subsetSumMITM(const vector<int>& nums, int target) {
216    int n = nums.size();
217    int half = n / 2;
218
219    // ์•ž์ชฝ ์ ˆ๋ฐ˜์˜ ๋ชจ๋“  ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ
220    vector<int> leftSums;
221    for (int mask = 0; mask < (1 << half); mask++) {
222        int sum = 0;
223        for (int i = 0; i < half; i++) {
224            if (mask & (1 << i)) sum += nums[i];
225        }
226        leftSums.push_back(sum);
227    }
228    sort(leftSums.begin(), leftSums.end());
229
230    // ๋’ค์ชฝ ์ ˆ๋ฐ˜ ํ™•์ธ
231    int rightHalf = n - half;
232    for (int mask = 0; mask < (1 << rightHalf); mask++) {
233        int sum = 0;
234        for (int i = 0; i < rightHalf; i++) {
235            if (mask & (1 << i)) sum += nums[half + i];
236        }
237
238        // target - sum์ด leftSums์— ์žˆ๋Š”์ง€ ํ™•์ธ
239        if (binary_search(leftSums.begin(), leftSums.end(), target - sum)) {
240            return true;
241        }
242    }
243
244    return false;
245}
246
247// =============================================================================
248// 6. ํ•ด๋ฐ€ํ„ด ๊ฒฝ๋กœ
249// =============================================================================
250
251int countHamiltonianPaths(int n, const vector<vector<int>>& adj) {
252    // dp[mask][i]: mask ์ง‘ํ•ฉ์„ ๋ฐฉ๋ฌธํ•˜๊ณ  i์—์„œ ๋๋‚˜๋Š” ๊ฒฝ๋กœ ์ˆ˜
253    vector<vector<int>> dp(1 << n, vector<int>(n, 0));
254
255    // ์‹œ์ž‘์  ์ดˆ๊ธฐํ™”
256    for (int i = 0; i < n; i++) {
257        dp[1 << i][i] = 1;
258    }
259
260    for (int mask = 1; mask < (1 << n); mask++) {
261        for (int u = 0; u < n; u++) {
262            if (!(mask & (1 << u))) continue;
263            if (dp[mask][u] == 0) continue;
264
265            for (int v : adj[u]) {
266                if (mask & (1 << v)) continue;
267
268                int newMask = mask | (1 << v);
269                dp[newMask][v] += dp[mask][u];
270            }
271        }
272    }
273
274    // ๋ชจ๋“  ์ •์  ๋ฐฉ๋ฌธํ•œ ๊ฒฝ๋กœ ์ˆ˜
275    int fullMask = (1 << n) - 1;
276    int total = 0;
277    for (int i = 0; i < n; i++) {
278        total += dp[fullMask][i];
279    }
280
281    return total;
282}
283
284// =============================================================================
285// 7. SOS DP (Sum over Subsets)
286// =============================================================================
287
288void sosDP(vector<int>& dp, int n) {
289    // dp[mask]์— mask์˜ ๋ชจ๋“  ๋ถ€๋ถ„์ง‘ํ•ฉ์˜ ํ•ฉ ์ €์žฅ
290    for (int i = 0; i < n; i++) {
291        for (int mask = 0; mask < (1 << n); mask++) {
292            if (mask & (1 << i)) {
293                dp[mask] += dp[mask ^ (1 << i)];
294            }
295        }
296    }
297}
298
299// =============================================================================
300// ํ…Œ์ŠคํŠธ
301// =============================================================================
302
303void printVector(const vector<int>& v) {
304    cout << "[";
305    for (size_t i = 0; i < v.size(); i++) {
306        cout << v[i];
307        if (i < v.size() - 1) cout << ", ";
308    }
309    cout << "]";
310}
311
312int main() {
313    cout << "============================================================" << endl;
314    cout << "๋น„ํŠธ๋งˆ์Šคํฌ DP ์˜ˆ์ œ" << endl;
315    cout << "============================================================" << endl;
316
317    // 1. ๋น„ํŠธ ์—ฐ์‚ฐ ๊ธฐ์ดˆ
318    bitOperations();
319
320    // 2. ๋ถ€๋ถ„์ง‘ํ•ฉ ์ˆœํšŒ
321    enumerateSubsets(3);
322
323    // 3. TSP
324    cout << "\n[3] ์™ธํŒ์› ๋ฌธ์ œ (TSP)" << endl;
325    vector<vector<int>> dist = {
326        {0, 10, 15, 20},
327        {10, 0, 35, 25},
328        {15, 35, 0, 30},
329        {20, 25, 30, 0}
330    };
331    cout << "    ๊ฑฐ๋ฆฌ ํ–‰๋ ฌ: 4x4" << endl;
332    cout << "    ์ตœ์†Œ ๋น„์šฉ: " << tsp(4, dist) << endl;
333
334    auto [cost, path] = tspWithPath(4, dist);
335    cout << "    ๊ฒฝ๋กœ: ";
336    printVector(path);
337    cout << endl;
338
339    // 4. ์ž‘์—… ํ• ๋‹น
340    cout << "\n[4] ์ž‘์—… ํ• ๋‹น ๋ฌธ์ œ" << endl;
341    vector<vector<int>> costMatrix = {
342        {9, 2, 7, 8},
343        {6, 4, 3, 7},
344        {5, 8, 1, 8},
345        {7, 6, 9, 4}
346    };
347    cout << "    ๋น„์šฉ ํ–‰๋ ฌ: 4x4" << endl;
348    cout << "    ์ตœ์†Œ ๋น„์šฉ: " << minCostAssignment(4, costMatrix) << endl;
349
350    // 5. ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ
351    cout << "\n[5] ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ" << endl;
352    vector<int> nums = {3, 34, 4, 12, 5, 2};
353    cout << "    ๋ฐฐ์—ด: [3, 34, 4, 12, 5, 2]" << endl;
354    cout << "    ํ•ฉ 9 ์กด์žฌ: " << (subsetSum(nums, 9) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
355    cout << "    ํ•ฉ 30 ์กด์žฌ: " << (subsetSum(nums, 30) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค") << endl;
356
357    // 6. SOS DP
358    cout << "\n[6] SOS DP" << endl;
359    vector<int> sos = {1, 2, 3, 4, 5, 6, 7, 8};  // 2^3 = 8
360    cout << "    ์ดˆ๊ธฐ: ";
361    printVector(sos);
362    cout << endl;
363    sosDP(sos, 3);
364    cout << "    SOS: ";
365    printVector(sos);
366    cout << endl;
367
368    // 7. ๋ณต์žก๋„ ์š”์•ฝ
369    cout << "\n[7] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
370    cout << "    | ๋ฌธ์ œ               | ์‹œ๊ฐ„๋ณต์žก๋„    | ๊ณต๊ฐ„๋ณต์žก๋„ |" << endl;
371    cout << "    |--------------------|---------------|------------|" << endl;
372    cout << "    | TSP                | O(nยฒ ร— 2^n)   | O(n ร— 2^n) |" << endl;
373    cout << "    | ์ž‘์—… ํ• ๋‹น          | O(n ร— 2^n)    | O(2^n)     |" << endl;
374    cout << "    | ๋ถ€๋ถ„์ง‘ํ•ฉ ํ•ฉ        | O(2^n)        | O(1)       |" << endl;
375    cout << "    | Meet in the Middle | O(n ร— 2^(n/2))| O(2^(n/2)) |" << endl;
376    cout << "    | SOS DP             | O(n ร— 2^n)    | O(2^n)     |" << endl;
377
378    // 8. ๋น„ํŠธ๋งˆ์Šคํฌ ํŒ
379    cout << "\n[8] ๋น„ํŠธ๋งˆ์Šคํฌ ํŒ" << endl;
380    cout << "    - n โ‰ค 20: ๋น„ํŠธ๋งˆ์Šคํฌ DP ๊ณ ๋ ค" << endl;
381    cout << "    - n โ‰ค 25: Meet in the Middle ๊ณ ๋ ค" << endl;
382    cout << "    - __builtin_popcount(x): 1์˜ ๊ฐœ์ˆ˜ (GCC)" << endl;
383    cout << "    - x & -x: ์ตœํ•˜์œ„ 1๋น„ํŠธ" << endl;
384    cout << "    - x & (x-1): ์ตœํ•˜์œ„ 1๋น„ํŠธ ์ œ๊ฑฐ" << endl;
385
386    cout << "\n============================================================" << endl;
387
388    return 0;
389}