\n\uc791\uc131\uc790: \uc870\uad11\ud615 | \ub0a0\uc9dc: 2024\ub144 11\uc6d4 26\uc77c<\/p>\n<\/header>\n\n1. \uc774\ud56d\uacc4\uc218\ub780?<\/h2>\n
\n \uc774\ud56d\uacc4\uc218\ub294 \uc870\ud569\ub860\uc5d0\uc11c \ub450 \uac1c\uc758 \uc815\uc218 n,k\uc5d0 \ub300\ud574 \uc815\uc758\ub429\ub2c8\ub2e4. n\uac1c \uc911\uc5d0\uc11c k\uac1c\ub97c \uc120\ud0dd\ud558\ub294
\n \ubc29\ubc95\uc758 \uc218\ub97c \ub098\ud0c0\ub0b4\uba70, \ud45c\uae30\ubc95\uc740 C(n, k) \ub610\ub294 (n choose k)\uc785\ub2c8\ub2e4. \uc774\ud56d\uacc4\uc218\ub294
\n \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ub429\ub2c8\ub2e4:\n <\/p>\n
\n- C(n, k) = n! \/ (k! * (n-k)!)<\/li>\n<\/ul>\n
\n \uc5ec\uae30\uc11c n!\uc740 n\uc758 \ud329\ud1a0\ub9ac\uc5bc\ub85c, n! = n \u00d7 (n-1) \u00d7 (n-2) \u00d7 … \u00d7 1\uc785\ub2c8\ub2e4.
\n \uc774\ud56d\uacc4\uc218\ub294 \uc870\ud569 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \ub54c \ub9e4\uc6b0 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub429\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n2. \ubb38\uc81c \uc124\uba85<\/h2>\n
\n \ubb38\uc81c: \uc8fc\uc5b4\uc9c4 n\uacfc k\uc5d0 \ub300\ud574 \uc774\ud56d\uacc4\uc218 C(n, k)\ub97c \uacc4\uc0b0\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc2dc\uc624.
\n n\uc740 0\ubd80\ud130 30\uae4c\uc9c0\uc758 \uc815\uc218\uc774\uace0, k\ub294 0\ubd80\ud130 n\uae4c\uc9c0\uc758 \uc815\uc218\uc774\ub2e4.\n <\/p>\n<\/section>\n\n3. \ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
\n \uc774 \ubb38\uc81c\ub294 \uc774\ud56d\uacc4\uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \uc5ec\ub7ec \uac00\uc9c0 \ubc29\ubc95\uc774 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc6b0\ub9ac\ub294 \uc7ac\uadc0, \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d, \ub610\ub294 \uc218\ud559 \uacf5\uc2dd\uc744 \uc774\uc6a9\ud55c \ubc29\ubc95 \ub4f1\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc5ec\uae30\uc5d0\uc11c\ub294 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming) \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n
3.1 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)<\/h3>\n
\n \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc740 \ubb38\uc81c\ub97c \uc791\uc740 \ud558\uc704 \ubb38\uc81c\ub85c \ub098\ub204\uace0, \uc774 \ud558\uc704 \ubb38\uc81c\uc758 \uacb0\uacfc\ub97c
\n \uc800\uc7a5\ud558\uc5ec \uc774\ud6c4 \ubb38\uc81c\uc5d0 \uc7ac\uc0ac\uc6a9\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc774\ud56d\uacc4\uc218\ub294 \ub2e4\uc74c\uc758 \uc810\ud654\uc2dd\uc744
\n \ud65c\uc6a9\ud558\uc5ec \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n- C(n, k) = C(n-1, k) + C(n-1, k-1)<\/li>\n
- \uae30\ubcf8 \uacbd\uc6b0: C(n, 0) = C(n, n) = 1<\/li>\n<\/ul>\n
\n \uc704\uc758 \uc810\ud654\uc2dd\uc5d0\uc11c \uac01\uac01\uc758 \uacbd\uc6b0\uc5d0 \ub300\ud574 \uc774\ud56d\uacc4\uc218\ub97c \uc7ac\uadc0\uc801\uc73c\ub85c \uad6c\ud560 \uc218 \uc788\uc9c0\ub9cc
\n \uc911\ubcf5 \uacc4\uc0b0\uc774 \ubc1c\uc0dd\ud558\uac8c \ub429\ub2c8\ub2e4. \uc774\ub97c \ud53c\ud558\uae30 \uc704\ud574 DP \ud14c\uc774\ube14\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac15\uc758\ub97c
\n \uc9c4\ud589\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n4. \uad6c\ud604<\/h2>\n
\n \uc774\uc81c \uc774\ud56d\uacc4\uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \ud30c\uc774\uc36c \ud568\uc218\uc758 \ucf54\ub4dc\ub97c \uc791\uc131\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.
\n DP \ud14c\uc774\ube14\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc774\ud56d\uacc4\uc218\ub97c \uad6c\ud558\ub294 \ubc29\uc2dd\uc744 \uad6c\ud604\ud560 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n
\n\ndef binomial_coefficient(n, k):\n # DP \ud14c\uc774\ube14 \ucd08\uae30\ud654\n dp = [[0] * (k + 1) for _ in range(n + 1)]\n\n # \uae30\ubcf8 \uacbd\uc6b0 \uc124\uc815\n for i in range(n + 1):\n dp[i][0] = 1 # C(i, 0) = 1\n dp[i][i] = 1 # C(i, i) = 1\n\n # \uc810\ud654\uc2dd\uc5d0 \ub530\ub77c DP \ud14c\uc774\ube14\uc744 \ucc44\uc6c0\n for i in range(1, n + 1):\n for j in range(1, min(i, k) + 1):\n dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]\n\n return dp[n][k]\n<\/code>\n <\/pre>\n\n \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c, \uc8fc\uc5b4\uc9c4 n\uacfc k\uc5d0 \ub300\ud574 DP \ud14c\uc774\ube14\uc744 \ucd08\uae30\ud654\ud558\uace0 \uae30\ubcf8 \uacbd\uc6b0\ub97c \uc124\uc815\ud55c \ub4a4
\n \uc810\ud654\uc2dd\uc744 \ud1b5\ud574 DP \ud14c\uc774\ube14\uc744 \ucc44\uc6cc\ub098\uac11\ub2c8\ub2e4.
\n \uacb0\uacfc\uc801\uc73c\ub85c dp[n][k]\uc5d0 \uc774\ud56d\uacc4\uc218\uac00 \uc800\uc7a5\ub429\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\n5. \ud14c\uc2a4\ud2b8<\/h2>\n
\n \uc704\uc5d0\uc11c \uad6c\ud604\ud55c \ud568\uc218\ub97c \ud14c\uc2a4\ud2b8\ud574\ubcfc \ucc28\ub840\uc785\ub2c8\ub2e4. C(5, 2)\uc640 \uac19\uc740 \uac04\ub2e8\ud55c \uc608\uc81c\ub97c \uc0ac\uc6a9\ud558\uc5ec
\n \ud568\uc218\uc758 \uc815\ud655\uc131\uc744 \uac80\uc99d\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n\n# \ud14c\uc2a4\ud2b8\nprint(binomial_coefficient(5, 2)) # \ucd9c\ub825: 10\nprint(binomial_coefficient(30, 15)) # \ucd9c\ub825: 155117520\n<\/code>\n <\/pre>\n\n \uc774\uc640 \uac19\uc774 \ud568\uc218\ub97c \ud638\ucd9c\ud558\uc5ec \uc774\ud56d\uacc4\uc218\ub97c \uacc4\uc0b0\ud558\uace0 \uadf8 \uacb0\uacfc\ub97c \ucd9c\ub825\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc704\uc758 \uc785\ub825\uac12\uc5d0 \ub300\ud55c \uacb0\uacfc\uac00 \ub9de\ub294\uc9c0\ub97c \ud655\uc778\ud574\ubcf4\uc138\uc694.\n <\/p>\n<\/section>\n\n6. \uacb0\ub860<\/h2>\n
\n \uc774\ubc88 \uac15\uc88c\ub97c \ud1b5\ud574 \uc774\ud56d\uacc4\uc218\uc758 \uc815\uc758\uc640 \uacc4\uc0b0 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4.
\n \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \ud1b5\ud574 \ud6a8\uc728\uc801\uc73c\ub85c \uc774\ud56d\uacc4\uc218\ub97c \uacc4\uc0b0\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4.
\n \ud30c\uc774\uc36c\uc744 \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud558\ub294 \uacfc\uc815 \ub610\ud55c \uc790\uc138\ud788 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4.
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8 \ubc0f \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uacb0\uc5d0\uc11c \uc790\uc8fc \uc0ac\uc6a9\ub418\ubbc0\ub85c,
\n \uc798 \uc775\ud600\ub450\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n <\/p>\n
\n \ucd94\uac00\uc801\uc73c\ub85c, \uc774\ud56d\uacc4\uc218\uc640 \uad00\ub828\ub41c \uace0\uae09 \ubb38\uc81c\ub4e4\uc744 \ud480\uc5b4\ubcf4\uba70 \uc2e4\ub825\uc744 \ub354\uc6b1 \ub2e8\ub828\ud574\ubcf4\uc138\uc694.
\n \uac10\uc0ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n