\uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \ucde8\uc5c5\uc744 \uc704\ud55c \uc2a4\uc704\ud504\ud2b8 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \uc900\ube44 \uacfc\uc815\uc5d0\uc11c \uc870\ud569<\/strong> \uac1c\ub150\uc744 \uc774\ud574\ud558\uace0 \uc774\ub97c \ud65c\uc6a9\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc870\ud569\uc740 \uc8fc\uc5b4\uc9c4 n\uac1c\uc758 \uc694\uc18c \uc911\uc5d0\uc11c r\uac1c\uc758 \uc694\uc18c\ub97c \uc120\ud0dd\ud558\ub294 \ubc29\ubc95\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \uc870\ud569\uc740 \uc120\ud0dd\uc758 \uc21c\uc11c\uac00 \uc911\uc694\ud558\uc9c0 \uc54a\uc740 \uacbd\uc6b0\uc5d0 \uc4f0\uc785\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, {A, B, C}\uc5d0\uc11c 2\uac1c\uc758 \uc694\uc18c\ub97c \uc120\ud0dd\ud560 \uacbd\uc6b0, {A, B}\uc640 {B, A}\ub294 \uac19\uc740 \uc870\ud569\uc73c\ub85c \uac04\uc8fc\ub429\ub2c8\ub2e4. \uc870\ud569\uc744 \uc218\ud559\uc801\uc73c\ub85c \ud45c\ud604\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uc5ec\uae30\uc11c \uc774\uc81c \uc870\ud569\uc744 \ud65c\uc6a9\ud55c \ubb38\uc81c\ub97c \ud558\ub098 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \uc870\ud569\uc758 \uac1c\uc218\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \ubb38\uc81c\ub97c \ubd84\uc11d\ud558\uace0 \ud574\uacb0\ud558\uae30 \uc704\ud55c \uacfc\uc815\uc744 \ub2e8\uacc4\ubcc4\ub85c \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 n\uac1c\uc758 \uc22b\uc790 \uc911\uc5d0\uc11c \uc870\ud569\uc744 \uc0dd\uc131\ud558\uae30 \uc704\ud574 \uc77c\ubc18\uc801\uc73c\ub85c \uc7ac\uadc0\ub97c \uc774\uc6a9\ud55c \ubc31\ud2b8\ub798\ud0b9 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ud604\uc7ac \uc120\ud0dd\ud55c \uc22b\uc790\uc640 \uc55e\uc73c\ub85c \uc0ac\uc6a9\ud560 \uc22b\uc790\uc758 \ubc94\uc704\ub97c \uc815\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ud2b9\ud788, \uac01 \uc22b\uc790\ub97c \uc120\ud0dd\ud560 \ub54c\uc5d0\ub294 \uadf8 \uc22b\uc790\uac00 \uc120\ud0dd\ub418\uc5c8\ub294\uc9c0\ub97c \ud655\uc778\ud558\ub294 \uacfc\uc815\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.<\/p>\n \uc544\ub798\ub294 \ud2b9\uc815 \uc22b\uc790\ub97c \uc120\ud0dd\ud558\uace0 \uc774\ub4e4\uc758 \ud569\uc774 \uc704\uc758 \ucf54\ub4dc\ub97c \uc0b4\ud3b4\ubd05\uc2dc\ub2e4:<\/p>\n \uc774\uc81c \uc791\uc131\ud55c \ud568\uc218\ub97c \uc5ec\ub7ec \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub97c \ud1b5\ud574 \uac80\uc99d\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc2a4\uc704\ud504\ud2b8\ub85c \uc870\ud569\uc744 \uad6c\ud604\ud558\uace0 \uc774\ub97c \ud65c\uc6a9\ud558\uc5ec \ud2b9\uc815 \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 \uc870\ud569\uc758 \uac1c\uc218\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc870\ud569\uacfc \uac19\uc740 \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud558\ub294 \uac83\uc740 \ucde8\uc5c5\uc744 \uc704\ud55c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc911\uc694\ud55c \uc5ed\ub7c9\uc774 \ub418\ubbc0\ub85c \uafb8\uc900\ud788 \uc5f0\uc2b5\ud558\ub294 \uac83\uc774 \uc88b\uc2b5\ub2c8\ub2e4.<\/p>\n \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uba70 \uc2e4\ub825\uc744 \uc313\uc544\ub098\uac00\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\uc870\ud569\uc758 \uc815\uc758<\/h2>\n
C(n, r) = n! \/ (r! * (n - r)!)<\/code><\/pre>\n!<\/code>\ub294 \ud329\ud1a0\ub9ac\uc5bc\uc744 \uc758\ubbf8\ud558\uba70, n!\uc740 n\uc758 \ubaa8\ub4e0 \uc591\uc758 \uc815\uc218\ub97c \uacf1\ud55c \uac12\uc744 \ub098\ud0c0\ub0c5\ub2c8\ub2e4.<\/p>\n\ubb38\uc81c \uc124\uba85<\/h2>\n
\ubb38\uc81c: \uc870\ud569\uc758 \ud569<\/h3>\n
n<\/code>\uacfc k<\/code>\uc5d0 \ub300\ud574, 1\ubd80\ud130 n\uae4c\uc9c0\uc758 \uc218<\/code> \uc911\uc5d0\uc11c k<\/code>\uac1c\ub97c \uc120\ud0dd\ud558\uc5ec \ud569\uc774 target<\/code>\uc774 \ub418\ub294 \uc870\ud569\uc758 \uac1c\uc218\ub97c \uad6c\ud558\ub294 \ud568\uc218 countCombinations(n: Int, k: Int, target: Int) -> Int<\/code>\ub97c \uc791\uc131\ud558\uc138\uc694.<\/p>\n\uc785\ub825<\/h3>\n
\n
n<\/code>: \uc815\uc218 (1 \u2264 n \u2264 20)<\/li>\nk<\/code>: \uc815\uc218 (1 \u2264 k \u2264 n)<\/li>\ntarget<\/code>: \uc815\uc218 (1 \u2264 target \u2264 100)<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \ubb38\uc81c \ubd84\uc11d<\/h3>\n
k<\/code>\uac1c\ub97c \uc120\ud0dd\ud558\uc5ec \uadf8 \ud569\uc774 target<\/code>\uacfc \uac19\uc740 \uc870\ud569\uc744 \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4. \uc21c\uc11c\uc640 \uc0c1\uad00\uc5c6\uc774 \uc120\ud0dd\ud558\uae30 \ub54c\ubb38\uc5d0 \uc870\ud569\uc744 \uc0ac\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4. \ub530\ub77c\uc11c \uc6b0\uc120\uc801\uc73c\ub85c \uc870\ud569\uc758 \uac1c\ub150\uc744 \uc774\ud574\ud558\uace0 \uad6c\ud604\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.<\/p>\n2\ub2e8\uacc4: \uc870\ud569 \uc0dd\uc131 \uc54c\uace0\ub9ac\uc998<\/h3>\n
3\ub2e8\uacc4: \ucf54\ub4dc \uad6c\ud604<\/h3>\n
target<\/code>\uacfc \uac19\uc740\uc9c0 \ud655\uc778\ud558\ub294 \ubc29\ubc95\uc744 \ud3ec\ud568\ud55c \uc870\ud569 \uc0dd\uc131\uae30\uc758 \uc608\uc81c \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\nfunc countCombinations(n: Int, k: Int, target: Int) -> Int {\n var count = 0\n var combination = [Int]()\n \n func backtrack(start: Int, k: Int, sum: Int) {\n if k == 0 {\n if sum == target {\n count += 1\n }\n return\n }\n \n for i in start...n {\n combination.append(i)\n backtrack(start: i + 1, k: k - 1, sum: sum + i)\n combination.removeLast()\n }\n }\n \n backtrack(start: 1, k: k, sum: 0)\n return count\n}<\/code><\/pre>\n4\ub2e8\uacc4: \ucf54\ub4dc \uc124\uba85<\/h3>\n
\n
backtrack<\/code> \uba54\uc11c\ub4dc\uc5d0 \ucd08\uae30\uac12\uc744 \uc804\ub2ec\ud558\uc5ec \uc870\ud569 \uc0dd\uc131\uc744 \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/li>\nk<\/code>\uac00 0\uc774\ub77c\uba74 \ud604\uc7ac \uc120\ud0dd\ud55c \uc22b\uc790\uc758 \uc870\ud569\uc774 target<\/code>\uc5d0 \ud574\ub2f9\ud558\ub294\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n5\ub2e8\uacc4: \ud14c\uc2a4\ud2b8<\/h3>\n
print(countCombinations(n: 5, k: 2, target: 5)) \/\/ \ucd9c\ub825: 1 (\uc870\ud569: [2, 3])\nprint(countCombinations(n: 7, k: 3, target: 10)) \/\/ \ucd9c\ub825: 4 (\uc870\ud569: [1, 2, 7], [1, 3, 6], [2, 3, 5], [1, 4, 5])\nprint(countCombinations(n: 10, k: 2, target: 8)) \/\/ \ucd9c\ub825: 3 (\uc870\ud569: [2, 6], [3, 5], [1, 7])\n<\/code><\/pre>\n\ub9c8\ubb34\ub9ac<\/h2>\n