{"id":27418,"date":"2024-10-27T14:11:29","date_gmt":"2024-10-27T14:11:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27418"},"modified":"2024-11-26T07:18:34","modified_gmt":"2024-11-26T07:18:34","slug":"c-%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\/27418\/","title":{"rendered":"C# \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uae30\uc218 \uc815\ub82c"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \uae30\uc218 \uc815\ub82c(Radix Sort)\uc758 \uac1c\ub150\uacfc \ud568\uaed8 C#\uc744 \uc774\uc6a9\ud55c \uad6c\ud604 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uae30\uc218 \uc815\ub82c\uc740 \ube44\uc815\ub82c \ub370\uc774\ud130\ub97c \uc815\ub82c\ud558\ub294 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95 \uc911 \ud558\ub098\ub85c, \ud2b9\ud788 \uc815\uc218\uac00 \ucc28\uc9c0\ud558\ub294 \ubc94\uc704\uac00 \uc81c\ud55c\uc801\uc77c \ub54c \ud2b9\ud788 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4.<\/p>\n

1. \uae30\uc218 \uc815\ub82c\uc774\ub780?<\/h2>\n

\uae30\uc218 \uc815\ub82c\uc740 \uc790\ub9bf\uc218\uc758 \uc704\uce58\uc5d0 \ub530\ub77c\uc11c \uc22b\uc790\ub97c \uc815\ub82c\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c, \uc77c\ubc18\uc801\uc73c\ub85c LSD(Least Significant Digit) \ubc29\uc2dd\uacfc MSD(Most Significant Digit) \ubc29\uc2dd\uc73c\ub85c \ub098\ub269\ub2c8\ub2e4. L\ub97c \uc0ac\uc6a9\ud558\uba74 \uac00\uc7a5 \ub0ae\uc740 \uc790\ub9bf\uc218\ubd80\ud130 \uc815\ub82c\ud558\uac8c \ub418\uace0, M\ub85c \uc2dc\uc791\ud558\uba74 \uac00\uc7a5 \ub192\uc740 \uc790\ub9bf\uc218\ubd80\ud130 \uc815\ub82c\ub429\ub2c8\ub2e4.<\/p>\n

2. \uae30\uc218 \uc815\ub82c\uc758 \ub3d9\uc791 \uc6d0\ub9ac<\/h2>\n

\uae30\uc218 \uc815\ub82c\uc758 \uc791\ub3d9 \ubc29\uc2dd\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n

    \n
  1. \uac00\uc7a5 \ub0ae\uc740 \uc790\ub9bf\uc218\ubd80\ud130 \uc2dc\uc791\ud558\uc5ec \uac01 \uc790\ub9bf\uc218\ub97c \uae30\uc900\uc73c\ub85c \ub370\uc774\ud130\ub97c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n
  2. \uc815\ub82c\uc744 \ubc18\ubcf5\ud558\uc5ec \uac00\uc7a5 \ub192\uc740 \uc790\ub9bf\uc218\uae4c\uc9c0 \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc774 \uacfc\uc815\uc5d0\uc11c \uc548\uc815\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998, \uc608\ub97c \ub4e4\uc5b4 \uacc4\uc218 \uc815\ub82c(Counting Sort)\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc790\ub9bf\uc218\ubcc4\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n

    3. \uae30\uc218 \uc815\ub82c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n

    \uae30\uc218 \uc815\ub82c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(d * (n + k))<\/code>\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c d<\/code>\ub294 \uc22b\uc790\uc758 \uc790\ub9bf\uc218, n<\/code>\uc740 \uc815\ub82c\ud560 \uc22b\uc790\uc758 \uac1c\uc218, k<\/code>\ub294 0\ubd80\ud130 \ucd5c\ub300 \uc790\ub9bf\uc218\uae4c\uc9c0\uc758 \uc22b\uc790 \ubc94\uc704\uc785\ub2c8\ub2e4. \uac00\uc7a5 \ud070 \uc7a5\uc810 \uc911 \ud558\ub098\ub294 \uae30\uc218 \uc815\ub82c\uc774 \uc548\uc815\uc801\uc774\ub77c\ub294 \uc810\uc785\ub2c8\ub2e4.<\/p>\n

    4. \uae30\uc218 \uc815\ub82c \ubb38\uc81c \ud480\uc774 \uc608\uc81c<\/h2>\n

    \uc774\ubc88\uc5d0\ub294 \uae30\uc218 \uc815\ub82c\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud2b9\uc815 \uc22b\uc790 \ubaa9\ub85d\uc744 \uc815\ub82c\ud558\ub294 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

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

    \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubaa9\ub85d\uc744 \uae30\uc218 \uc815\ub82c\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\uc2dc\uc624.
    \n\uc785\ub825: [170, 45, 75, 90, 802, 24, 2, 66]
    \n\ucd9c\ub825: [2, 24, 45, 66, 75, 90, 170, 802]<\/p>\n

    \ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h3>\n
      \n
    1. \uac00\uc7a5 \ub0ae\uc740 \uc790\ub9bf\uc218\ubd80\ud130 \uc2dc\uc791\ud569\ub2c8\ub2e4. \uccab \ubc88\uc9f8 \uc790\ub9bf\uc218\uc778 1\uc758 \uc790\ub9ac \uc22b\uc790\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
      C#\npublic static void LSDRadixSort(int[] array)\n{\n    \/\/ \uac00\uc7a5 \ud070 \uc22b\uc790\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.\n    int max = array.Max();\n    \/\/ \uc790\ub9bf\uc218\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.\n    for (int exp = 1; max \/ exp > 0; exp *= 10)\n    {\n        CountingSort(array, exp);\n    }\n}\n\nprivate static void CountingSort(int[] array, int exp)\n{\n    int n = array.Length;\n    int[] output = new int[n]; \/\/ \uc815\ub82c\ub41c \ubc30\uc5f4\n    int[] count = new int[10]; \/\/ 0-9\uae4c\uc9c0\uc758 \uc22b\uc790 \uce74\uc6b4\ud2b8\n\n    \/\/ \uc790\ub9bf\uc218\uc5d0 \ud574\ub2f9\ud558\ub294 \uc6d0\uc18c \uac1c\uc218\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n    for (int i = 0; i < n; i++)\n    {\n        count[(array[i] \/ exp) % 10]++;\n    }\n\n    \/\/ \ub204\uc801 \uce74\uc6b4\ud2b8\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n    for (int i = 1; i < 10; i++)\n    {\n        count[i] += count[i - 1];\n    }\n\n    \/\/ \uc815\ub82c\ub41c \ubc30\uc5f4\uc744 \ub9cc\ub4ed\ub2c8\ub2e4.\n    for (int i = n - 1; i >= 0; i--)\n    {\n        output[count[(array[i] \/ exp) % 10] - 1] = array[i];\n        count[(array[i] \/ exp) % 10]--;\n    }\n\n    \/\/ \uc6d0\ubcf8 \ubc30\uc5f4\uc744 \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.\n    for (int i = 0; i < n; i++)\n    {\n        array[i] = output[i];\n    }\n}\n<\/code><\/pre>\n
      \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c \uc6b0\ub9ac\ub294 LSDRadixSort<\/code> \uba54\uc11c\ub4dc\ub97c \uc815\uc758\ud558\uc600\uc2b5\ub2c8\ub2e4. \uc774 \uba54\uc11c\ub4dc\ub294 \uac01 \uc790\ub9bf\uc218\uc5d0 \ub300\ud574 CountingSort<\/code> \ub3c4\uc6c0\uc744 \ubc1b\uc544 \uc815\ub82c\uc744 \uc9c4\ud589\ud569\ub2c8\ub2e4.<\/p>\n
      5. \uad6c\ud604 \ubc0f \uc2e4\ud589<\/h2>\n
      \uc774\uc81c \uc704\uc758 \ud568\uc218\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc804\uccb4 \ud504\ub85c\uadf8\ub7a8\uc744 \uc2e4\ud589\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798\ub294 \ud504\ub85c\uadf8\ub7a8\uc758 \uc804\uccb4 \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
      C#\nusing System;\nusing System.Linq;\n\nclass Program\n{\n    public static void Main(string[] args)\n    {\n        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};\n        LSDRadixSort(array);\n\n        Console.WriteLine(\"\uc815\ub82c\ub41c \ubc30\uc5f4:\");\n        Console.WriteLine(string.Join(\", \", array));\n    }\n  \n    public static void LSDRadixSort(int[] array)\n    {\n        int max = array.Max();\n        for (int exp = 1; max \/ exp > 0; exp *= 10)\n        {\n            CountingSort(array, exp);\n        }\n    }\n\n    private static void CountingSort(int[] array, int exp)\n    {\n        int n = array.Length;\n        int[] output = new int[n];\n        int[] count = new int[10];\n\n        for (int i = 0; i < n; i++)\n        {\n            count[(array[i] \/ exp) % 10]++;\n        }\n\n        for (int i = 1; i < 10; i++)\n        {\n            count[i] += count[i - 1];\n        }\n\n        for (int i = n - 1; i >= 0; i--)\n        {\n            output[count[(array[i] \/ exp) % 10] - 1] = array[i];\n            count[(array[i] \/ exp) % 10]--;\n        }\n\n        for (int i = 0; i < n; i++)\n        {\n            array[i] = output[i];\n        }\n    }\n}\n<\/code><\/pre>\n
      \uc704\uc758 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc740 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
      \n\uc815\ub82c\ub41c \ubc30\uc5f4:\n2, 24, 45, 66, 75, 90, 170, 802\n<\/code><\/pre>\n
      6. \uae30\uc218 \uc815\ub82c\uc758 \uc7a5\ub2e8\uc810<\/h2>\n
      \uae30\uc218 \uc815\ub82c\uc758 \uc7a5\uc810\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n