\ucf54\ub529\ud14c\uc2a4\ud2b8\ub294 \ud604\ub300 \uc18c\ud504\ud2b8\uc6e8\uc5b4 \uac1c\ubc1c\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \uc694\uc18c\uc785\ub2c8\ub2e4. \uae30\uc5c5\ub4e4\uc740 \uac1c\ubc1c\uc790\uc758 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud3c9\uac00\ud558\uae30 \uc704\ud574 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ucd9c\uc81c\ud569\ub2c8\ub2e4. \uc624\ub298\uc740 \ubc30\uc5f4\uc5d0\uc11c K\ubc88\uc9f8 \uc218\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ubc30\uc5f4\uc744 \ub2e4\ub8e8\ub294 \uae30\ubcf8\uc801\uc778 \uc54c\uace0\ub9ac\uc998 \uae30\uc220\uc744 \uc313\uc744 \uc218 \uc788\ub294 \uc88b\uc740 \uc608\uc2dc\uc785\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 \ubc30\uc5f4 \uc774 \ubb38\uc81c\ub294 \ubc30\uc5f4\uc744 \uc815\ub82c\ud55c \ud6c4\uc5d0 K\ubc88\uc9f8 \uc694\uc18c\ub97c \uc27d\uac8c \ucc3e\uc744 \uc218 \uc788\uc73c\ub098, \uc815\ub82c \ubc29\ubc95\uc5d0 \ub530\ub77c \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uac00 \ub2ec\ub77c\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc5ec\uae30\uc11c\ub294 \ub450 \uac00\uc9c0 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc704 \ucf54\ub4dc\uc5d0\uc11c\ub294 \ub2e8\uc21c\ud788 \ubc30\uc5f4\uc744 \uc815\ub82c\ud558\uace0 K\ubc88\uc9f8 \uc694\uc18c\ub97c \ucc3e\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 Quickselect \uc54c\uace0\ub9ac\uc998\uc740 \ud035\uc18c\ud2b8\uc640 \uc720\uc0ac\ud55c \ubc29\uc2dd\uc73c\ub85c K\ubc88\uc9f8 \uc791\uc740 \uc218\ub97c \ucc3e\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \ud3c9\uade0\uc801\uc73c\ub85c \uc704 \ucf54\ub4dc\ub97c \ud1b5\ud574 Quickselect \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud558\uc5ec K\ubc88\uc9f8 \uc218\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc3e\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \ud3c9\uade0\uc801\uc73c\ub85c \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub2e4\ub8e8\uc5b4\uc9c0\ub294 \ubc30\uc5f4\uc5d0\uc11c K\ubc88\uc9f8 \uc218 \ucc3e\uae30 \ubb38\uc81c\ub97c \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uac04\ub2e8\ud55c \uc815\ub82c\uc744 \ud1b5\ud574\uc11c\ub3c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc9c0\ub9cc, Quickselect\uc640 \uac19\uc740 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc131\ub2a5\uc744 \uadf9\ub300\ud654\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ub0b4\uc6a9\ub4e4\uc740 \uc2e4\uc81c \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \ub9e4\uc6b0 \uc720\uc6a9\ud558\uac8c \ud65c\uc6a9\ub420 \uc218 \uc788\uc73c\ubbc0\ub85c, \uaf2d \uc5f0\uc2b5\ud574\ubcf4\uc2dc\uae30\ub97c \uad8c\uc7a5\ud569\ub2c8\ub2e4.<\/p>\n \ubaa8\ub4e0 \uc54c\uace0\ub9ac\uc998\uc740 \uae30\ubcf8\uc801\uc778 \uc774\ud574\uac00 \uc120\ud589\ub41c \ud6c4, \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud1b5\ud574 \uc751\uc6a9\ub825\uc744 \ud0a4\uc6cc\uac00\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub354 \ub2e4\uc591\ud55c \ubc30\uc5f4 \ubb38\uc81c\uc640 \uace0\uae09 \uc54c\uace0\ub9ac\uc998\uc744 \ub2e4\ub8e8\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"arr<\/code>\uc640 \uc815\uc218 k<\/code>\uac00 \uc788\uc744 \ub54c, arr<\/code>\uc5d0\uc11c K\ubc88\uc9f8\ub85c \uc791\uc740 \uc218\ub97c \ucc3e\uc544 \ubc18\ud658\ud558\uc2dc\uc624. \ubc30\uc5f4\uc758 \uc778\ub371\uc2a4\ub294 0\ubd80\ud130 \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/p>\n\uc785\ub825<\/h3>\n
\n
arr<\/code>, \uae38\uc774\ub294 1 \uc774\uc0c1 100,000 \uc774\ud558.<\/li>\nk<\/code>, 1 \uc774\uc0c1 \ubc30\uc5f4\uc758 \uae38\uc774 \uc774\ud558.<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
arr<\/code>\uc5d0\uc11c K\ubc88\uc9f8\ub85c \uc791\uc740 \uc218\ub97c \ubc18\ud658\ud55c\ub2e4.<\/p>\n\uc608\uc2dc<\/h2>\n
arr = [3, 1, 2, 4, 5], k = 2<\/code>
\n\ucd9c\ub825:<\/strong> 2<\/code>
\n\uc124\uba85:<\/strong> \ubc30\uc5f4\uc744 \uc624\ub984\ucc28\uc21c \uc815\ub82c\ud558\uba74 [1, 2, 3, 4, 5]\uac00 \ub418\uace0, 2\ubc88\uc9f8 \uc218\ub294 2\uc785\ub2c8\ub2e4.\n<\/div>\narr = [7, 10, 4, 3, 20, 15], k = 3<\/code>
\n\ucd9c\ub825:<\/strong> 7<\/code>
\n\uc124\uba85:<\/strong> \ubc30\uc5f4\uc744 \uc624\ub984\ucc28\uc21c \uc815\ub82c\ud558\uba74 [3, 4, 7, 10, 15, 20]\uac00 \ub418\uace0, 3\ubc88\uc9f8 \uc218\ub294 7\uc785\ub2c8\ub2e4.\n<\/div>\n\ud480\uc774 \uacfc\uc815<\/h2>\n
\ud574\uacb0 \ubc29\ubc95 1: \ubc30\uc5f4 \uc815\ub82c \ud6c4 K\ubc88\uc9f8 \uc218 \ucc3e\uae30<\/h3>\n
\n
k - 1<\/code>\uc5d0 \ud574\ub2f9\ud558\ub294 \uac12\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc \uc608\uc2dc<\/h4>\n
function findKthNumber(arr, k) {\n arr.sort((a, b) => a - b); \/\/ \ubc30\uc5f4\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\n return arr[k - 1]; \/\/ K\ubc88\uc9f8 \uc218 \ubc18\ud658\n}\n\n\/\/ \uc608\uc2dc \uc2e4\ud589\nconsole.log(findKthNumber([3, 1, 2, 4, 5], 2)); \/\/ 2\nconsole.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); \/\/ 7\n<\/code><\/pre>\nO(n log n)<\/code>\uc785\ub2c8\ub2e4. \ud558\uc9c0\ub9cc, \ubc18\ub4dc\uc2dc \uc815\ub82c\ud560 \ud544\uc694 \uc5c6\uc774 K\ubc88\uc9f8 \uc791\uc740 \uc218\ub9cc \ucc3e\ub294 \ubc29\ubc95\uc774 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n\ud574\uacb0 \ubc29\ubc95 2: Quickselect \uc54c\uace0\ub9ac\uc998<\/h3>\n
O(n)<\/code>\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ubd80\ubd84 \ubc30\uc5f4\uc744 \uc124\uc815\ud558\uace0, \ud53c\ubc97\uc744 \uc120\ud0dd\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4.<\/p>\n\n
\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc \uc608\uc2dc<\/h4>\n
function quickSelect(arr, left, right, k) {\n if (left === right) {\n return arr[left]; \/\/ \ubc30\uc5f4\uc5d0 \uc790\uc2e0\ub9cc \uc788\ub294 \uacbd\uc6b0\n }\n const pivotIndex = partition(arr, left, right);\n if (k === pivotIndex) {\n return arr[k]; \/\/ K\ubc88\uc9f8 \uc218 \ubc1c\uacac\n } else if (k < pivotIndex) {\n return quickSelect(arr, left, pivotIndex - 1, k);\n } else {\n return quickSelect(arr, pivotIndex + 1, right, k);\n }\n}\n\nfunction partition(arr, left, right) {\n const pivot = arr[right]; \/\/ \ub9c8\uc9c0\ub9c9 \uc694\uc18c\ub97c \ud53c\ubc97\uc73c\ub85c \uc120\ud0dd\n let i = left; \n for (let j = left; j < right; j++) {\n if (arr[j] <= pivot) {\n [arr[i], arr[j]] = [arr[j], arr[i]]; \/\/ \uad50\ud658\n i++;\n }\n }\n [arr[i], arr[right]] = [arr[right], arr[i]]; \/\/ \ud53c\ubc97 \ucd5c\uc885 \uc704\uce58\n return i; \/\/ \ud53c\ubc97\uc758 \uc778\ub371\uc2a4 \ubc18\ud658\n}\n\nfunction findKthNumber(arr, k) {\n return quickSelect(arr, 0, arr.length - 1, k - 1); \/\/ K-1\uc744 \uc778\uc790\ub85c \uc804\ub2ec\n}\n\n\/\/ \uc608\uc2dc \uc2e4\ud589\nconsole.log(findKthNumber([3, 1, 2, 4, 5], 2)); \/\/ 2\nconsole.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); \/\/ 7\n<\/code><\/pre>\nO(n)<\/code>\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\ubbc0\ub85c \ub300\uaddc\ubaa8 \ub370\uc774\ud130\uc5d0\uc11c \ub354\uc6b1 \uc720\uc6a9\ud569\ub2c8\ub2e4.<\/p>\n\uacb0\ub860<\/h2>\n