\n\ubb38\uc81c \uc774\ud574 \ubc0f \ubd84\uc11d<\/h2>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc870\ud569(combination) \uac1c\ub150\uc744 \uc801\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uae30\ub465 M\uac1c\uc5d0\uc11c \ub2e4\ub9ac N\uac1c\ub97c \uc120\ud0dd\ud558\ub294 \uac83\uc73c\ub85c, \uc870\ud569\uc758 \uc218\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uc218\uc2dd\uc73c\ub85c \ud45c\ud604\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\n C(M, N) = M! \/ (N! * (M - N)!)\n <\/pre>\n\uc5ec\uae30\uc11c C\ub294 \uc870\ud569\uc744 \uc758\ubbf8\ud558\uba70, M\uc740 \uae30\ub465\uc758 \ucd1d \uac1c\uc218, N\uc740 \ub193\uc744 \ub2e4\ub9ac\uc758 \uac1c\uc218\uc785\ub2c8\ub2e4. \uc774\ub97c C++\ub85c \uad6c\ud604\ud560 \ub54c \uc870\ud569\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\ub294 \ud568\uc218\ub97c \ub9cc\ub4e4\uc5b4 \uc8fc\uc5b4\uc57c \ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h2>\n
\uc8fc\uc5b4\uc9c4 N\uacfc M\uac12\uc5d0 \ub530\ub77c \ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c\uc758 \uacbd\uc6b0\ub294 \uc870\ud569\uc744 \ud65c\uc6a9\ud558\uc5ec \ub2e4\ub9ac\uc758 \ubc30\uce58\ub97c \uacb0\uc815\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c\uc758 \uc810\ud654\uc2dd\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n dp[n][m] = dp[n-1][m-1] + dp[n][m-1]\n <\/pre>\n\uc5ec\uae30\uc11c dp[n][m]\uc740 n\uac1c\uc758 \ub2e4\ub9ac\ub97c m\uac1c\uc758 \uae30\ub465\uc5d0 \ub193\uc744 \uc218 \uc788\ub294 \uacbd\uc6b0\uc758 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \uae30\ub465 \ud558\ub098\ub97c \uc120\ud0dd\ud574 \ub2e4\ub9ac\ub97c \ub193\uace0 \ub0a8\uc740 \ub2e4\ub9ac\ub97c \ub193\ub294 \uacbd\uc6b0\uc758 \uc218\uc640 \ub2e4\ub9ac\ub97c \ub193\uc9c0 \uc54a\uace0 \ub118\uc5b4\uac00\ub294 \uacbd\uc6b0\uc758 \uc218\ub97c \ub354\ud558\uc5ec \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h2>\n
\ub2e4\uc74c\uc740 \uc774 \uc54c\uace0\ub9ac\uc998\uc744 C++\ub85c \uad6c\ud604\ud55c \uc608\uc81c \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nlong long combinations(int n, int r) {\n if (r > n) return 0;\n if (r == 0 || r == n) return 1;\n vector<long long> dp(n + 1);\n dp[0] = 1;\n\n for (int i = 1; i <= n; ++i) {\n for (int j = i; j >= 1; --j) {\n dp[j] += dp[j - 1];\n }\n }\n return dp[r];\n}\n\nint main() {\n int n, m;\n cout << \"\ub2e4\ub9ac\uc758 \uc218\uc640 \uae30\ub465\uc758 \uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n cin >> n >> m;\n\n long long result = combinations(m, n);\n cout << \"\ucd5c\ub300 \ub2e4\ub9ac \ub193\uae30 \uac00\ub2a5 \uc870\ud569 \uc218: \" << result << endl;\n return 0;\n}\n <\/pre>\n<\/section>\n\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c \uc6b0\ub9ac\ub294 \ub2e4\ub9ac\uc758 \uc218\uc640 \uae30\ub465\uc758 \uc218\ub97c \uc785\ub825\ubc1b\uace0, \uc870\ud569\uc744 \uacc4\uc0b0\ud558\uc5ec \ucd9c\ub825\ud569\ub2c8\ub2e4. combinations \ud568\uc218\uc5d0\uc11c\ub294 \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud574 \uc870\ud569\uc744 \uacc4\uc0b0\ud558\ub294 \ubc29\uc2dd\uc744 \uc774\uc6a9\ud588\uc2b5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ud6a8\uc728\uc801\uc778 \uacc4\uc0b0\uc774 \uac00\ub2a5\ud574\uc84c\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n * r)\uc73c\ub85c, r\uc740 \uae30\ub465\uc5d0\uc11c \uc120\ud0dd\ud560 \ub2e4\ub9ac\uc758 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(n)\uc785\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ud6a8\uc728\uc801\uc778 \uad6c\uc870 \ub355\ubd84\uc5d0 \uc0c1\ub2f9\ud788 \ud070 \uac12\uc5d0\uc11c\ub3c4 \ube60\ub974\uac8c \uacb0\uacfc\ub97c \ub3c4\ucd9c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n\n\uacb0\ub860<\/h2>\n
\ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c\ub294 \uc870\ud569\ub860\uc758 \uae30\ucd08\ub97c \uc798 \uc774\ud574\ud558\uace0, \ub2e4\uc774\ub098\ubbf9 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ud480 \uc218 \uc788\ub294 \uc88b\uc740 \uc5f0\uc2b5\ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ubc29\uc2dd\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \ubfd0\ub9cc \uc544\ub2c8\ub77c \uc784\uc758\uc758 \uc870\ud569 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370\uc5d0\ub3c4 \uc720\uc6a9\ud569\ub2c8\ub2e4. \uc5ec\ub7ec\ubd84\uc740 \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uae30\ubcf8\uc801\uc778 \ud504\ub85c\uadf8\ub798\ubc0d \ub2a5\ub825 \ubfd0\ub9cc \uc544\ub2c8\ub77c \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud0a4\uc6b8 \uc218 \uc788\uc744 \uac83\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n