\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \uae30\uc218 \uc815\ub82c(Radix Sort)\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc740 \uc815\uc218\ub098 \ubb38\uc790\uc5f4\uc758 \uac01 \uc790\ub9ac\uc218\ub97c \uae30\uc900\uc73c\ub85c \uc815\ub82c\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \ud2b9\uc815 \uc870\uac74 \ud558\uc5d0 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \uae30\uc218 \uc815\ub82c\uc758 \uac1c\ub150, \ub3d9\uc791 \ubc29\uc2dd, \uadf8\ub9ac\uace0 \uc790\ubc14\ub85c \uad6c\ud604\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc744 \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ud480\uc774 \ub2a5\ub825\uc744 \ud55c \ub2e8\uacc4 \ub04c\uc5b4\uc62c\ub9ac\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
\uae30\uc218 \uc815\ub82c\uc740 \ub300\ud45c\uc801\uc778 \ube44\uad50 \uae30\ubc18 \uc815\ub82c\uc774 \uc544\ub2c8\ub77c, \ube44\uad50\ud558\uc9c0 \uc54a\uace0 \ud0a4\uc758 \uc790\ub9ac\uc218\ub97c \uc774\uc6a9\ud558\uc5ec \uc815\ub82c\ud558\ub294 \ube44\uad50 \ube44\uc815\ub82c \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc77c\ubc18\uc801\uc73c\ub85c \uae30\uc218 \uc815\ub82c\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc8fc\uc694 \ub2e8\uacc4\ub97c \uac70\uce69\ub2c8\ub2e4:<\/p>\n
\uae30\uc218 \uc815\ub82c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n*k)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c n\uc740 \ub370\uc774\ud130\uc758 \uac1c\uc218, k\ub294 \uc22b\uc790\uc758 \uc790\ub9ac\uc218\uc785\ub2c8\ub2e4. \ub530\ub77c\uc11c, \uae30\uc218 \uc815\ub82c\uc740 \uc790\ub9ac\uc218\uac00 \uc801\uc740 \uacbd\uc6b0, \ub610\ub294 \ub370\uc774\ud130\uc758 \uac1c\uc218\uac00 \ub9ce\uc9c0 \uc54a\uc740 \uacbd\uc6b0\uc5d0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n
\uae30\uc218 \uc815\ub82c\uc758 \uc791\ub3d9 \uc6d0\ub9ac\ub97c \uc774\ud574\ud558\uae30 \uc704\ud574 \uac04\ub2e8\ud55c \uc608\uc81c\ub97c \ud1b5\ud574 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \ubc30\uc5f4\uc744 \uae30\uc218 \uc815\ub82c\uc744 \uc774\uc6a9\ud574 \uc815\ub82c\ud55c\ub2e4\uace0 \uac00\uc815\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n
[170, 45, 75, 90, 802, 24, 2, 66]<\/code><\/pre>\n\uc774 \ubc30\uc5f4\uc5d0\uc11c \uae30\uc218 \uc815\ub82c\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4:<\/p>\n
Step 1: LSB(Least Significant Bit) \uae30\uc900\uc73c\ub85c \uc815\ub82c<\/h3>\n
\ucd5c\ud558\uc704 \uc790\ub9ac\uc218(1\uc758 \uc790\ub9ac)\ub97c \uae30\uc900\uc73c\ub85c \ubc30\uc5f4\uc744 \uc815\ub82c\ud569\ub2c8\ub2e4:<\/p>\n
[170, 90, 802, 24, 2, 45, 75, 66]<\/code><\/pre>\n1\uc758 \uc790\ub9ac\uc5d0\uc11c \uc791\uc740 \uc22b\uc790\ub97c \uba3c\uc800 \ubc30\uce58\ud558\uac8c \ub429\ub2c8\ub2e4.<\/p>\n
Step 2: 10\uc758 \uc790\ub9ac \uae30\uc900\uc73c\ub85c \uc815\ub82c<\/h3>\n
\uc774\ubc88\uc5d0\ub294 10\uc758 \uc790\ub9ac\ub97c \uae30\uc900\uc73c\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4:<\/p>\n
[170, 802, 24, 2, 45, 75, 90, 66]<\/code><\/pre>\n\uc774\ub807\uac8c \ud55c \uc790\ub9ac\uc529 \uc21c\ucc28\uc801\uc73c\ub85c \uc9c4\ud589\ud574 \ub098\uac11\ub2c8\ub2e4.<\/p>\n
Step 3: 100\uc758 \uc790\ub9ac \uae30\uc900\uc73c\ub85c \uc815\ub82c<\/h3>\n
\ub9c8\uc9c0\ub9c9\uc73c\ub85c 100\uc758 \uc790\ub9ac\ub97c \uae30\uc900\uc73c\ub85c \uc815\ub82c\ud558\uba74:<\/p>\n
[2, 24, 45, 66, 75, 90, 170, 802]<\/code><\/pre>\n\uc774\uc81c \ubc30\uc5f4\uc774 \uc644\uc804\ud788 \uc815\ub82c\ub41c \uac83\uc744 \ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
3. \uae30\uc218 \uc815\ub82c \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc774\uc81c \uc790\ubc14\ub85c \uae30\uc218 \uc815\ub82c\uc744 \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798\uc758 \ucf54\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \uae30\uc218 \uc815\ub82c\uc744 \uc218\ud589\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
\n public class RadixSort {\n \/\/ \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc758 \ucd5c\ub313\uac12\uc744 \ucc3e\uc544 \ubc18\ud658\ud558\ub294 \uba54\uc11c\ub4dc\n static int getMax(int[] arr, int n) {\n int max = arr[0];\n for (int i = 1; i < n; i++) {\n if (arr[i] > max) {\n max = arr[i];\n }\n }\n return max;\n }\n\n \/\/ \ud2b9\uc815 \uc790\ub9ac\uc218\uc5d0 \ub300\ud574 counting sort\ub97c \uc218\ud589\ud558\ub294 \uba54\uc11c\ub4dc\n static void countingSort(int[] arr, int n, int exp) {\n int[] output = new int[n]; \/\/ \uc815\ub82c\ub41c \uacb0\uacfc\ub97c \ub2f4\uc744 \ubc30\uc5f4\n int[] count = new int[10]; \/\/ 0~9\uae4c\uc9c0\uc758 \uc22b\uc790\uc5d0 \ub300\ud574 \uce74\uc6b4\ud2b8\n\n for (int i = 0; i < n; i++) {\n count[(arr[i] \/ exp) % 10]++;\n }\n\n for (int i = 1; i < 10; i++) {\n count[i] += count[i - 1];\n }\n\n for (int i = n - 1; i >= 0; i--) {\n output[count[(arr[i] \/ exp) % 10] - 1] = arr[i];\n count[(arr[i] \/ exp) % 10]--;\n }\n\n for (int i = 0; i < n; i++) {\n arr[i] = output[i];\n }\n }\n\n \/\/ \uae30\uc218 \uc815\ub82c \uba54\uc11c\ub4dc\n static void radixSort(int[] arr) {\n int n = arr.length;\n int max = getMax(arr, n);\n\n for (int exp = 1; max \/ exp > 0; exp *= 10) {\n countingSort(arr, n, exp);\n }\n }\n\n \/\/ \uba54\uc778 \uba54\uc11c\ub4dc\n public static void main(String[] args) {\n int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};\n radixSort(arr);\n\n System.out.println(\"\uc815\ub82c\ub41c \ubc30\uc5f4: \");\n for (int num : arr) {\n System.out.print(num + \" \");\n }\n }\n }\n <\/code><\/pre>\n\uc774 \ucf54\ub4dc\ub294 \uc22b\uc790\uc758 \uac01 \uc790\ub9ac\ubcc4\ub85c \uc815\ub82c\uc744 \uc218\ud589\ud558\uc5ec \ucd5c\uc885\uc801\uc73c\ub85c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ub41c \ubc30\uc5f4\uc744 \ucd9c\ub825\ud569\ub2c8\ub2e4. getMax<\/strong>, countingSort<\/strong>, radixSort<\/strong> \uba54\uc11c\ub4dc\ub97c \ud1b5\ud574 \uac01 \ub2e8\uacc4\uc758 \uc5ed\ud560\uc744 \uad6c\ud604\ud558\uace0 \uc788\uc5b4, \uae30\uc218 \uc815\ub82c\uc758 \uc791\ub3d9 \uc6d0\ub9ac\ub97c \uc27d\uac8c \uc774\ud574\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n4. \uae30\uc218 \uc815\ub82c\uc758 \uc7a5\ub2e8\uc810<\/h2>\n\uc7a5\uc810<\/h3>\n\n- O(n * k)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub85c, \uaddc\uce59\uc801\uc778 \ub370\uc774\ud130\uc758 \uc815\ub82c\uc5d0 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/li>\n
- \uc811\uadfc \ud328\ud134\uc774 \uc608\uce21 \uac00\ub2a5\ud558\ubbc0\ub85c \ub370\uc774\ud130\ubca0\uc774\uc2a4\uc640 \uac19\uc740 \uc2dc\uc2a4\ud15c\uc5d0\uc11c \uc720\ub9ac\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\ub2e8\uc810<\/h3>\n\n- \uba54\ubaa8\ub9ac \uc0ac\uc6a9\uc774 \ucd94\uac00\ub85c \ud544\uc694\ud558\uc5ec \ud070 \ub370\uc774\ud130\uc14b\uc5d0\ub294 \uc801\ud569\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\n
- \ubd80\ub3d9\uc18c\uc218\uc810 \uc22b\uc790\uc5d0\ub294 \uc801\uc6a9\ud558\uae30 \uc5b4\ub835\uc2b5\ub2c8\ub2e4.<\/li>\n<\/ul>\n
5. \uae30\uc218 \uc815\ub82c \uc751\uc6a9 \ubb38\uc81c<\/h2>\n
\uc774\uc81c \uae30\uc218 \uc815\ub82c\uc744 \ud65c\uc6a9\ud574\ubcfc \uc218 \uc788\ub294 \uac04\ub2e8\ud55c \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \uc124\uba85<\/h3>\n
\uc815\uc218 \ubc30\uc5f4\uc774 \uc8fc\uc5b4\uc9c8 \ub54c, \uae30\uc218 \uc815\ub82c\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubc30\uc5f4\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\ub77c. \ub2e8, \ubc30\uc5f4\uc758 \ucd5c\ub300 \uae38\uc774\ub294 1000\uc774\uba70, \uac01 \uc6d0\uc18c\ub294 0 \uc774\uc0c1 10000 \uc774\ud558\uc758 \uc815\uc218\uc774\ub2e4.<\/p>\n
\uc81c\ud55c \uc0ac\ud56d<\/h3>\n\n- \uae30\uc218 \uc815\ub82c\uc744 \ubc18\ub4dc\uc2dc \uc0ac\uc6a9\ud574\uc57c \ud558\uba70, \ub2e4\ub978 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud574\uc11c\ub294 \uc548 \ub41c\ub2e4.<\/li>\n
- \ubd88\ud544\uc694\ud55c \ubcc0\uc218\ub97c \uc0ac\uc6a9\ud558\uc9c0 \uc54a\uace0\ub3c4 \ud574\uacb0\ud574\uc57c \ud55c\ub2e4.<\/li>\n<\/ul>\n
\ud574\uacb0 \uacfc\uc815<\/h3>\n
\uc704\uc758 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uae30\uc218 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uadf8\ub300\ub85c \uc801\uc6a9\ud558\uba74 \ub429\ub2c8\ub2e4.<\/p>\n
\uc608\uc81c \uc785\ub825<\/h3>\n[3, 6, 1, 8, 4, 7, 9, 2, 5]<\/code><\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n[1, 2, 3, 4, 5, 6, 7, 8, 9]<\/code><\/pre>\n\ucf54\ub4dc \uc2e4\ud589<\/h3>\n\n public class RadixSortExample {\n public static void main(String[] args) {\n int[] arr = {3, 6, 1, 8, 4, 7, 9, 2, 5};\n RadixSort.radixSort(arr);\n System.out.println(\"\uc815\ub82c\ub41c \ubc30\uc5f4: \");\n for (int num : arr) {\n System.out.print(num + \" \");\n }\n }\n }\n <\/code><\/pre>\n6. \ub9c8\ubb34\ub9ac<\/h2>\n
\uc774\ubc88 \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \uae30\uc218 \uc815\ub82c\uc758 \uac1c\ub150, \ub3d9\uc791 \ubc29\uc2dd, \uc790\ubc14 \uad6c\ud604 \ubc0f \ubb38\uc81c \ud480\uc774 \uacfc\uc815\uc744 \ub2e4\ub904\ubd24\uc2b5\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc740 \uc81c\ucd9c \ubc0f \uc81c\ucd9c \uae30\uc900\uc5d0 \ub530\ub77c \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \uc751\uc6a9\ub420 \uc218 \uc788\ub294 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud480\uc774\uc5d0\uc11c \uae30\uc218 \uc815\ub82c\uc744 \uc790\uc8fc \ud65c\uc6a9\ud558\uc2dc\uae38 \ubc14\ub77c\uba70, \ub2e4\uc74c\uc5d0\ub3c4 \uc720\uc775\ud55c \ub0b4\uc6a9\uc744 \uac00\uc9c0\uace0 \ucc3e\uc544\uc624\uaca0\uc2b5\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"