{"id":28407,"date":"2024-10-27T16:10:58","date_gmt":"2024-10-27T16:10:58","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28407"},"modified":"2024-11-26T07:03:04","modified_gmt":"2024-11-26T07:03:04","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b8%b0%ec%88%98-%ec%a0%95%eb%a0%ac","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28407\/","title":{"rendered":"\ucf54\ud2c0\ub9b0 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uae30\uc218 \uc815\ub82c"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \ucde8\uc5c5 \uc900\ube44\uc0dd\uacfc \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc790\ub4e4\uc774 \uc54c\uc544\uc57c \ud560 \uae30\uc218 \uc815\ub82c(Radix Sort)\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc740 \uc815\uc218\ub4e4\uc744 \uc815\ub82c\ud558\ub294 \ub370 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998 \uc911 \ud558\ub098\ub85c, \ud2b9\ud788 \ud070 \ub370\uc774\ud130\uc14b\uc5d0\uc11c \uadf8 \uc131\ub2a5\uc774 \ube5b\uc744 \ubc1c\ud569\ub2c8\ub2e4.<\/p>\n

\uae30\uc218 \uc815\ub82c\uc774\ub780 \ubb34\uc5c7\uc778\uac00?<\/h2>\n

\uae30\uc218 \uc815\ub82c\uc740 \ubd84\uc0b0 \uc815\ub82c\uc758 \uc77c\uc885\uc73c\ub85c, \uc815\ub82c\ud560 \uac12\ub4e4\uc744 \uac1c\ubcc4 \uc790\ub9ac\uc218\ub85c \ub098\ub204\uc5b4 \ucc98\ub9ac\ud569\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \uc815\uc218\ud615 \ub370\uc774\ud130\uc5d0 \ud2b9\ud788 \ud6a8\uacfc\uc801\uc774\uba70, \uc548\uc815 \uc815\ub82c(stable sort)\uc785\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc740 \ub300\ubd80\ubd84\uc758 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uacfc \ub2ec\ub9ac \ube44\uad50 \uae30\ubc18\uc774 \uc544\ub2c8\ubbc0\ub85c, O(nk)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4. \uc5ec\uae30\uc11c n<\/code>\uc740 \uc815\ub82c\ud560 \ub370\uc774\ud130\uc758 \uac1c\uc218\uc774\uace0, k<\/code>\ub294 \uac00\uc7a5 \ud070 \uc218\uc758 \uc790\ub9ac\uc218\uc785\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\ubb38\uc81c: \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ub9ac\uc2a4\ud2b8\ub97c \uae30\uc218 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\ub77c.<\/h3>\n

\ub2e4\uc74c\uacfc \uac19\uc740 \uc785\ub825\uc774 \uc8fc\uc5b4\uc9c8 \ub54c, \uae30\uc218 \uc815\ub82c\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc815\ub82c\ub41c \uacb0\uacfc\ub97c \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n

\uc785\ub825: [170, 45, 75, 90, 802, 24, 2, 66]<\/code><\/pre>\n
\ucd9c\ub825: [2, 24, 45, 66, 75, 90, 170, 802]<\/code><\/pre>\n
\uae30\uc218 \uc815\ub82c \uc54c\uace0\ub9ac\uc998 \uc774\ud574\ud558\uae30<\/h2>\n
\uae30\uc218 \uc815\ub82c\uc758 \uae30\ubcf8 \uc544\uc774\ub514\uc5b4\ub294 \uac01 \uc790\ub9ac\ub97c \uae30\uc900\uc73c\ub85c \uce74\uc6b4\ud305 \uc815\ub82c\uc744 \ubc18\ubcf5 \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc758 \uc218\ud589 \uacfc\uc815\uc744 \ub2e8\uacc4\ubcc4\ub85c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
1\ub2e8\uacc4: \uc790\ub9ac\uc218 \ubd84\ub9ac<\/h3>\n
\uac01 \uc22b\uc790\ub97c \uc22b\uc790\uc758 \uc790\ub9ac\uc218(1\uc758 \uc790\ub9ac, 10\uc758 \uc790\ub9ac, 100\uc758 \uc790\ub9ac \ub4f1) \ubcc4\ub85c \ub098\ub204\uc5b4 \ucc98\ub9ac\ud569\ub2c8\ub2e4. \uac01 \uc790\ub9ac\uc218\ub97c \ucc98\ub9ac\ud560 \ub54c\ub294 \uce74\uc6b4\ud305 \uc815\ub82c\uc744 \ud1b5\ud574 \uc774 \uc22b\uc790\ub4e4\uc744 \uc815\ub82c\ud569\ub2c8\ub2e4.<\/p>\n
2\ub2e8\uacc4: \uce74\uc6b4\ud305 \uc815\ub82c<\/h3>\n
\uce74\uc6b4\ud305 \uc815\ub82c\uc740 \ud2b9\uc815 \uc790\ub9ac\uc218\ub97c \uae30\uc900\uc73c\ub85c \uc785\ub825 \ub9ac\uc2a4\ud2b8\ub97c \uc815\ub82c\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \uc548\uc815\uc131\uc774 \ud655\ubcf4\ub418\uae30 \ub54c\ubb38\uc5d0, \ucc98\uc74c\uc5d0 \uc870\uc815\ud55c \uc0c1\ub300\uc801\uc778 \uc21c\uc11c\ub97c \uc720\uc9c0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
3\ub2e8\uacc4: \ubc18\ubcf5<\/h3>\n
\uac00\uc7a5 \uc791\uc740 \uc790\ub9ac\uc218\ubd80\ud130 \uc2dc\uc791\ud558\uc5ec, \uac00\uc7a5 \ud070 \uc790\ub9ac\uc218\uae4c\uc9c0 \ubc18\ubcf5\ud558\uc5ec \uc815\ub82c\ud55c \ud6c4 \ucd5c\uc885\uc801\uc73c\ub85c \uc815\ub82c\ub41c \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\uae30\uc218 \uc815\ub82c\uc758 \uad6c\ud604 (\ucf54\ud2c0\ub9b0 \uc608\uc81c)<\/h2>\n
\ub2e4\uc74c\uc740 \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud558\uc5ec \uae30\uc218 \uc815\ub82c\uc744 \uad6c\ud604\ud55c \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
fun countingSort(array: IntArray, place: Int) {\n    val size = array.size\n    val output = IntArray(size)\n    val count = IntArray(10)\n\n    for (i in 0 until size) {\n        count[(array[i] \/ place) % 10]++\n    }\n\n    for (i in 1 until 10) {\n        count[i] += count[i - 1]\n    }\n\n    for (i in size - 1 downTo 0) {\n        output[count[(array[i] \/ place) % 10] - 1] = array[i]\n        count[(array[i] \/ place) % 10]--\n    }\n\n    for (i in 0 until size) {\n        array[i] = output[i]\n    }\n}\n\nfun radixSort(array: IntArray) {\n    val max = array.maxOrNull() ?: return\n\n    for (place in 1 until max + 1 step 10) {\n        countingSort(array, place)\n    }\n}\n<\/code><\/pre>\n
\uc704 \ucf54\ub4dc\ub294 \uba3c\uc800 \uce74\uc6b4\ud305 \uc815\ub82c\uc744 \uc218\ud589\ud558\ub294 countingSort<\/code> \ud568\uc218\ub97c \uc815\uc758\ud569\ub2c8\ub2e4. \uadf8 \ud6c4, \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc758 \ucd5c\ub300\uac12\uc744 \uae30\uc900\uc73c\ub85c \uc790\ub9ac\uc218\ub97c \ubc18\ubcf5\ud558\uba70 \uc815\ub82c\uc744 \uc9c4\ud589\ud558\ub294 radixSort<\/code> \ud568\uc218\ub97c \uad6c\ud604\ud569\ub2c8\ub2e4.<\/p>\n
\ucf54\ub4dc \uc124\uba85<\/h3>\n