{"id":27728,"date":"2024-10-27T14:43:26","date_gmt":"2024-10-27T14:43:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27728"},"modified":"2024-11-26T07:15:47","modified_gmt":"2024-11-26T07:15:47","slug":"c-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%a1%b0%ed%95%a9-%ec%95%8c%ec%95%84%eb%b3%b4%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27728\/","title":{"rendered":"C++ \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uc870\ud569 \uc54c\uc544\ubcf4\uae30"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694, \uc5ec\ub7ec\ubd84! \uc774\ubc88 \uc2dc\uac04\uc5d0\ub294 C++\ub97c \uc774\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc5d0 \ub300\ud574 \uc774\uc57c\uae30\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ud2b9\ud788, \uc870\ud569(Combination) \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \uae4a\uc774 \uc788\ub294 \uc774\ud574\ub97c \ub3d5\uae30 \uc704\ud574 \ubb38\uc81c\ub97c \ud558\ub098 \ud480\uc5b4\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \uc870\ud569\uc740 \ud2b9\uc815 \uc870\uac74\uc744 \ucda9\uc871\ud558\ub294 \ud56d\ubaa9\ub4e4\uc744 \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc744 \ucc3e\ub294\ub370 \ub9e4\uc6b0 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n

\uc870\ud569\uc758 \uc815\uc758<\/h2>\n

\uc870\ud569\uc740 \uc8fc\uc5b4\uc9c4 \uc694\uc18c\ub4e4 \uc911\uc5d0\uc11c \ud2b9\uc815 \uac1c\uc218\uc758 \uc694\uc18c\ub97c \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uc9d1\ud569 {A, B, C}\uc5d0\uc11c 2\uac1c\ub97c \uc120\ud0dd\ud558\ub294 \uacbd\uc6b0\ub294 {A, B}, {A, C}, {B, C}\uc758 3\uac00\uc9c0\uac00 \ub429\ub2c8\ub2e4. \uc5ec\uae30\uc11c \uc911\uc694\ud55c \uc810\uc740 \uc120\ud0dd\ub41c \uc694\uc18c\ub4e4\uc758 \uc21c\uc11c\uac00 \uc911\uc694\ud558\uc9c0 \uc54a\ub2e4\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774\ub294 \uc6b0\ub9ac\uac00 \uc21c\uc5f4(Permutation)\uacfc \uad6c\ubcc4\ub418\ub294 \uc911\uc694\ud55c \ucc28\uc774\uc810\uc785\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\ubb38\uc81c: \uc870\ud569\uc758 \ud569<\/h3>\n

\uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 nums<\/code>\uc640 \uc815\uc218 target<\/code>\uac00 \uc788\uc744 \ub54c, target<\/code>\uc758 \ud569\uc744 \ub9cc\ub4e4 \uc218 \uc788\ub294 \uc870\ud569\uc744 \ubaa8\ub450 \ucc3e\uc544\uc11c \ucd9c\ub825\ud558\uc2dc\uc624. \uc870\ud569\uc5d0\uc11c \uac01 \uc22b\uc790\ub294 \uc5ec\ub7ec \ubc88 \uc0ac\uc6a9\ub420 \uc218 \uc788\uc73c\uba70, \uac19\uc740 \uc22b\uc790\uac00 \uc788\ub294 \uc870\ud569\uc740 \uc5ec\ub7ec \ubc88 \ud3ec\ud568\ud558\uc9c0 \uc54a\uc544\uc57c \ud569\ub2c8\ub2e4.<\/p>\n

\uc785\ub825 \uc608\uc2dc<\/h3>\n
nums = [2, 3, 6, 7]\ntarget = 7<\/code><\/pre>\n
\ucd9c\ub825 \uc608\uc2dc<\/h3>\n
[[2, 2, 3], [7]]<\/code><\/pre>\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1. \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc6b0\ub9ac\ub294 \ubc31\ud2b8\ub798\ud0b9(Backtracking) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \ubc31\ud2b8\ub798\ud0b9\uc740 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc5d0\uc11c \uac00\ub2a5\ud55c \uc120\ud0dd\uc744 \ud0d0\uc0c9\ud558\uace0, \ub9cc\uc57d \uadf8 \uc120\ud0dd\uc774 \uc720\ud6a8\ud558\uc9c0 \uc54a\uac70\ub098 \ucd5c\uc801 \ud574\ub97c \ucc3e\uc9c0 \ubabb\ud558\uba74 \uc774\uc804 \ub2e8\uacc4\ub85c \ub3cc\uc544\uac00\uc11c \ub2e4\ub978 \uc120\ud0dd\uc744 \uc2dc\ub3c4\ud558\ub294 \uc811\uadfc \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
2. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h3>\n
\uc774\ubc88 \ubb38\uc81c\uc5d0 \ub300\ud55c \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc774\ub8e8\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n
    \n
  1. \ud604\uc7ac\uc758 \uc870\ud569\uc744 \ubc30\uc5f4\uc5d0 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li>\n
  2. \uc870\ud569\uc758 \ud569\uc774 target<\/code>\uacfc \uac19\uc544\uc9c0\uba74 \ud574\ub2f9 \uc870\ud569\uc744 \uacb0\uacfc \ubc30\uc5f4\uc5d0 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li>\n
  3. \ud604\uc7ac\uc758 \uc870\ud569\uc774 target<\/code>\ubcf4\ub2e4 \ud06c\uba74 \uc7ac\uadc0 \ud638\ucd9c\uc744 \uc885\ub8cc\ud569\ub2c8\ub2e4.<\/li>\n
  4. \uc870\ud569\uc5d0 \ub300\ud55c \uac00\ub2a5\ud55c \uc22b\uc790\ub97c \ucd94\uac00\ud558\uace0, \uac19\uc740 \uc22b\uc790\ub97c \uc120\ud0dd\ud560 \uc218 \uc788\ub3c4\ub85d \uc7ac\uadc0 \ud638\ucd9c\uc744 \ud569\ub2c8\ub2e4.<\/li>\n
  5. \ub9c8\uc9c0\ub9c9\uc73c\ub85c \uc120\ud0dd\ud55c \uc22b\uc790\ub97c \ub2e4\uc2dc \uc81c\uac70\ud558\uc5ec \uc774\uc804 \uc0c1\ud0dc\ub85c \ub3cc\uc544\uac11\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    3. \ucf54\ub4dc \uad6c\ud604\ud558\uae30<\/h3>\n
    \uc774\uc81c C++\ub85c \uad6c\ud604\ud55c \ucf54\ub4dc\ub97c \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
    #include <iostream>\n#include <vector>\nusing namespace std;\n\nvoid backtrack(vector<int> &combination, vector<vector<int>> &result, vector<int> &nums, int target, int start) {\n    if (target == 0) {\n        result.push_back(combination);\n        return;\n    }\n    \n    for (int i = start; i < nums.size(); i++) {\n        if (nums[i] > target) continue; \/\/ \ud604\uc7ac \uc22b\uc790\uac00 target\ubcf4\ub2e4 \ud06c\uba74 \uac74\ub108\ub6f4\ub2e4\n        combination.push_back(nums[i]); \/\/ \uc870\ud569\uc5d0 \uc22b\uc790\ub97c \ucd94\uac00\n        backtrack(combination, result, nums, target - nums[i], i); \/\/ \uc7ac\uadc0 \ud638\ucd9c\n        combination.pop_back(); \/\/ \ub9c8\uc9c0\ub9c9 \uc22b\uc790\ub97c \uc81c\uac70\ud558\uc5ec \uc774\uc804 \uc0c1\ud0dc\ub85c \ub3cc\uc544\uac04\ub2e4\n    }\n}\n\nvector<vector<int>> combinationSum(vector<int> &nums, int target) {\n    vector<vector<int>> result;\n    vector<int> combination;\n    backtrack(combination, result, nums, target, 0);\n    return result;\n}\n\nint main() {\n    vector<int> nums = {2, 3, 6, 7};\n    int target = 7;\n    vector<vector<int>> result = combinationSum(nums, target);\n    \n    for (const auto &comb : result) {\n        cout << \"[ \";\n        for (int num : comb) {\n            cout << num << \" \";\n        }\n        cout << \"]\" << endl;\n    }\n    \n    return 0;\n}<\/code><\/pre>\n
    4. \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \uc704 \ucf54\ub4dc\ub294 combinationSum<\/code>\ub77c\ub294 \ud568\uc218\uac00 \uc8fc\uc5b4\uc9c4 \uc22b\uc790 \ubc30\uc5f4\uacfc \ud0c0\uac9f \uac12\uc744 \uc785\ub825\ubc1b\uc544 \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uc870\ud569\uc758 \ubc30\uc5f4\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4. \ud568\uc218 \ub0b4\ubd80\uc5d0\uc11c\ub294 backtrack<\/code>\ub77c\ub294 \uc7ac\uadc0 \ud568\uc218\ub97c \ud638\ucd9c\ud558\uc5ec \uc870\ud569\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4.<\/p>\n