\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ucf54\ud2c0\ub9b0\uc744 \ud65c\uc6a9\ud558\uc5ec K\ubc88\uc9f8 \uc218\ub97c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0 \ub300\ud574 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. K\ubc88\uc9f8 \uc218\ub97c \ucc3e\ub294 \ubb38\uc81c\ub294 \ub370\uc774\ud130 \uc815\ub82c \ubc0f \uac80\uc0c9 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ucd08\ub97c \ub2e4\uc9c0\ub294 \ub370 \uc720\uc6a9\ud55c \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \ubb38\uc81c\uc758 \uc815\uc758, \uc811\uadfc \ubc29\ubc95, \ucf54\ub529 \uad6c\ud604 \ubc0f \ucd5c\uc801\ud654 \uae30\ubc95\uae4c\uc9c0 \ud3ed\ub113\uac8c \ub2e4\ub8e8\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \uc124\uba85\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n\uc790\uc5f0\uc218\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ubc30\uc5f4\uc774 \uc8fc\uc5b4\uc9c0\uace0, \uc22b\uc790 K\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \ubc30\uc5f4\uc5d0\uc11c K\ubc88\uc9f8\ub85c \uc791\uc740 \uc218\ub97c \uad6c\ud558\uc2dc\uc624.<\/p>\n
\n
- \uc785\ub825: \ubc30\uc5f4 {5, 3, 8, 1, 2}\uc640 K=3<\/li>\n
- \ucd9c\ub825: 3<\/li>\n<\/ul>\n<\/blockquote>\n
\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
\n
- \ubc30\uc5f4\uc744 \uc815\ub82c\ud55c \ud6c4, K-1 \uc778\ub371\uc2a4\uc5d0 \uc704\uce58\ud55c \uac12\uc744 \ubc18\ud658<\/li>\n
- \ud799(heap) \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec K\ubc88\uc9f8 \uc218\uae4c\uc9c0 \ud6a8\uc728\uc801\uc73c\ub85c \ucc3e\uae30<\/li>\n
- Quickselect \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud3c9\uade0 O(N) \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub85c K\ubc88\uc9f8 \uc218\ub97c \ucc3e\uae30<\/li>\n<\/ol>\n
1. \ubc30\uc5f4 \uc815\ub82c<\/h3>\n
\ubc30\uc5f4\uc744 \uc815\ub82c\ud55c \ud6c4, K-1 \uc778\ub371\uc2a4\ub97c \ucc3e\ub294 \ubc29\ubc95\uc740 \uac00\uc7a5 \uc9c1\uad00\uc801\uc774\uba70 \uc774\ud574\ud558\uae30 \uc27d\uc2b5\ub2c8\ub2e4. \ud558\uc9c0\ub9cc \ucd5c\uc545\uc758 \uacbd\uc6b0 O(N log N)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uae30 \ub54c\ubb38\uc5d0, \ub354 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc744 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
2. \ud799\uc744 \ud65c\uc6a9\ud55c \ubc29\ubc95<\/h3>\n
\ud799\uc744 \uc0ac\uc6a9\ud558\uc5ec K\ubc88\uc9f8 \uc218\ub97c \ucc3e\ub294 \ubc29\ubc95\uc740 K\uac1c\uc758 \ucd5c\uc18c \uc694\uc18c\ub97c \ud799\uc73c\ub85c \uc800\uc7a5\ud55c \ud6c4, \ud799\uc758 \ucd5c\ub300\uac12\uc744 \ucc3e\uc544 \ubc18\ud658\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc774 \uc811\uadfc\ubc95\uc740 O(N log K)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4.<\/p>\n
3. Quickselect<\/h3>\n
Quickselect \uc54c\uace0\ub9ac\uc998\uc740 QuickSort\uc758 \ud30c\ud2f0\uc158 \uae30\ubc95\uc744 \ubcc0\ud615\ud558\uc5ec \uc6d0\ud558\ub294 K\ubc88\uc9f8 \uc218\ub97c \ucc3e\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ud3c9\uade0\uc801\uc73c\ub85c O(N)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4.<\/p>\n
\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc774\uc81c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \ucf54\ub4dc\ub97c \uc791\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774\ubc88 \uc608\uc81c\uc5d0\uc11c\ub294 \ubc30\uc5f4\uc744 \uc815\ub82c\ud558\uc5ec K\ubc88\uc9f8 \uc218\ub97c \ucc3e\ub294 \uac00\uc7a5 \uc9c1\uad00\uc801\uc778 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4.<\/p>\n
K\ubc88\uc9f8 \uc218 \ucc3e\uae30 \ucf54\ub4dc<\/h3>\n
\n fun findKthNumber(arr: IntArray, k: Int): Int {\n \/\/ \ubc30\uc5f4 \uc815\ub82c\n val sortedArray = arr.sortedArray()\n \/\/ K\ubc88\uc9f8 \uc218 \ubc18\ud658 (K\ub294 1\ubd80\ud130 \uc2dc\uc791\ud558\ubbc0\ub85c K-1)\n return sortedArray[k - 1]\n }\n\n fun main() {\n val arr = intArrayOf(5, 3, 8, 1, 2)\n val k = 3\n val result = findKthNumber(arr, k)\n println(\"K\ubc88\uc9f8 \uc218: $result\") \/\/ \ucd9c\ub825: K\ubc88\uc9f8 \uc218: 3\n }\n <\/code><\/pre>\n\uc608\uc81c \ubc0f \uc124\uba85<\/h2>\n
\uc704 \ucf54\ub4dc\uc5d0\uc11c\ub294 \ub2e4\uc74c \ub2e8\uacc4\ub97c \ub530\ub985\ub2c8\ub2e4:<\/p>\n
\n
- findKthNumber \ud568\uc218\ub97c \uc815\uc758\ud558\uace0 \uc815\uc218 \ubc30\uc5f4\uacfc K\ub97c \ub9e4\uac1c\ubcc0\uc218\ub85c \ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- \ubc30\uc5f4\uc744 \uc815\ub82c\ud55c \ud6c4, K-1 \uc778\ub371\uc2a4\uc758 \uac12\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n
- main \ud568\uc218\ub97c \uc2e4\ud589\ud558\uc5ec \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
\ucd5c\uc801\ud654 \ubc0f \uae30\ud0c0 \uc811\uadfc \ubc29\ubc95<\/h2>\n
\uc704\uc758 \ud574\uacb0 \ubc29\ubc95\ub4e4\uc740 \uae30\ucd08\uc801\uc774\uba70, \uc2e4\uc81c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub294 \ub354 \ub9ce\uc740 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4\uc57c \ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. K\ubc88\uc9f8 \uc218\uc640 \uac19\uc774 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\uc5d0 \ubbfc\uac10\ud55c \ubb38\uc81c\uc5d0 \ub300\ud574 \uba87 \uac00\uc9c0 \ucd94\uac00 \ubc29\ubc95\uc744 \ub17c\uc758\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\ud799\uc744 \uc774\uc6a9\ud55c \ubc29\ubc95<\/h3>\n
\n import java.util.PriorityQueue\n\n fun findKthNumberUsingHeap(arr: IntArray, k: Int): Int {\n val minHeap = PriorityQueue(compareBy { -it })\n for (num in arr) {\n minHeap.offer(num)\n if (minHeap.size > k) {\n minHeap.poll() \/\/ K\uac1c\ub97c \ucd08\uacfc\ud560 \uacbd\uc6b0 \ucd5c\ub300\uac12 \uc81c\uac70\n }\n }\n return minHeap.poll() \/\/ K\ubc88\uc9f8 \uc218 \ubc18\ud658\n }\n <\/int><\/code><\/pre>\n Quickselect \uc54c\uace0\ub9ac\uc998<\/h3>\n
\n fun quickselect(arr: IntArray, left: Int, right: Int, k: Int): Int {\n if (left == right) {\n return arr[left]\n }\n\n val pivotIndex = partition(arr, left, right)\n if (k == pivotIndex) {\n return arr[k]\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\n fun partition(arr: IntArray, left: Int, right: Int): Int {\n val pivot = arr[right]\n var i = left\n for (j in left until right) {\n if (arr[j] < pivot) {\n swap(arr, i, j)\n i++\n }\n }\n swap(arr, i, right)\n return i\n }\n\n fun swap(arr: IntArray, i: Int, j: Int) {\n val temp = arr[i]\n arr[i] = arr[j]\n arr[j] = temp\n }\n\n fun findKthNumberQuickselect(arr: IntArray, k: Int): Int {\n return quickselect(arr, 0, arr.size - 1, k - 1)\n }\n <\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 K\ubc88\uc9f8 \uc218 \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \ud574\uacb0\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \ubc30\uc5f4 \uc815\ub82c\uc744 \ud1b5\ud55c \uc9c1\uad00\uc801\uc778 \ubc29\ubc95\ubd80\ud130, \ud799, Quickselect \uc54c\uace0\ub9ac\uc998\uae4c\uc9c0 \uc5ec\ub7ec \uc811\uadfc \ubc29\ubc95\uc744 \ud559\uc2b5\ud558\uc5ec \uc54c\uace0\ub9ac\uc998\uc758 \uae4a\uc740 \uc774\ud574\ub97c \ub3c4\uc654\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ubb38\uc81c\ub4e4\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c, \uc5ec\ub7ec\uac00\uc9c0 \ubc29\ubc95\uc744 \uc2dc\ub3c4\ud574\ubcf4\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
\ucd94\uac00\uc801\uc73c\ub85c K\ubc88\uc9f8 \uc218 \uad6c\ud558\uae30 \ubb38\uc81c\ub294 \ubc30\uc5f4\uc758 \uc815\ub82c\uacfc \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ucd08\uc774\uae30 \ub54c\ubb38\uc5d0, \uc774\ub7ec\ud55c \uae30\ubc95\ub4e4\uc744 \uc798 \uc219\uc9c0\ud558\uace0 \uc788\ub2e4\uba74 \ub2e4\uc591\ud55c \ubb38\uc81c\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \ud65c\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ucf54\ub4dc \uad6c\ud604 \ubc0f \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uace0\ub824\ud558\uc5ec \ud6a8\uc728\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc744 \uc120\ud0dd\ud558\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
\ucc38\uace0 \uc790\ub8cc<\/h2>\n