{"id":26878,"date":"2024-10-27T11:53:24","date_gmt":"2024-10-27T11:53:24","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26878"},"modified":"2024-11-26T07:27:24","modified_gmt":"2024-11-26T07:27:24","slug":"%ec%9e%90%eb%b0%94-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%9d%b4%ed%95%ad%ea%b3%84%ec%88%98-%ea%b5%ac%ed%95%98%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26878\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uc774\ud56d\uacc4\uc218 \uad6c\ud558\uae30 2"},"content":{"rendered":"

<\/p>\n

\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc774\ud56d \uacc4\uc218(Binomial Coefficient)\uc5d0 \ub300\ud574 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uace0, \uc774\ub97c \uad6c\ud558\ub294 \ud6a8\uc728\uc801\uc778 \ucf54\ub4dc\ub97c \uc790\ubc14\ub85c \uc791\uc131\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774\ud56d \uacc4\uc218\ub294 \uc870\ud569\uc758 \uc218\ub97c \uc140 \ub54c \uc0ac\uc6a9\ub418\uba70, “nCr”\ub85c \ud45c\uae30\ud569\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998\uc758 \uc911\uc694\uc131\uc744 \uc774\ud574\ud558\uace0, \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0 \ud544\uc694\ud55c \uc2a4\ud0ac\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\ub294 \uae30\ud68c\ub97c \uac16\uac8c \ub420 \uac83\uc785\ub2c8\ub2e4.\n<\/p>\n

\uc774\ud56d\uacc4\uc218\ub780?<\/h2>\n

\n \uc774\ud56d\uacc4\uc218\ub294 \uc8fc\uc5b4\uc9c4 n\uacfc r\uc5d0 \ub300\ud574 r\uac1c\uc758 \uc6d0\uc18c\ub97c n\uac1c\uc758 \uc6d0\uc18c \uc911\uc5d0\uc11c \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \ub9d0\ud569\ub2c8\ub2e4. \uc218\ud559\uc801\uc73c\ub85c\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \ud45c\ud604\ud569\ub2c8\ub2e4:\n<\/p>\n

\nC(n, r) = n! \/ (r! * (n - r)!)\n<\/pre>\n
\n    \uc5ec\uae30\uc11c, n!\uc740 n\uc758 \ud329\ud1a0\ub9ac\uc5bc\uc744 \uc758\ubbf8\ud558\uba70, n! = n \u00d7 (n-1) \u00d7 … \u00d7 1\uc785\ub2c8\ub2e4. \uc774\ud56d \uacc4\uc218\ub97c \uad6c\ud558\ub294 \uacf5\uc2dd\uc774 \ub2e8\uc21c\ud574 \ubcf4\uc77c \uc218 \uc788\uc9c0\ub9cc, n\uc774 \ucee4\uc9c0\uba74 \ud329\ud1a0\ub9ac\uc5bc \uac12\uc774 \uae09\uaca9\ud788 \uc99d\uac00\ud558\ubbc0\ub85c \ud070 \uc218 \uacc4\uc0b0\uc5d0 \uc720\uc758\ud574\uc57c \ud569\ub2c8\ub2e4.\n<\/p>\n
\ubb38\uc81c \uc815\uc758<\/h2>\n
\n    \ub2e4\uc74c\uc758 \ubb38\uc81c\ub97c \ud574\uacb0\ud574\ubd05\uc2dc\ub2e4:\n<\/p>\n
\n\ubb38\uc81c:<\/strong> 0 \u2264 n \u2264 30, 0 \u2264 r \u2264 n \ubc94\uc704\uc758 \uc815\uc218\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774\ud56d\uacc4\uc218 C(n, r)\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624.\n<\/p>\n
\ubb38\uc81c \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\n    \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uae30\ubcf8\uc801\uc778 \ubc29\ubc95\ubd80\ud130 \uc2dc\uc791\ud574 \ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ud558\uc9c0\ub9cc n\uc758 \ucd5c\ub300\uac12\uc774 30\uc774\ubbc0\ub85c, \ub2e8\uc21c\ud558\uac8c \ud329\ud1a0\ub9ac\uc5bc\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc740 \ube44\ud6a8\uc728\uc801\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8\ub7ec\ubbc0\ub85c \uc6b0\ub9ac\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming) \uae30\ubc95\uc744 \ud65c\uc6a9\ud558\uc5ec \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc774\uc6a9\ud55c \uc774\ud56d\uacc4\uc218 \uacc4\uc0b0<\/h3>\n
\n    \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud558\uba74 \uc911\ubcf5\ub418\ub294 \uacc4\uc0b0\uc744 \ud53c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ud56d\uacc4\uc218\ub97c \uad6c\ud558\ub294 \ub370 \uc788\uc5b4 \ub2e4\uc74c\uacfc \uac19\uc740 \uc131\uc9c8\uc744 \ud65c\uc6a9\ud569\ub2c8\ub2e4:\n<\/p>\n
\nC(n, r) = C(n-1, r-1) + C(n-1, r)\n<\/pre>\n
\n    \uc774 \uc131\uc9c8\uc744 \ud1b5\ud574, \uae30\ubcf8 \uacbd\uc6b0 C(n, 0) = C(n, n) = 1\uc640 \uac19\uc740 \uac12\uc744 \ucd08\uae30\ud654\ud558\uace0, \ub098\uba38\uc9c0 \uac12\uc744 \ucc44\uc6cc \ub098\uac00\ub294 \ubc29\uc2dd\uc73c\ub85c \uc774\ud56d \uacc4\uc218\ub97c \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n    \uc544\ub798\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc774\uc6a9\ud558\uc5ec \uc774\ud56d \uacc4\uc218\ub97c \uacc4\uc0b0\ud558\ub294 \uc790\ubc14 \ucf54\ub4dc\uc785\ub2c8\ub2e4:\n<\/p>\n
\npublic class BinomialCoefficient {\n    public static int binomialCoefficient(int n, int r) {\n        int[][] dp = new int[n + 1][r + 1];\n\n        \/\/ C(n, 0) = 1\n        for (int i = 0; i <= n; i++) {\n            dp[i][0] = 1;\n        }\n\n        \/\/ C(n, n) = 1\n        for (int i = 0; i <= n; i++) {\n            dp[i][i] = 1;\n        }\n\n        \/\/ Fill the dp table\n        for (int i = 1; i <= n; i++) {\n            for (int j = 1; j <= Math.min(i, r); j++) {\n                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n            }\n        }\n\n        return dp[n][r];\n    }\n\n    public static void main(String[] args) {\n        int n = 5; \/\/ \uc608\uc2dc\ub97c \uc704\ud55c \uac12\n        int r = 2; \/\/ \uc608\uc2dc\ub97c \uc704\ud55c \uac12\n        System.out.println(\"C(\" + n + \", \" + r + \") = \" + binomialCoefficient(n, r));\n    }\n}\n<\/pre>\n
\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n    \uc704 \ucf54\ub4dc\ub294 \uc774\ud56d\uacc4\uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \uc811\uadfc \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uac01 \ub2e8\uacc4\uc5d0 \ub300\ud55c \uc124\uba85\uc740 \uc544\ub798\uc640 \uac19\uc2b5\ub2c8\ub2e4:\n<\/p>\n