\n\ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c<\/strong>\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ub9e5\ub77d\uc5d0\uc11c \ubc1c\uc0dd\ud569\ub2c8\ub2e4. \ub2f9\uc2e0\uc740 N\uac1c\uc758 \ub2e4\ub9ac\ub97c \ub193\uace0, M\uac1c\uc758 \uad50\uac01\uc744 \uac74\uc124\ud558\uace0\uc790 \ud569\ub2c8\ub2e4. \uc774 \ubb38\uc81c\uc758 \ubaa9\ud45c\ub294 \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ub2e4\ub9ac \ub193\uae30 \uc870\ud569\uc758 \uc218\ub97c \uacc4\uc0b0\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc785\ub825<\/strong><\/p>\n \ucd9c\ub825<\/strong><\/p>\n \n \ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c\ub294 \ubcf8\uc9c8\uc801\uc73c\ub85c \uc870\ud569 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc6b0\ub9ac\ub294 N\uac1c\uc758 \ub2e4\ub9ac \uc911\uc5d0\uc11c M\uac1c\ub97c \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc744 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uc870\ud569\uc758 \uc218\ub294 \ub2e4\uc74c \uacf5\uc2dd\uc73c\ub85c \uacc4\uc0b0\ub429\ub2c8\ub2e4:\n <\/p>\n \n \ud558\uc9c0\ub9cc factorial\uc744 \uc9c1\uc811 \uacc4\uc0b0\ud558\uba74 \uc2dc\uac04\uc774 \uc624\ub798 \uac78\ub9ac\uae30 \ub54c\ubb38\uc5d0, \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc6b0\ub9ac\ub294 \ub450 \uac1c\uc758 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \n \uba3c\uc800 DP \ubc30\uc5f4\uc744 \ucd08\uae30\ud654\ud569\ub2c8\ub2e4. \n \ub2e4\ub9ac\ub97c \ud558\ub098 \ub298\ub9ac\uac70\ub4e0 \uad50\uac01\uc744 \ud558\ub098 \ub193\ub294 \uc120\ud0dd\uc774 \uac00\ub2a5\ud569\ub2c8\ub2e4. \uc544\ub798\uc640 \uac19\uc740 \uc810\ud654\uc2dd\uc744 \uc0ac\uc6a9\ud558\uc5ec dp \ubc30\uc5f4\uc744 \ucc44\uc6cc\ub098\uac08 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc5ec\uae30\uc11c \n \ubaa8\ub4e0 \ubc94\uc704\ub97c \ucc44\uc6b4 \ud6c4\uc5d0, \ub2e4\ub9ac \ub193\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc790\ubc14 \ucf54\ub4dc\ub294 \uc544\ub798\uc640 \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \n \ubcf8 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N*M)\uc785\ub2c8\ub2e4. \uc774\ub294 \ub450 \uac1c\uc758 \uc774\uc911 \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\uba74\uc11c DP \ud14c\uc774\ube14\uc744 \ucc44\uc6b0\ub294 \uacfc\uc815\uc5d0\uc11c \ubc1c\uc0dd\ud558\ub294 \uc2dc\uac04\uc785\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N*M)\uc73c\ub85c, DP \ubc30\uc5f4\uc744 \uc800\uc7a5\ud558\uae30 \uc704\ud55c \uacf5\uac04\uc744 \uace0\ub824\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n \n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 ‘\ub2e4\ub9ac \ub193\uae30’ \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc870\ud569 \uc774\ub860\uacfc \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc5d0 \ub300\ud55c \uc774\ud574\uac00 \ud544\uc694\ud569\ub2c8\ub2e4. <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \ub2e4\ub9ac\ub294 \uc11c\ub85c \uacb9\uce58\uc9c0 \uc54a\uc544\uc57c \ud558\uba70, \uac01 \uad50\uac01\uc740 \ub450 \ub2e4\ub9ac\ub97c \uc5f0\uacb0\ud558\ub294 \uc5ed\ud560\uc744 \uc218\ud589\ud569\ub2c8\ub2e4. \ub2e4\ub9ac\ub97c \ub193\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \uacc4\uc0b0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc870\ud569(combination)\uacfc \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(dynamic programming)\uc5d0 \ub300\ud55c \uc9c0\uc2dd\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.\n <\/p>\n\ubb38\uc81c \uc815\uc758<\/h2>\n
\n
\n
\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
C(N, M) = N! \/ (M! * (N-M)!)<\/code><\/pre>\n
\n \uccab \ubc88\uc9f8 \ubc30\uc5f4\uc740 \ub2e4\ub9ac\ub97c \ub193\uae30 \uc704\ud574 \uc120\ud0dd\ud55c \uad50\uac01\uc758 \uac1c\uc218\ub97c \uae30\ub85d\ud558\uace0, \ub450 \ubc88\uc9f8 \ubc30\uc5f4\uc740 \ub2e4\ub9ac\ub97c \ub193\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4.\n <\/p>\n\ubb38\uc81c \ud480\uc774<\/h2>\n
1\ub2e8\uacc4: \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ubc30\uc5f4 \ucd08\uae30\ud654<\/h3>\n
dp[i][j]<\/code>\ub294 i\uac1c\uc758 \ub2e4\ub9ac\uc640 j\uac1c\uc758 \uad50\uac01\uc744 \ub193\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \ubc30\uc5f4\uc744 0\uc73c\ub85c \ucd08\uae30\ud654\ud55c \ud6c4,
\n dp[0][0] = 1<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4. \uc774\ub294 \ub2e4\ub9ac\uac00 \uc5c6\uace0 \uad50\uac01\ub3c4 \uc5c6\ub294 \uacbd\uc6b0\ub294 1\uac00\uc9c0 \ubc29\ubc95\uc774 \uc788\ub2e4\ub294 \uac83\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/p>\n2\ub2e8\uacc4: \uc810\ud654\uc2dd \uad6c\ud558\uae30<\/h3>\n
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]<\/code><\/pre>\ndp[i-1][j-1]<\/code>\ub294 i-1\uac1c\uc758 \ub2e4\ub9ac\uc640 j-1\uac1c\uc758 \uad50\uac01\uc744 \ub193\uc744 \ub54c, \uc0c8\ub85c\uc6b4 \ub2e4\ub9ac\ub97c \ucd94\uac00\ud558\ub294 \uacbd\uc6b0\uc774\uace0,
\n dp[i-1][j]<\/code>\ub294 \uc0c8\ub85c\uc6b4 \ub2e4\ub9ac\ub97c \ucd94\uac00\ud558\uc9c0 \uc54a\uace0 i-1\uac1c\uc758 \ub2e4\ub9ac\ub85c j\uac1c\uc758 \uad50\uac01\uc744 \ub193\ub294 \uacbd\uc6b0\uc785\ub2c8\ub2e4.\n <\/p>\n3\ub2e8\uacc4: \ucd5c\uc885 \uacb0\uacfc \ucd9c\ub825<\/h3>\n
dp[N][M]<\/code>\ub97c \ucd9c\ub825\ud558\uc5ec \ucd5c\uc885\uc801\uc73c\ub85c \ub2e4\ub9ac\ub97c \ub193\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \uc54c \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\npublic class BridgeBuilding {\n public static void main(String[] args) {\n int N = 5; \/\/ \ub2e4\ub9ac\uc758 \uc218\n int M = 3; \/\/ \uad50\uac01\uc758 \uc218\n \n System.out.println(countWays(N, M));\n }\n \n public static int countWays(int n, int m) {\n int[][] dp = new int[n + 1][m + 1];\n\n for (int i = 0; i <= n; i++) {\n for (int j = 0; j <= Math.min(i, m); j++) {\n if (j == 0) {\n dp[i][j] = 1; \/\/ \ubaa8\ub4e0 \uad50\uac01\uc744 \ub193\uc9c0 \uc54a\ub294 \uacbd\uc6b0\n } else if (i > 0) {\n dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];\n }\n }\n }\n \n return dp[n][m];\n }\n}\n<\/code><\/pre>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
\ub9c8\ubb34\ub9ac<\/h2>\n
\n \uc81c\uc2dc\ub41c \uc790\ubc14 \ucf54\ub4dc\ub97c \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc5c8\uc73c\uba70, \ube44\uc2b7\ud55c \uc720\ud615\uc758 \ubb38\uc81c\ub97c \uc811\ud560 \ub54c\uc5d0\ub3c4 \uadf8\ub7f0 \uc811\uadfc\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc744 \uac83\uc785\ub2c8\ub2e4.
\n \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub610 \ub2e4\ub978 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub904\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n